Problem Statement

There is a device with a screen that shows a single-digit number, and a button.

When the screen is showing a number k, pressing the button once changes the number on the screen to a_k.

The device currently shows 0. After pressing the button 3 times, what will be shown on the screen?

Constraints

• 0\leq a_i \leq 9
• All values in input are integers.

Sample Input 1

9 0 1 2 3 4 5 6 7 8

Sample Output 1

7

The number on the screen transitions as 0 \rightarrow 9 \rightarrow 8 \rightarrow 7.

Sample Input 2

4 8 8 8 0 8 8 8 8 8

Sample Output 2

4

The number on the screen transitions as 0 \rightarrow 4 \rightarrow 0 \rightarrow 4.

Sample Input 3

0 0 0 0 0 0 0 0 0 0

Sample Output 3

0

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

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

• S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
• T is a string obtained by the procedure described in the problem statement.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

• Type a.
• Try to type b but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Type b.
• Try to type c but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Try to type c but mistakenly type y.
• Press the backspace key, but the character is not deleted.
• Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

• 2 \leq K \leq 10
• 1 \leq A,B \leq 10^5
• A and B are in base-K representation.

Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

5
3
1 2
2 3
3 4
4
1 2
2 3
3 4
4 5
9 1 1 1
1 1 1
1 1
9

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.

Turret i guards castle walls numbered from L_i through R_i.

When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.

What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

10 4
1 6
4 5
5 10
7 10

Sample Output 1

1

If turret 1 is destroyed, no turret guards castle wall 3. Also, if no turrets are destroyed, all castle walls are guarded by some turret. Therefore, output 1.

Sample Input 2

5 2
1 2
3 4

Sample Output 2

0

Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.

Sample Input 3

5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

Sample Output 3

3

Problem Statement

Takahashi is hosting a contest with N players numbered 1 to N. The players will compete for points. Currently, all players have zero points.

Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for i=1,2,\dots,T, the score of player A_i will increase by B_i points at i seconds from now. There will be no other change in the scores.

Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each i=1,2,\dots,T, find the number of different score values among the players' scores at i+0.5 seconds from now.

For example, if the players have 10, 20, 30, and 20 points at some moment, there are three different score values among the players' scores at that moment.

Constraints

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

Sample Input 1

3 4
1 10
3 20
2 10
2 10

Sample Output 1

2
3
2
2

Let S be the sequence of scores of players 1, 2, 3 in this order. Currently, S=\lbrace 0,0,0\rbrace.

• After one second, the score of player 1 increases by 10 points, making S=\lbrace 10,0,0\rbrace. Thus, there are two different score values among the players' scores at 1.5 seconds from now.
• After two seconds, the score of player 3 increases by 20 points, making S=\lbrace 10,0,20\rbrace. Thus, there are three different score values among the players' scores at 2.5 seconds from now.
• After three seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,10,20\rbrace. Therefore, there are two different score values among the players' scores at 3.5 seconds from now.
• After four seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,20,20\rbrace. Therefore, there are two different score values among the players' scores at 4.5 seconds from now.

Sample Input 2

1 3
1 3
1 4
1 3

Sample Output 2

1
1
1

Sample Input 3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

Sample Output 3

2
2
3
3
4
4
5
5
6
5

Problem Statement

Find the number, modulo 998244353, of sequences A = (a_1, \cdots, a_{X_1 + X_2 + X_3}) of length X_1+X_2+X_3 that satisfy all of the following conditions.

• A contains exactly X_1 copies of 1, exactly X_2 copies of 2, and exactly X_3 copies of 3.
• The absolute difference between adjacent elements is at most 1. That is, for every integer i satisfying 1 \leq i \leq X_1+X_2+X_3-1, we have |a_{i+1} - a_i| \leq 1.

Constraints

• 1 \leq X_1, X_2, X_3 \leq 10^6
• All input values are integers.

Sample Input 1

2 2 1

Sample Output 1

9

The sequences satisfying the conditions are the following nine:

• (1, 1, 2, 2, 3)
• (1, 1, 2, 3, 2)
• (1, 2, 1, 2, 3)
• (1, 2, 3, 2, 1)
• (2, 1, 1, 2, 3)
• (2, 3, 2, 1, 1)
• (3, 2, 1, 1, 2)
• (3, 2, 1, 2, 1)
• (3, 2, 2, 1, 1)

Sample Input 2

5 3 4

Sample Output 2

204

Sample Input 3

998244 998353 998107

Sample Output 3

701926019

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