Problem Statement

AtCoder Beginner Contest usually starts at 21:00 JST and lasts for 100 minutes.

You are given an integer K between 0 and 100 (inclusive). Print the time K minutes after 21:00 in the HH:MM format, where HH denotes the hour on the 24-hour clock and MM denotes the minute. If the hour or the minute has just one digit, append a 0 to the beginning to represent it as a 2-digit integer.

Constraints

• K is an integer between 0 and 100 (inclusive).

Sample Input 1

63

Sample Output 1

22:03

63 minutes after 21:00, it will be 22:03, so 22:03 should be printed.

The following outputs would be judged incorrect:

• 10:03
• 22:3

Sample Input 2

45

Sample Output 2

21:45

Sample Input 3

100

Sample Output 3

22:40

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
• (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• 1 \le N \le 10
• 1 \le A_{i,j} \le 9
• All values in input are integers.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

We have a video game consisting of N stages. The i-th stage (1 \leq i \leq N) is composed of a movie lasting A_i minutes and gameplay lasting B_i minutes.

To clear the i-th stage for the first time, one must watch the movie and do the gameplay for that stage. For the second and subsequent times, one may skip the movie and do just the gameplay.

In the beginning, only the 1-st stage is unlocked, and clearing the i-th stage (1 \leq i \leq N - 1) unlocks the (i+1)-th stage.

Find the shortest time needed to clear a stage X times in total. Here, if the same stage is cleared multiple times, all of them count.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9 \, (1 \leq i \leq N)
• 1 \leq X \leq 10^9
• All values in input are integers.

Sample Input 1

3 4
3 4
2 3
4 2

Sample Output 1

18

Here is one way to clear a stage 4 times in 18 minutes:

• Clear Stage 1. It takes A_1 + B_1 = 7 minutes.
• Clear Stage 2. It takes A_2 + B_2 = 5 minutes.
• Clear Stage 2 again. It takes B_2= 3 minutes.
• Clear Stage 2 again. It takes B_2= 3 minutes.

It is impossible to clear a stage 4 times within 17 minutes.

Sample Input 2

10 1000000000
3 3
1 6
4 7
1 8
5 7
9 9
2 4
6 4
5 1
3 1

Sample Output 2

1000000076

Problem Statement

10^{100} potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence W = (W_0, \dots, W_{N-1}) of length N: the weight of the i-th potato coming is W_{(i-1) \bmod N}, where (i-1) \bmod N denotes the remainder when i - 1 is divided by N.

Takahashi will prepare an empty box and then pack the potatoes in order, as follows.

• Pack the incoming potato into the box. If the total weight of the potatoes in the box is now X or greater, seal that box and prepare a new empty box.

You are given Q queries. In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the number of potatoes in the K_i-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least K_i sealed boxes.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq X \leq 10^9
• 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)
• 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

3 2 5
3 4 1
1
2

Sample Output 1

2
3

Before sealing the 2-nd box, Takahashi will do the following:

• Prepare an empty box.
• Pack the 1-st potato into the box. Now, the total weight of potatoes in the box is 3.
• Pack the 2-nd potato into the box. Now, the total weight of potatoes in the box is 3 + 4 = 7, which is not less than X = 5, so seal this box.
• Prepare a new empty box.
• Pack the 3-rd potato into the box. Now, the total weight of potatoes in the box is 1.
• Pack the 4-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 = 4.
• Pack the 5-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 + 4 = 8, which is not less than X = 5, so seal this box.

The 1-st box sealed contains 2 potatoes, and the 2-nd box sealed contains 3 potatoes.

Sample Input 2

10 5 20
5 8 5 9 8 7 4 4 8 2
1
1000
1000000
1000000000
1000000000000

Sample Output 2

4
5
5
5
5

Problem Statement

The roads in the Kingdom of AtCoder, which lies on the xy-plane, are the lines x=n and y=n for all integers n. Among them, the lines x=Bn and y=Bn for all integers n are main roads.

When Takahashi is at (x,y), he can move to (x,y-1), (x,y+1), (x+1,y), or (x-1,y). Each move takes 1 second along a main road and K seconds otherwise.

Find the minimum number of seconds Takahashi needs to get from (S_x, S_y) to (G_x, G_y).

You will have T test cases to solve.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le B,K \le 10^9
• 0 \le S_x,S_y,G_x,G_y \le 10^9
• All values in input are integers.

Sample Input 1

4
3 4 2 2 4 4
5 6 2 3 2 3
1 1000000000 0 0 1000000000 1000000000
1000000000 1000000000 500000000 500000000 1000000000 1000000000

Sample Output 1

10
0
2000000000
500000000500000000

For the 1-st test case, he can go from (2,2) to (2,3) in 4 seconds, from (2,3) to (4,3) in 2 seconds, and from (4,3) to (4,4) in 4 seconds to get from (2,2) to (4,4) in 10 seconds. It is impossible to get there in less than 10 seconds, so the answer is 10.
For the 2-nd test case, he is already at (G_x, G_y) in the beginning, so the answer is 0.

Sample Input 2

10
928184439 674654465 203937094 186855052 851783856 805293696
55480262 448852233 823161539 786348805 550018803 322680316
891870741 235679524 32164572 497841190 620600021 96487871
321502816 428964257 499656016 521484999 717623189 824784374
144040837 680268887 76238777 371138006 350230937 78690135
768922620 799628518 403830696 60449731 218880692 88319939
482031503 121412614 472330444 284479575 949635609 427232765
389524418 132987043 656496997 678732442 23028233 488463974
857778764 629964237 714551548 739330018 579247790 874251485
461612428 535402609 555160129 833592114 44418273 287363785

Sample Output 2

177606591118701316
6205925075792263
30320747646118343
84136273267803188
83764071874751489
118960470930399064
2929499649126153
16403238161749820
84995699148879437
71771264361119335

Problem Statement

You are given a simple undirected graph G with N vertices.

G is given as the N \times N adjacency matrix A. That is, there is an edge between Vertices i and j if A_{i,j} is 1, and there is not if A_{i,j} is 0.

Find the number of triples of integers (i,j,k) satisfying 1 \le i < j < k \le N such that there is an edge between Vertices i and j, an edge between Vertices j and k, and an edge between Vertices i and k.

Constraints

• 3 \le N \le 3000
• A is the adjacency matrix of a simple undirected graph G.
• All values in input are integers.

Sample Input 1

4
0011
0011
1101
1110

Sample Output 1

2

(i,j,k)=(1,3,4),(2,3,4) satisfy the condition.

(i,j,k)=(1,2,3) does not satisfy the condition, because there is no edge between Vertices 1 and 2.

Thus, the answer is 2.

Sample Input 2

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

Sample Output 2

0

Problem Statement

Find the number, modulo 998244353, of sequences X that satisfy all of the following conditions.

• Every term in X is a positive odd number.
• The sum of the terms in X is S.
• The prefix sums of X contain none of A_1, \dots, A_N. Formally, if we define Y_i = X_1 + \dots + X_i for each i, then Y_i \neq A_j holds for all integers i and j such that 1 \leq i \leq |X| and 1 \leq j \leq N.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \lt S \leq 10^{18}
• All values in input are integers.

Sample Input 1

3 7
2 4 5

Sample Output 1

3

The following three sequences satisfy the conditions.

• (1, 5, 1)
• (3, 3, 1)
• (7)

Sample Input 2

5 60
10 20 30 40 50

Sample Output 2

37634180

Sample Input 3

10 1000000000000000000
1 2 4 8 16 32 64 128 256 512

Sample Output 3

75326268