Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

• 1 \leq N \leq 1000
• -10^9 \leq A_i, B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054

• The first line should contain A_1 + B_1 = 3 + 5 = 8.
• The second line should contain A_2 + B_2 = 2 + (-6) = -4.
• The third line should contain A_3 + B_3 = (-5) + 0 = -5.
• The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.

Problem Statement

Takahashi is heading to AtCoder Land. There is a signboard in front of him, and he wants to determine whether it says AtCoder Land.

You are given two strings S and T separated by a space. Determine whether S= AtCoder and T= Land.

Constraints

• S and T are strings consisting of uppercase and lowercase English letters, with lengths between 1 and 10, inclusive.

Sample Input 1

AtCoder Land

Sample Output 1

Yes

S= AtCoder and T= Land.

Sample Input 2

CodeQUEEN Land

Sample Output 2

No

S is not AtCoder.

Sample Input 3

aTcodeR lANd

Sample Output 3

No

Uppercase and lowercase letters are distinguished.

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

Sample Input 2

5 1 5

Sample Output 2

.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....

Sample Input 3

4 4 1

Sample Output 3

.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

• if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
• if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

• if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
• if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

• N and K are integers.
• 1 \le K \le N \le 100
• S is a string of length N consisting of o and x.
• S has at least K o's.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

• The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
• The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
• The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
• The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
• The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
• Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

Problem Statement

There are N versions of a certain OS, numbered 1,2,\dots,N in chronological order.
There are N PCs, and initially the OS version of the i-th PC is i.

Perform Q operations in order. The i-th operation is as follows:

• Upgrade all PCs whose current OS version is X_i or earlier to version Y_i(>X_i). Then, print the number of PCs upgraded in this operation.

Note that for i<Q, the upgrades from the i-th operation are performed before proceeding to the (i+1)-th operation.

Constraints

• All input values are integers.
• 2 \le N \le 10^6
• 1 \le Q \le 2 \times 10^5
• 1 \le X_i < Y_i \le N

Sample Input 1

8 5
2 6
3 5
1 7
5 7
7 8

Sample Output 1

2
1
0
3
7

This input contains five operations.

• Initially, the versions of the eight PCs are 1,2,3,4,5,6,7,8.
• In the first operation, PCs with version 2 or earlier are upgraded to version 6.
  • This operation upgrades two PCs, and the versions of the PCs become 6,6,3,4,5,6,7,8.
• In the second operation, PCs with version 3 or earlier are upgraded to version 5.
  • This operation upgrades one PC, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the third operation, PCs with version 1 or earlier are upgraded to version 7.
  • This operation upgrades zero PCs, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the fourth operation, PCs with version 5 or earlier are upgraded to version 7.
  • This operation upgrades three PCs, and the versions of the PCs become 6,6,7,7,7,6,7,8.
• In the fifth operation, PCs with version 7 or earlier are upgraded to version 8.
  • This operation upgrades seven PCs, and the versions of the PCs become 8,8,8,8,8,8,8,8.

Problem Statement

You are given a positive integer N, and an integer A_{x,y,z} for each triple of integers (x, y, z) such that 1 \leq x, y, z \leq N.

You will be given Q queries in the following format, which must be processed in order.

For the i-th query (1 \leq i \leq Q), you are given a tuple of integers (Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i) such that 1 \leq Lx_i \leq Rx_i \leq N, 1 \leq Ly_i \leq Ry_i \leq N, and 1 \leq Lz_i \leq Rz_i \leq N. Find:

\displaystyle{\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}}.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 2 \times 10^{5}
• 0 \leq A_{x,y,z} \leq 999 (1 \leq x, y, z \leq N)
• 1 \leq Lx_i \leq Rx_i \leq N (1 \leq i \leq Q)
• 1 \leq Ly_i \leq Ry_i \leq N (1 \leq i \leq Q)
• 1 \leq Lz_i \leq Rz_i \leq N (1 \leq i \leq Q)
• All input values are integers.

Sample Input 1

2
1 2
3 4
5 6
7 8
2
1 2 2 2 1 1
2 2 1 2 1 2

Sample Output 1

10
26

For the 1st query, the sought value is A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10. Thus, print 10.

For the 2nd query, the sought value is A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26. Thus, print 26.

Sample Input 2

3
733 857 714
956 208 257
123 719 648
840 881 245
245 112 746
306 942 694
58 870 849
13 208 789
687 906 783
8
3 3 3 3 1 1
1 3 2 3 3 3
2 2 2 3 1 1
1 3 1 1 1 1
2 3 2 3 2 3
1 2 1 1 1 2
3 3 2 2 1 3
1 2 2 3 2 3

Sample Output 2

687
3917
551
1631
5180
3311
1010
4326

Problem Statement

You are given strings A and B of equal length consisting of 0 and 1.

You can perform the following operation on A zero or more times.

• Move the first character of A to the end.

Find the minimum number of operations required to make A=B.
If it is impossible to make A=B no matter how you operate, print -1 instead.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 10000
• A and B are strings consisting of 0 and 1.
• 2 \le |A|=|B| \le 10^6
• For a single input, the sum of |A| does not exceed 10^6.

Sample Input 1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

Sample Output 1

2
-1
0
-1
22

This input contains five test cases.

• For the first test case, A= 1010001 and B= 1000110.
  • By performing the operation on A twice, A becomes 1010001 \rightarrow 0100011 \rightarrow 1000110, which makes A=B.
• For the second test case, no matter how you perform the operation, you cannot change 000 to 111.
• For the third test case, A=B from the beginning.

Problem Statement

There are N plates arranged from left to right as plate 1, plate 2,\ldots, plate N. Initially, plate i\ (1\le i\le N) contains A _ i stones.

You will perform M operations on these plates. In the i-th operation (1\le i\le M), two integers L _ i and R _ i are given, and the following operations are performed in order:

• Remove all stones from the R _ i-L _ i+1 plates: plate L _ i, plate L _ i+1,\ldots, plate R _ i.
• Uniformly randomly choose an integer between L _ i and R _ i, inclusive, and let it be x.
• Place all the removed stones on plate x.

For i=1,2,\ldots,N, find the expected number, modulo 998244353, of stones placed on plate i when all M operations are completed.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le M\le2\times10 ^ 5
• 0\le A _ i\lt998244353\ (1\le i\le N)
• 1\le L _ i\le R _ i\le N\ (1\le i\le M)
• All input values are integers.

Sample Input 1

7 4
30 10 40 10 50 90 20
4 6
5 7
1 6
3 7

Sample Output 1

35 35 36 36 36 36 36 

For example, the operations proceed as follows:

• In the first operation, 4 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 30, 10, 40, 150, 0, 0, 20, respectively.
• In the second operation, 6 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 30, 10, 40, 150, 0, 20, 0, respectively.
• In the third operation, 2 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 0, 250, 0, 0, 0, 0, 0, respectively.
• In the fourth operation, 3 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 0, 250, 0, 0, 0, 0, 0, respectively.

When all operations are completed, the expected number of stones on plates 1, 2 is 35, and the expected number of stones on plates 3, 4, 5, 6, 7 is 36, so output 35 35 36 36 36 36 36.

Sample Input 2

2 1
0 1
1 2

Sample Output 2

499122177 499122177 

Note that you need to find the expected value modulo 998244353.

When all operations are completed, for both plates, there is a \dfrac12 probability that one stone is placed, and a \dfrac12 probability that no stone is placed. Therefore, the expected number of stones placed is \dfrac12. We have 499122177\times2\equiv1\pmod{998244353}, so output 499122177 499122177.

Sample Input 3

15 10
61477244 450343304 812961384 836482955 280670539 405068748 318805088 304825858 518212597 316347783 589272551 505875419 944071276 364842194 5376942
2 11
5 9
8 15
6 7
6 8
1 2
1 10
4 9
12 15
6 11

Sample Output 3

449356308 449356308 449356308 449356308 449356308 648148154 648148154 648148154 648148154 648148154 648148154 643863031 643863031 643863031 643863031