Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

• All values in input are integers.
• 1 \le R \le H \le 10
• 1 \le C \le W \le 10

Sample Input 1

3 4
2 2

Sample Output 1

4

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.

Sample Input 2

3 4
1 3

Sample Output 2

3

Sample Input 3

3 4
3 4

Sample Output 3

2

When H=3 and W=4, the grid looks as follows.

• For Sample Input 1, there are 4 squares adjacent to Square (2,2).
• For Sample Input 2, there are 3 squares adjacent to Square (1,3).
• For Sample Input 3, there are 2 squares adjacent to Square (3,4).

Sample Input 4

1 10
1 5

Sample Output 4

2

Sample Input 5

8 1
8 1

Sample Output 5

1

Sample Input 6

1 1
1 1

Sample Output 6

0

Problem Statement

Find a length-N string that satisfies all of the following conditions:

• Each character is - or =.
• It is a palindrome.
• It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.

The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

• A_1,A_2,A_3,A_4 and A_5 have letters s, n, u, k, and e written on them, respectively.
• For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
• The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.

Constraints

• 5\leq H\leq 100
• 5\leq W\leq 100
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.
• The given grid has a unique conforming set of cells.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

Sample Output 3

9 3
8 3
7 3
6 3
5 3

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N, each consisting of lowercase English letters. The lengths of these strings are all distinct.

Sort these strings in ascending order of length, and then concatenate them in that order to form a single string.

Constraints

• 2 \leq N \leq 50
• N is an integer.
• Each S_i is a string consisting of lowercase English letters with length between 1 and 50, inclusive.
• If i \neq j, the length of S_i is different from the length of S_j.

Sample Input 1

3
tc
oder
a

Sample Output 1

atcoder

When we sort (tc, oder, a) in ascending order of length, we get (a, tc, oder). Concatenating them in this order yields the string atcoder.

Sample Input 2

4
cat
enate
on
c

Sample Output 2

concatenate

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

• 1 x : Put one ball with the integer x written on it into the bag.
• 2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
• 3 : Print the number of different integers written on the balls in the bag.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq x \leq 10^{6}
• When a query of the second type is given, the bag has a ball with the integer x written on it.
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

8
1 3
1 1
1 4
3
2 1
3
1 5
3

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

Sample Output 2

1
1

Problem Statement

You are given two sequences of positive integers of length N, L=(L_1,L_2,\ldots,L_N) and R=(R_1,R_2,\ldots,R_N), and an integer M.

Find the number of pairs of integers (l,r) that satisfy both of the following conditions:

• 1\le l \le r \le M
• For every 1\le i\le N, the interval [l,r] does not completely contain the interval [L_i,R_i].

Constraints

• 1\le N,M\le 2\times 10^5
• 1\le L_i\le R_i\le M
• All input values are integers.

Sample Input 1

2 4
1 2
3 4

Sample Output 1

5

The five pairs (l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) satisfy the conditions.

For example, (l,r)=(1,3) does not satisfy the conditions because the interval [1,3] completely contains the interval [1,2].

Sample Input 2

6 5
1 1
2 2
3 3
4 4
5 5
1 5

Sample Output 2

0

There may be cases where no pairs of integers satisfy the conditions.

Sample Input 3

6 20
8 12
14 20
11 13
5 19
4 11
1 6

Sample Output 3

102

Problem Statement

There is a rooted tree T with N vertices, where the vertices are numbered as vertex 1, vertex 2, \ldots, vertex N.
Vertex 1 is the root of T, and the (direct) parent of vertex i (2 \leq i \leq N) is P_i.

Additionally, vertex i (1 \leq i \leq N) has C_i candies. All (C_1 + C_2 + \cdots + C_N) candies are distinguishable from each other.

Takahashi gave instructions to N squirrels. Specifically, he gave the following instruction to the i-th squirrel (1 \leq i \leq N):

• Choose and collect D_i candies from the subtree rooted at vertex i.

Different squirrels cannot take the same candy.
Output the number, modulo 998244353, of possible ways to choose the candies.

Here, even if the set of candies ultimately chosen is the same, if the squirrels that chose them are different, they are counted as different ways.
If it is impossible for all squirrels to bring back candies as instructed, output 0.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• 1 \leq C_i \leq 10^9
• 1 \leq D_i
• D_1 + D_2 + \cdots + D_N \leq 10^6
• All input values are integers.
• T is a rooted tree with vertex 1 as the root.

Sample Input 1

5
1 1 3 3
1 2 1 2 3
1 1 3 1 1

Sample Output 1

144

We call the candies so that we have candy 1 at vertex 1, candies 2, 3 at vertex 2, candy 4 at vertex 3, candies 5, 6 at vertex 4, and candies 7, 8, 9 at vertex 5.

One possible way to choose the candies is as follows:

• Squirrel 1 collects candy 3 from the tree rooted at vertex 1 (consisting of vertices 1, 2, 3, 4, 5).
• Squirrel 2 collects candy 2 from the tree rooted at vertex 2 (consisting of vertex 2).
• Squirrel 3 collects candies 4, 7, 9 from the tree rooted at vertex 3 (consisting of vertices 3, 4, 5).
• Squirrel 4 collects candy 6 from the tree rooted at vertex 4 (consisting of vertex 4 only).
• Squirrel 5 collects candy 8 from the tree rooted at vertex 5 (consisting of vertex 5 only).

Note that this is counted as a different way from the following:

• Squirrel 1 collects candy \mathbf{2} from the tree rooted at vertex 1 (consisting of vertices 1, 2, 3, 4, 5).
• Squirrel 2 collects candy \mathbf{3} from the tree rooted at vertex 2 (consisting of vertex 2).
• Squirrel 3 collects candies 4, 7, 9 from the tree rooted at vertex 3 (consisting of vertices 3, 4, 5).
• Squirrel 4 collects candy 6 from the tree rooted at vertex 4 (consisting of vertex 4 only).
• Squirrel 5 collects candy 8 from the tree rooted at vertex 5 (consisting of vertex 5 only).

There are 144 valid ways in total, so output 144 modulo 998244353, that is, 144.

Sample Input 2

2
1
1 1
2 1

Sample Output 2

0

The tree has only two candies across vertices 1 and 2, so it is impossible for both squirrels to collect candies as instructed.
Thus, output 0.

Sample Input 3

3
3 1
1000000000 1 1
1 1 1

Sample Output 3

1755647

Remember to output the count modulo 998244353.

Problem Statement

You are given a sequence of integers A=(A_1,\ldots,A_N). For a tree T with N vertices, define f(T) as follows:

• Let d_i be the degree of vertex i in T. Then, f(T)=\sum_{i=1}^N {d_i}^2 A_i.

Find the minimum possible value of f(T).

The constraints guarantee the answer to be less than 2^{63}.

Constraints

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

Sample Input 1

4
3 2 5 2

Sample Output 1

24

Consider a tree T with an edge connecting vertices 1 and 2, an edge connecting vertices 2 and 4, and an edge connecting vertices 4 and 3.

Then, f(T) = 1^2\times 3 + 2^2\times 2 + 1^2\times 5 + 2^2\times 2 = 24. It can be proven that this is the minimum value of f(T).

Sample Input 2

3
4 3 2

Sample Output 2

15

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

128