Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

• All input values are integers.
• 1 \le K \le N \le 100
• 1 \le A_i, X \le 100

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).

Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\dots,A_N).

Find the sum of the odd-indexed elements of A. That is, find A_1 + A_3 + A_5 + \dots + A_m, where m is the largest odd number not exceeding N.

Constraints

• 1 \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

7
3 1 4 1 5 9 2

Sample Output 1

14

The sum of the odd-indexed elements of A is A_1+A_3+A_5+A_7=3+4+5+2=14.

Sample Input 2

1
100

Sample Output 2

100

Sample Input 3

14
100 10 1 10 100 10 1 10 100 10 1 10 100 10

Sample Output 3

403

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

• -1000 \leq a,b \leq 1000
• 1 \leq d \leq 360
• All values in input are integers.

Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).

Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.

Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.

Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.

Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

• 1\leq S\leq 10^{100000}
• S is an integer.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

• Type the key 4. It now displays 4.
• Type the key 00. It now displays 400.
• Type the key 0. It now displays 4000.
• Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. Each vertex i\,(1\leq i \leq N) has a weight A_i. Each edge j\,(1\leq j \leq M) connects vertices U_j and V_j bidirectionally and has a weight B_j.

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each i=2,3,\dots,N, solve the following problem:

• Find the minimum weight of a path from vertex 1 to vertex i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j.
• The graph is connected.
• 0 \leq A_i \leq 10^9
• 0 \leq B_j \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

Sample Output 1

4 9

Consider the paths from vertex 1 to vertex 2. The weight of the path 1 \to 2 is A_1 + B_1 + A_2 = 1 + 1 + 2 = 4, and the weight of the path 1 \to 3 \to 2 is A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14. The minimum weight is 4.

Consider the paths from vertex 1 to vertex 3. The weight of the path 1 \to 3 is A_1 + B_2 + A_3 = 1 + 6 + 3 = 10, and the weight of the path 1 \to 2 \to 3 is A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9. The minimum weight is 9.

Sample Input 2

2 1
0 1
1 2 3

Sample Output 2

4

Sample Input 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

Sample Output 3

2832044198 2824130042 4696218483 2805069468

Note that the answers may not fit in a 32-bit integer.

Problem Statement

For a string S consisting of digits from 1 through 9, let f(S) be the string T obtained by the following procedure. (S_i denotes the i-th character of S.)

• Let T be an initially empty string.
• For i=1, 2, \dots, |S| - 1, perform the following operation:
  • Append n copies of S_i to the tail of T, where n is the value when S_{i+1} is interpreted as an integer.

For example, S = 313 yields f(S) = 3111 by the following steps.

• T is initially empty.
• For i=1, we have n = 1. Append one copy of 3 to T, which becomes 3.
• For i=2, we have n = 3. Append three copies of 1 to T, which becomes 3111.
• Terminate the procedure. We obtain T = 3111.

You are given a length-N string S consisting of digits from 1 through 9.
You repeat the following operation until the length of S becomes 1: replace S with f(S).
Find how many times, modulo 998244353, you perform the operation until you complete it. If you will repeat the operation indefinitely, print -1 instead.

Constraints

• 2 \leq N \leq 10^6
• S is a length-N string consisting of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

3
313

Sample Output 1

4

If S = 313, the length of S be comes 1 after four operations.

• We have f(S) = 3111. Replace S with 3111.
• We have f(S) = 311. Replace S with 311.
• We have f(S) = 31. Replace S with 31.
• We have f(S) = 3. Replace S with 3.
• Now that the length of S is 1, terminate the repetition.

Sample Input 2

9
123456789

Sample Output 2

-1

If S = 123456789, you indefinitely repeat the operation. In this case, -1 should be printed.

Sample Input 3

2
11

Sample Output 3

1

Problem Statement

Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.

For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.

Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)

The graph has no edge other than these 2N edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

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

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10