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 sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

• 2000 \leq Y \leq 3000
• Y is an integer.

Sample Input 1

2022

Sample Output 1

2022

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.

Sample Input 2

2023

Sample Output 2

2026

Sample Input 3

3000

Sample Output 3

3002

Problem Statement

In the xy-plane, there are three points A(x_A, y_A), B(x_B, y_B), and C(x_C, y_C) that are not collinear. Determine whether the triangle ABC is a right triangle.

Constraints

• -1000 \leq x_A, y_A, x_B, y_B, x_C, y_C \leq 1000
• The three points A, B, and C are not collinear.
• All input values are integers.

Sample Input 1

0 0
4 0
0 3

Sample Output 1

Yes

The triangle ABC is a right triangle.

Sample Input 2

-4 3
2 1
3 4

Sample Output 2

Yes

The triangle ABC is a right triangle.

Sample Input 3

2 4
-3 2
1 -2

Sample Output 3

No

The triangle ABC is not a right triangle.

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

• X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• H and W are integers.
• C_{i, j} is . or #.

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Problem Statement

You are given a string S of length N. You are also given Q queries, which you should process in order.

The i-th query is as follows:

• Given an integer X_i and a character C_i, replace the X_i-th character of S with C_i. Then, print the number of times the string ABC appears as a substring in S.

Here, a substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• S is a string of length N consisting of uppercase English letters.
• 1 \le X_i \le N
• C_i is an uppercase English letter.

Sample Input 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

Sample Output 1

2
1
1
0

After processing each query, S becomes as follows.

• After the first query: S= ABCBABC. In this string, ABC appears twice as a substring.
• After the second query: S= ABABABC. In this string, ABC appears once as a substring.
• After the third query: S= ABABCBC. In this string, ABC appears once as a substring.
• After the fourth query: S= ABAGCBC. In this string, ABC appears zero times as a substring.

Sample Input 2

3 3
ABC
1 A
2 B
3 C

Sample Output 2

1
1
1

There are cases where S does not change through processing a query.

Sample Input 3

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

Sample Output 3

0
0
0
0
1
1
2
2
1
1

Problem Statement

There is an empty integer sequence A=(). You are given Q queries, and you need to process them in the given order. There are two types of queries:

• Type 1: Given in the format 1 c x. Add c copies of x to the end of A.
• Type 2: Given in the format 2 k. Remove the first k elements from A and output the sum of the removed k integers. It is guaranteed that k is at most the length of A at that time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• In type 1 queries, 1 \leq c \leq 10^{9}.
• In type 1 queries, 1 \leq x \leq 10^{9}.
• In type 2 queries, letting n be the length of A at that time, 1 \leq k \leq \min(10^{9},n).
• All input values are integers.

Sample Input 1

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

Sample Output 1

11
19

• 1st query: Add 2 copies of 3 to the end of A. Then, A=(3,3).
• 2nd query: Add 4 copies of 5 to the end of A. Then, A=(3,3,5,5,5,5).
• 3rd query: Remove the first 3 elements from A. Then, the sum of the removed 3 integers is 3+3+5=11, so output 11. After removal, A=(5,5,5).
• 4th query: Add 6 copies of 2 to the end of A. Then, A=(5,5,5,2,2,2,2,2,2).
• 5th query: Remove the first 5 elements from A. Then, the sum of the removed 5 integers is 5+5+5+2+2=19, so output 19. After removal, A=(2,2,2,2).

Sample Input 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

Sample Output 2

990
804
3024

Sample Input 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

Sample Output 3

16430766442004320
155640513381884866
149721462357295680

Problem Statement

Takahashi is about to go buy eel at a fish shop.

The town where he lives is divided into a grid of H rows and W columns. Each cell is either a road or a wall.
Let us denote the cell at the i-th row from the top (1\leq i \leq H) and the j-th column from the left (1\leq j \leq W) as cell (i,j).
Information about each cell is given by H strings S_1,S_2,\ldots,S_H, each of length W. Specifically, if the j-th character of S_i (1\leq i \leq H,1\leq j\leq W) is ., cell (i,j) is a road; if it is #, cell (i,j) is a wall.

He can repeatedly perform the following two types of actions in any order:

• Move to an adjacent cell (up, down, left, or right) that is within the town and is a road.
• Choose one of the four directions (up, down, left, or right) and perform a front kick in that direction.
  When he performs a front kick, for each of the cells at most 2 steps away in that direction from the cell he is currently in, if that cell is a wall, it becomes a road.
  If some of the cells at most 2 steps away are outside the town, a front kick can still be performed, but anything outside the town does not change.

He starts in cell (A,B), and he wants to move to the fish shop in cell (C,D).
It is guaranteed that both the cell where he starts and the cell with the fish shop are roads.
Find the minimum number of front kicks he needs in order to reach the fish shop.

Constraints

• 1\leq H\leq 1000
• 1\leq W\leq 1000
• Each S_i is a string of length W consisting of . and #.
• 1\leq A,C\leq H
• 1\leq B,D\leq W
• (A,B)\neq (C,D)
• H, W, A, B, C, and D are integers.
• The cell where Takahashi starts and the cell with the fish shop are roads.

Sample Input 1

10 10
..........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
.##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
1 1 7 1

Sample Output 1

1

Takahashi starts in cell (1,1).
By repeatedly moving to adjacent road cells, he can reach cell (7,4).
If he performs a front kick to the left from cell (7,4), cells (7,3) and (7,2) turn from walls to roads.
Then, by continuing to move through road cells (including those that have become roads), he can reach the fish shop in cell (7,1).

In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.

Sample Input 2

2 2
.#
#.
1 1 2 2

Sample Output 2

1

Takahashi starts in cell (1,1).
When he performs a front kick to the right, cell (1,2) turns from a wall to a road.
The cell two steps to the right of (1,1) is outside the town, so it does not change.
Then, he can move to cell (1,2) and then to the fish shop in cell (2,2).

In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.

Sample Input 3

1 3
.#.
1 1 1 3

Sample Output 3

1

When performing a front kick, it is fine if the fish shop’s cell is within the cells that could be turned into a road. Specifically, the fish shop’s cell is a road from the beginning, so it remains unchanged; particularly, the shop is not destroyed by the front kick.

Sample Input 4

20 20
####################
##...##....###...###
#.....#.....#.....##
#..#..#..#..#..#..##
#..#..#....##..#####
#.....#.....#..#####
#.....#..#..#..#..##
#..#..#.....#.....##
#..#..#....###...###
####################
####################
##..#..##...###...##
##..#..#.....#.....#
##..#..#..#..#..#..#
##..#..#..#..#..#..#
##.....#..#..#..#..#
###....#..#..#..#..#
#####..#.....#.....#
#####..##...###...##
####################
3 3 18 18

Sample Output 4

3

Problem Statement

You are given N points in the coordinate plane. For each 1\leq i\leq N, the i-th point is at the coordinates (X_i, Y_i).

Find the number of lines in the plane that pass K or more of the N points.
If there are infinitely many such lines, print Infinity.

Constraints

• 1 \leq K \leq N \leq 300
• \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
• X_i\neq X_j or Y_i\neq Y_j, if i\neq j.
• All values in input are integers.

Sample Input 1

5 2
0 0
1 0
0 1
-1 0
0 -1

Sample Output 1

6

The six lines x=0, y=0, y=x\pm 1, and y=-x\pm 1 satisfy the requirement.
For example, x=0 passes the first, third, and fifth points.

Thus, 6 should be printed.

Sample Input 2

1 1
0 0

Sample Output 2

Infinity

Infinitely many lines pass the origin.

Thus, Infinity should be printed.

Problem Statement

For a string X of length n, let f(X,k) denote the string obtained by repeating k times the string X, and g(X,k) denote the string obtained by repeating k times the first character, the second character, \dots, the n-th character of X, in this order. For example, if X= abc, then f(X,2)= abcabc, and g(X,3)= aaabbbccc. Also, for any string X, both f(X,0) and g(X,0) are empty strings.

You are given a positive integer N and strings S and T. Find the largest non-negative integer k such that g(T,k) is a (not necessarily contiguous) subsequence of f(S,N). Note that g(T,0) is always a subsequence of f(S,N) by definition.

Constraints

• N is an integer.
• 1\leq N\leq 10^{12}
• S and T are strings consisting of lowercase English letters with lengths between 1 and 10^5, inclusive.

Sample Input 1

3
abc
ab

Sample Output 1

2

We have f(S,3)= abcabcabc. g(T,2)= aabb is a subsequence of f(S,3), but g(T,3)= aaabbb is not, so print 2.

Sample Input 2

3
abc
arc

Sample Output 2

0

Sample Input 3

1000000000000
kzazkakxkk
azakxk

Sample Output 3

344827586207