Problem Statement

Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.
Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.

Team Takahashi scored A_i runs in the top of the i-th inning (1\leq i\leq 9), and Team Aoki scored B_j runs in the bottom of the j-th inning (1\leq j\leq 8).
At the end of the top of the ninth, Team Takahashi's score is not less than Team Aoki's score.
Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.

Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.
Team Takahashi's score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki's score is the total runs scored in the bottoms of the innings.

Constraints

• 0\leq A_i, B_j\leq 99
• A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
• All input values are integers.

Sample Input 1

0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0

Sample Output 1

5

At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.
Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be 7-8, allowing them to win.
Note that scoring four runs would result in a draw and not a victory.

Sample Input 2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Sample Output 2

1

Problem Statement

You are given two grids, each with N rows and N columns, referred to as grid A and grid B.
Each cell in the grids contains a lowercase English letter.
The character at the i-th row and j-th column of grid A is A_{i, j}.
The character at the i-th row and j-th column of grid B is B_{i, j}.

The two grids differ in exactly one cell. That is, there exists exactly one pair (i, j) of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Find this (i, j).

Constraints

• 1 \leq N \leq 100
• A_{i, j} and B_{i, j} are all lowercase English letters.
• There exists exactly one pair (i, j) such that A_{i, j} \neq B_{i, j}.

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From A_{2, 1} = d and B_{2, 1} = b, we have A_{2, 1} \neq B_{2, 1}, so (i, j) = (2, 1) satisfies the condition in the problem statement.

Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9

Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation.
2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^2.
• After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
• After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
  • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
  • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
  • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
• After the fourth operation, the sequence has one ball, of size 2^4.
• After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
• After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
• After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^0.
• After the second operation, the sequence has one ball, of size 2^1.
• After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
• After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
• After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.

Problem Statement

There is a grid of H rows and W columns. Some cells (possibly zero) contain magnets.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H of length W. If the j-th character of S_i is #, it indicates that there is a magnet in the cell at the i-th row from the top and j-th column from the left; if it is ., it indicates that the cell is empty.

Takahashi, wearing an iron armor, can move in the grid as follows:

• If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
• Otherwise, he can move to any one of the vertically or horizontally adjacent cells.
  However, he cannot exit the grid.

For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.

Here, in the definition of degree of freedom, "cells he can reach by repeatedly moving" mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W consisting of . and #.
• There is at least one cell without a magnet.

Sample Input 1

3 5
.#...
.....
.#..#

Sample Output 1

9

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. If Takahashi starts at (2,3), possible movements include:

• (2,3) \to (2,4) \to (1,4) \to (1,5) \to (2,5)
• (2,3) \to (2,4) \to (3,4)
• (2,3) \to (2,2)
• (2,3) \to (1,3)
• (2,3) \to (3,3)

Thus, including the cells he passes through, he can reach at least nine cells from (2,3).
Actually, no other cells can be reached, so the degree of freedom for (2,3) is 9.

This is the maximum degree of freedom among all cells without magnets, so print 9.

Sample Input 2

3 3
..#
#..
..#

Sample Output 2

1

For any cell without a magnet, there is a magnet in at least one of the adjacent cells.
Thus, he cannot move from any of these cells, so their degrees of freedom are 1.
Therefore, print 1.

Problem Statement

On a coordinate plane, there are N points P_1, P_2, \ldots, P_N, where point P_i has coordinates (X_i, Y_i).
The distance \text{dist}(A, B) between two points A and B is defined as follows:

A rabbit is initially at point A.
A rabbit at position (x, y) can jump to (x+1, y+1), (x+1, y-1), (x-1, y+1), or (x-1, y-1) in one jump.
\text{dist}(A, B) is defined as the minimum number of jumps required to get from point A to point B.
If it is impossible to get from point A to point B after any number of jumps, let \text{dist}(A, B) = 0.

Calculate the sum \displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i, Y_i \leq 10^8
• For i \neq j, (X_i, Y_i) \neq (X_j, Y_j)
• All input values are integers.

Sample Input 1

3
0 0
1 3
5 6

Sample Output 1

3

P_1, P_2, and P_3 have coordinates (0,0), (1,3), and (5,6), respectively.
The rabbit can get from P_1 to P_2 in three jumps via (0,0) \to (1,1) \to (0,2) \to (1,3), but not in two or fewer jumps,
so \text{dist}(P_1, P_2) = 3.
The rabbit cannot get from P_1 to P_3 or from P_2 to P_3, so \text{dist}(P_1, P_3) = \text{dist}(P_2, P_3) = 0.

Therefore, the answer is \displaystyle\sum_{i=1}^{2}\displaystyle\sum_{j=i+1}^3\text{dist}(P_i, P_j)=\text{dist}(P_1, P_2)+\text{dist}(P_1, P_3)+\text{dist}(P_2, P_3)=3+0+0=3.

Sample Input 2

5
0 5
1 7
2 9
3 8
4 6

Sample Output 2

11

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N).
Calculate the following expression:

The constraints guarantee that the answer is less than 2^{63}.

Constraints

• 2 \leq N \leq 4 \times 10^5
• 0 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

3
2 5 3

Sample Output 1

4

For (i, j) = (1, 2), we have \max(A_j - A_i, 0) = \max(3, 0) = 3.
For (i, j) = (1, 3), we have \max(A_j - A_i, 0) = \max(1, 0) = 1.
For (i, j) = (2, 3), we have \max(A_j - A_i, 0) = \max(-2, 0) = 0.
Adding these together gives 3 + 1 + 0 = 4, which is the answer.

Sample Input 2

10
5 9 3 0 4 8 7 5 4 0

Sample Output 2

58

Problem Statement

You are given a rooted tree with N vertices numbered 1 to N.
Vertex 1 is the root, and the parent of vertex i (2 \leq i \leq N) is vertex p_i (p_i < i).
Additionally, there is a sequence A = (A_1, A_2, \dots, A_N).

The hash value of the rooted tree is calculated as follows:

• Define f(n) (1 \leq n \leq N) as follows in the order n = N, N-1, \dots, 2, 1.
  • If vertex n is a leaf, f(n) = A_n.
  • If vertex n is not a leaf, \displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c), where C(n) is the set of children of n.
• The hash value of the rooted tree is f(1) \bmod{998244353}.

Process Q queries in the order they are given.
Each query provides v and x, so update A_v to x and then compute the hash value of the rooted tree.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq p_i < i
• 0 \leq A_i < 998244353
• 1 \leq v \leq N
• 0 \leq x < 998244353
• All input values are integers.

Sample Input 1

3 2
1 1
3 5 1
3 4
2 1

Sample Output 1

23
7

Initially, A = (3, 5, 1).
The first query is processed as follows:

• Update A_3 to 4. Now A = (3, 5, 4).
• The hash value of the rooted tree is calculated as follows to be 23, which should be printed.
  • Vertex 3 has no children. Thus, f(3) = 4.
  • Vertex 2 has no children. Thus, f(2) = 5.
  • Vertex 1 has children 2 and 3. Thus, f(1) = 3 + 5 \times 4 = 23.
  • f(1) \bmod{998244353} = 23 is the hash value of the rooted tree.

The second query is processed as follows:

• Update A_2 to 1. Now A = (3, 1, 4).
• The hash value of the rooted tree is calculated as follows to be 7:
  • Vertex 3 has no children. Thus, f(3) = 4.
  • Vertex 2 has no children. Thus, f(2) = 1.
  • Vertex 1 has children 2 and 3. Thus, f(1) = 3 + 1 \times 4 = 7.
  • f(1) \bmod{998244353} = 7 is the hash value of the rooted tree.

Sample Input 2

5 4
1 1 2 2
2 5 4 4 1
3 3
5 0
4 5
5 2

Sample Output 2

29
17
17
47

Sample Input 3

10 10
1 2 1 2 5 6 3 5 1
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
1 21524934
9 529970099
6 757265587
8 219853537
5 687675301
5 844033519
8 780395611
2 285523485
6 13801766
3 487663184

Sample Output 3

876873846
952166813
626349486
341294449
466546009
331098453
469507939
414882732
86695436
199797684