Problem Statement

AtCoder Grand Contest (AGC), a regularly held contest with a world authority, has been held 54 times.

Just like the 230-th ABC ― the one you are in now ― is called ABC230, the N-th AGC is initially named with a zero-padded 3-digit number N. (The 1-st AGC is AGC001, the 2-nd AGC is AGC002, ...)

However, the latest 54-th AGC is called AGC055, where the number is one greater than 54. Because AGC042 is canceled and missing due to the social situation, the 42-th and subsequent contests are assigned numbers that are one greater than the numbers of contests held. (See also the explanations at Sample Inputs and Outputs.)

Here is the problem: given an integer N, print the name of the N-th AGC in the format AGCXXX, where XXX is the zero-padded 3-digit number.

Constraints

• 1 \leq N \leq 54
• N is an integer.

Sample Input 1

42

Sample Output 1

AGC043

As explained in Problem Statement, the 42-th and subsequent AGCs are assigned numbers that are one greater than the numbers of contests.
Thus, the 42-th AGC is named AGC043.

Sample Input 2

19

Sample Output 2

AGC019

The 41-th and preceding AGCs are assigned numbers that are equal to the numbers of contests.
Thus, the answer is AGC019.

Sample Input 3

1

Sample Output 3

AGC001

As mentioned in Problem Statement, the 1-st AGC is named AGC001.
Be sure to pad the number with zeros into a 3-digit number.

Sample Input 4

50

Sample Output 4

AGC051

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

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

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

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

Problem Statement

In a town divided into a grid with N rows and 10^9 columns, there are N walls, numbered 1 to N.
Wall i ranges from the L_i-th column to the R_i-th column from the left in the i-th row from the top. (See also the figure at Sample Input and Output 1.)

Takahashi has decided to destroy all N walls.
With his superhuman strength, his one punch can damage consecutive D columns at once.

• More formally, he can choose an integer x between 1 and 10^9 - D + 1 (inclusive) to damage all walls that exist (or partly exist) in the x-th through (x + D - 1)-th columns and are not yet destroyed.

When a part of a wall is damaged, that whole wall will be destroyed by the impact of the punch.
(See also the figure at Sample Input and Output 1.)

At least how many times does Takahashi need to punch to destroy all walls?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^9
• 1 \leq L_i \leq R_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
1 2
4 7
5 9

Sample Output 1

2

The figure below describes the arrangements of walls in Sample Input 1.

He can destroy all walls with two punches, such as the following. (Below, \lbrack a, b \rbrack denotes the range from the a-th through b-th columns.)

• First, punch \lbrack 2, 4 \rbrack. The walls existing in \lbrack 2, 4 \rbrack ― Walls 1 and 2 ― are damaged and destroyed.
• Second, punch \lbrack 5, 7 \rbrack. The wall existing in \lbrack 5, 7 \rbrack ― Wall 3 ― is damaged and destroyed.

It is also possible to destroy all walls with two punches in this way:

• First, punch \lbrack 7, 9 \rbrack to destroy Walls 2 and 3.
• Second, punch \lbrack 1, 3 \rbrack to destroy Wall 1.

Sample Input 2

3 3
1 2
4 7
4 9

Sample Output 2

1

The difference from Sample Input/Output 1 is that Wall 3 now covers \lbrack 4, 9 \rbrack, not \lbrack 5, 9 \rbrack.
In this case, he can punch \lbrack 2, 4 \rbrack to destroy all walls with one punch.

Sample Input 3

5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

Sample Output 3

3

Problem Statement

Given is a positive integer N. Find the value \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right].

Here, for a real number x, [x] denotes the largest integer not exceeding x.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

3

Sample Output 1

5

We have \left[ \frac{3}{1} \right]+\left[ \frac{3}{2} \right]+\left[ \frac{3}{3} \right]=3+1+1=5.

Sample Input 2

10000000000

Sample Output 2

231802823220

Note that the input and output may not fit into a 32-bit integer type.

Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
1 -1 1

Sample Output 1

4

The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

Sample Output 2

321

Problem Statement

Given is a permutation P=(P_1,P_2,\ldots,P_N) of the integers from 1 through N.

Find the number of pairs of integers (i,j) such that 1\leq i\leq j\leq N satisfying GCD(i,j)\neq 1 and GCD(P_i,P_j)\neq 1.
Here, for positive integers x and y, GCD(x,y) denotes the greatest common divisor of x and y.

Constraints

• 1 \leq N \leq 2\times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

6
5 1 3 2 4 6

Sample Output 1

6

Six pairs (3,3), (3,6), (4,4), (4,6), (5,5), (6,6) satisfy the condition, so 6 should be printed.

Sample Input 2

12
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 2

32

Problem Statement

Takahashi won a claw machine competition and was awarded "all-you-can-stuff" gold blocks.
There are unlimited numbers of blocks weighing w_1, w_2, \dots, w_K kilograms each, and an unlimited number of bags weighing 1 kilogram each to stuff them.

Takahashi can bring home one non-empty bag.
A bag can contain zero or more other non-empty bags and zero or more gold blocks.

After arranging a truck with a load capacity of W kilograms, he gets interested in the number of ways to stuff gold blocks and bring home a bag that weighs w kilograms in total for w = 2, 3, \dots, W.
Find the number, modulo 998244353, of possible states of the bag for each w = 2, 3, \dots, W. Here,

• two gold blocks are said to be the same when their weights are the same;
• two bags are said to be in the same state when the two multisets whose elements are the bags and gold blocks in the two bags are the same.

Constraints

• 2 \leq W \leq 2.5 \times 10^5
• 1 \leq K \leq W
• 1 \leq w_i \leq W (1 \leq i \leq K)
• i \neq j \to w_i \neq w_j (1 \leq i,j \leq K)
• All values in input are integers.

Sample Input 1

4 1
1

Sample Output 1

1
2
4

The figure below enumerates the possible states of the bag for w = 2, 3, 4. (A circle represents a bag.)

Sample Input 2

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

Sample Output 2

1
3
7
18
45
121
325
904
2546