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

There are 12 strings S_1, S_2, \ldots, S_{12} consisting of lowercase English letters.

Find how many integers i (1 \leq i \leq 12) satisfy that the length of S_i is i.

Constraints

• Each S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters. (1 \leq i \leq 12)

Sample Input 1

january
february
march
april
may
june
july
august
september
october
november
december

Sample Output 1

1

There is only one integer i such that the length of S_i is i: 9. Thus, print 1.

Sample Input 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

Sample Output 2

2

There are two integers i such that the length of S_i is i: 4 and 8. Thus, print 2.

Problem Statement

There is a calculator with the buttons 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
When a string x is displayed on this calculator and you press a button b, the resulting displayed string becomes the string x with b appended to its end.

Initially, the calculator displays the empty string (a string of length 0).
Find the minimum number of button presses required to display the string S on this calculator.

Constraints

• S is a string of length at least 1 and at most 1000, consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• The first character of S is not 0.

Sample Input 1

1000000007

Sample Output 1

6

To display 1000000007, you can press the buttons 1, 00, 00, 00, 00, 7 in this order. The total number of button presses is 6, and this is the minimum possible.

Sample Input 2

998244353

Sample Output 2

9

Sample Input 3

32000

Sample Output 3

4

Problem Statement

There are N people, called Person 1, Person 2, \ldots, Person N.

The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.

How many generations away from Person N is Person 1?

Constraints

• 2 \le N \le 50
• 1 \le P_i < i(2 \le i \le N)
• All values in input are integers.

Sample Input 1

3
1 2

Sample Output 1

2

Person 2 is a parent of Person 3, and thus is one generation away from Person 3.

Person 1 is a parent of Person 2, and thus is two generations away from Person 3.

Therefore, the answer is 2.

Sample Input 2

10
1 2 3 4 5 6 7 8 9

Sample Output 2

9

Problem Statement

Takahashi is playing a game. This game has N skills numbered 1 through N.

You are given N pairs of integers (A_1,B_1), \dots,(A_N,B_N).
If (A_i,B_i)=(0,0), then Takahashi has already learned skill i.
Otherwise, Takahashi can learn skill i if and only if at least one of skills A_i and B_i has already been learned.

Including the skills already learned, find the number of skills that Takahashi can ultimately learn.

Constraints

• 1\leq N \leq 2\times 10^5
• (A_i,B_i)=(0,0) or 1\leq A_i,B_i \leq N
• All input values are integers.

Sample Input 1

6
0 0
1 3
3 2
5 5
4 6
6 4

Sample Output 1

3

At first, Takahashi has already learned skill 1. Because skill 1 has been learned, skill 2 can be learned, and learning skill 2 enables learning skill 3. Since it is impossible to learn skills 4,5,6, the answer is 3.

Sample Input 2

4
0 0
0 0
0 0
0 0

Sample Output 2

4

Problem Statement

You are given an integer sequence of length N, A=(A_1,A_2,\ldots,A_N).
Find the number of triples of integers (i,j,k) satisfying 1\leq i<j<k\leq N that satisfy the following condition:

Exactly two distinct values are contained in A_i,A_j,A_k. That is, two of A_i,A_j,A_k are equal, and the remaining one is different.

Constraints

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

Sample Input 1

5
3 2 5 2 2

Sample Output 1

6

For example, (i,j,k)=(1,2,4) satisfies the condition because exactly two distinct values, 2 and 3, are contained in A_1=3, A_2=2, and A_4=2.
Including this, the six triples (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) satisfy the condition.
Therefore, print 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

There may be no triples that satisfy the condition.

Problem Statement

A polyomino is a puzzle piece in the shape of a connected polygon made by connecting several squares by their edges.

There is a grid with four rows and four columns, and three polyominoes that fit within the grid.
The shape of the i-th polyomino is represented by 16 characters P_{i,j,k} (1 \leq j, k \leq 4). They describe the state of the grid when the i-th polyomino is placed on it. If P_{i, j, k} is #, the square at the j-th row from the top and k-th column from the left is occupied by the polyomino; if it is ., the square is not occupied. (Refer to the figures at Sample Input/Output 1.)

You want to fill the grid with all three polyominoes so that all of the following conditions are satisfied.

• All squares of the grid are covered by the polyominoes.
• The polyominoes must not overlap each other.
• The polyominoes must not stick out of the grid.
• The polyominoes may be freely translated and rotated but may not be flipped over.

Can the grid be filled with the polyominoes to satisfy these conditions?

Constraints

• P_{i, j, k} is # or ..
• The given polyominoes are connected. In other words, the squares that make up a polyomino can be reached from each other by following only the squares up, down, left, and right.
• The given polyominoes are not empty.

Sample Input 1

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

Sample Output 1

Yes

The figure below shows the shapes of the polyominoes corresponding to Sample Input 1.

In this case, you can fill the grid with them to satisfy the conditions in the problem statement by placing them as shown in the figure below.

Thus, the answer is Yes.

Sample Input 2

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

Sample Output 2

Yes

As in the first polyomino in Sample Input 2, a polyomino may be in the shape of a polygon with a hole.

Sample Input 3

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

Sample Output 3

No

Note that the polyominoes may not be flipped over when filling the grid.

Sample Input 4

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

Sample Output 4

No

Sample Input 5

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

Sample Output 5

No

Sample Input 6

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

Sample Output 6

Yes

Problem Statement

There are N large bowls arranged in a row, numbered 0,1,\dots,N-1 from the left.
For each bowl i ( 1\le i\le N-1 ), an integer C_i is written on it, and initially it contains A_i beans.
Bowl 0 has no integer written on it and initially contains no beans.

Consider repeating the following operation any number of times:

• Choose one bowl i (1\le i\le N-1) and take out one or more beans from it.
• Distribute the taken beans freely among bowls i-C_i,i-C_i+1,\dots,i-1.
  • Formally, when you take out k beans, you must put a total of k beans into bowls i-C_i,i-C_i+1,\dots,i-1, and you may choose how many beans go into each bowl.

Find the minimum number of operations required to put all the beans into bowl 0.

Constraints

• All input values are integers.
• 2 \le N \le 2000
• 1 \le C_i \le i
• 0 \le A_i \le 1
• \displaystyle \sum_{i=1}^{N-1} A_i > 0

Sample Input 1

5
1 1 2 1
1 0 0 1

Sample Output 1

3

For example, the following three operations put all the beans into bowl 0, and this is the minimum:

• Choose bowl 4. It has 1 bean.
  • Put 1 bean into bowl 3.
• Choose bowl 3. It has 1 bean.
  • Put 1 bean into bowl 1.
• Choose bowl 1. It has 2 beans.
  • Put 2 beans into bowl 0.

Sample Input 2

6
1 2 1 3 1
1 1 0 1 1

Sample Output 2

4

For example, the following four operations put all the beans into bowl 0, and this is the minimum:

• Choose bowl 5. It has 1 bean.
  • Put 1 bean into bowl 4.
• Choose bowl 4. It has 2 beans.
  • Put 1 bean into bowl 1.
  • Put 1 bean into bowl 2.
• Choose bowl 1. It has 2 beans.
  • Put 2 beans into bowl 0.
• Choose bowl 2. It has 2 beans.
  • Put 2 beans into bowl 0.

Sample Input 3

16
1 1 1 2 5 1 1 3 4 1 4 3 1 1 2
1 0 0 0 1 0 0 1 1 0 0 0 0 0 1

Sample Output 3

7

Problem Statement

You are given strings S and T of length N each, consisting of lowercase English letters.

For a string X and an integer i, let f(X,i) be the string obtained by performing on X the following operation i times:

• Remove the first character of X and append the same character to the end of X.

Find the number of integer pairs (i,j) satisfying 0 \le i,j \le N-1 such that f(S,i) is lexicographically smaller than or equal to f(T,j).

Constraints

• 1 \le N \le 2 \times 10^5
• S and T are strings of length N each, consisting of lowercase English letters.
• N is an integer.

Sample Input 1

3
adb
cab

Sample Output 1

4

There are 4 pairs of (i, j) satisfying the conditions: (0,0),(0,2),(2,0), and (2,2).

(i,j)=(1,2) does not satisfy the conditions because f(S,i)=dba and f(T,j)=bca.

Sample Input 2

10
wsiuhwijsl
pwqoketvun

Sample Output 2

56