Problem Statement

You are given a 3-character string S, where the first character is a digit, the second character is the character x, and the third character is a digit.

Find the product of the two numbers in S.

Constraints

• S is a 3-character string where the first character is an integer between 1 and 9, inclusive, the second character is the character x, and the third character is an integer between 1 and 9, inclusive.

Sample Input 1

3x8

Sample Output 1

24

From 3 \times 8 = 24, print 24.

Sample Input 2

9x9

Sample Output 2

81

From 9 \times 9 = 81, print 81.

Problem Statement

You are given an integer X not less than 2.

Find the positive integer N such that N! = X.

Here, N! denotes the factorial of N, and it is guaranteed that there is exactly one such N.

Constraints

• 2 \leq X \leq 3 \times 10^{18}
• There is exactly one positive integer N such that N!=X.
• All input values are integers.

Sample Input 1

6

Sample Output 1

3

From 3!=3\times2\times1=6, print 3.

Sample Input 2

2432902008176640000

Sample Output 2

20

From 20!=2432902008176640000, print 20.

Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

• Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
• Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
• Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

• 1 \leq Q \leq 3 \times 10^{5}
• For a query of type 1, 1 \leq l \leq 10^{9}
• For a query of type 2, it is guaranteed that the queue is not empty.
• For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5
10

• 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
• 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
• 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
• 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
• 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
• 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
• 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

3
1 1
2
1 3

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

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

Sample Output 3

20
5

Problem Statement

On the two-dimensional coordinate plane, there is an infinite tiling of 1 \times 1 squares.

Consider drawing a circle of radius R centered at the center of one of these squares. How many of these squares are completely contained inside the circle?

More precisely, find the number of integer pairs (i,j) such that all four points (i+0.5,j+0.5), (i+0.5,j-0.5), (i-0.5,j+0.5), and (i-0.5,j-0.5) are at a distance of at most R from the origin.

Constraints

• 1 \leq R \leq 10^{6}
• All input values are integers.

Sample Input 1

2

Sample Output 1

5

There are a total of five squares completely contained in the circle: the square whose center matches the circle’s center, plus the four squares adjacent to it.

Sample Input 2

4

Sample Output 2

37

Sample Input 3

26

Sample Output 3

2025

Problem Statement

There are N types of products, each having 10^{100} units in stock.

You can buy any non-negative number of units of each product. To buy k units of the i-th product, it costs k^2 P_i yen.

If your total purchase cost is at most M yen, what is the maximum number of units you can buy in total?

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq M \leq 10^{18}
• 1 \leq P_i \leq 2 \times 10^{9}
• All input values are integers.

Sample Input 1

3 9
4 1 9

Sample Output 1

3

If you buy one unit of the 1st product and two units of the 2nd product, the total purchase cost is 1^2 \times 4 + 2^2 \times 1 = 8. It is impossible to buy four or more units in total with a total cost of at most 9 yen, so the answer is 3.

Sample Input 2

10 1000
2 15 6 5 12 1 7 9 17 2

Sample Output 2

53

Problem Statement

Takahashi plans to participate in N AtCoder contests.

In the i-th contest (1 \leq i \leq N), if his rating is between L_i and R_i (inclusive), his rating increases by 1.

You are given Q queries in the following format:

• An integer X is given. Assuming that Takahashi's initial rating is X, determine his rating after participating in all N contests.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N)
• 1 \leq Q \leq 3 \times 10^5
• For each query, 1 \leq X \leq 5 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

6
6
8

For the 1st query, the rating changes as follows:

• In the 1st contest, the rating is between 1 and 5, so it increases by 1, becoming 4.
• In the 2nd contest, the rating is not between 1 and 3, so it remains 4.
• In the 3rd contest, the rating is between 3 and 6, so it increases by 1, becoming 5.
• In the 4th contest, the rating is not between 2 and 4, so it remains 5.
• In the 5th contest, the rating is between 4 and 7, so it increases by 1, becoming 6.

For the 2nd query, the rating increases in the 1st, 2nd, 3rd, and 5th contests, ending at 6.

For the 3rd query, the rating increases in the 1st, 3rd, and 5th contests, ending at 8.

Sample Input 2

10
1 1999
1 1999
1200 2399
1 1999
1 1999
1 1999
2000 500000
1 1999
1 1999
1600 2799
7
1
1995
2000
2399
500000
2799
1000

Sample Output 2

8
2002
2003
2402
500001
2800
1007

Sample Input 3

15
260522 414575
436426 479445
148772 190081
190629 433447
47202 203497
394325 407775
304784 463982
302156 468417
131932 235902
78537 395728
223857 330739
286918 329211
39679 238506
63340 186568
160016 361868
10
287940
296263
224593
101449
336991
390310
323355
177068
11431
8580

Sample Output 3

287946
296269
224599
101453
336997
390315
323363
177075
11431
8580

Problem Statement

You are given a positive even integer N and a prime number P.

For M = N-1, \ldots, \frac{N(N-1)}{2}, solve the following problem.

How many undirected connected simple graphs with N vertices labeled from 1 to N and M edges satisfy this: the number of vertices whose shortest distance from vertex 1 is even is equal to the number of vertices whose shortest distance from vertex 1 is odd? Find this number modulo P.

Constraints

• 2 \leq N \leq 30
• 10^8 \leq P \leq 10^9
• N is even.
• P is prime.
• All input values are integers.

Sample Input 1

4 998244353

Sample Output 1

12 9 3 0

With four vertices and three edges, there are 12 simple connected undirected graphs satisfying the condition.

With four vertices and four edges, there are 9 such graphs.

With four vertices and five edges, there are 3 such graphs.

With four vertices and six edges, there are 0 such graphs.

Sample Input 2

6 924844033

Sample Output 2

810 2100 3060 3030 2230 1210 450 100 10 0 0

Sample Input 3

10 433416647

Sample Output 3

49218750 419111280 321937732 107111441 372416570 351559278 312484809 334285827 317777667 211471846 58741385 422156135 323887465 54923551 121645733 94354149 346849276 72744827 385773306 163421544 351691775 59915863 430096957 166653801 346330874 185052506 245426328 47501118 7422030 899640 79380 4536 126 0 0 0 0

Remember to find the number of such graphs modulo P.