Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

• 1 \leq X,Y \leq 100
• X \neq Y
• All input values are integers.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

Problem Statement

The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.

Given an integer N between 97 and 122, print the letter whose ASCII value is N.

Constraints

• N is an integer between 97 and 122 (inclusive).

Sample Input 1

97

Sample Output 1

a

97 is the ASCII value of a.

Sample Input 2

122

Sample Output 2

z

Problem Statement

There is a grid with H rows and W columns; initially, all cells are painted white. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

This grid is considered to be toroidal. That is, (i, 1) is to the right of (i, W) for each 1 \leq i \leq H, and (1, j) is below (H, j) for each 1 \leq j \leq W.

Takahashi is at (1, 1) and facing upwards. Print the color of each cell in the grid after Takahashi repeats the following operation N times.

• If the current cell is painted white, repaint it black, rotate 90^\circ clockwise, and move forward one cell in the direction he is facing. Otherwise, repaint the current cell white, rotate 90^\circ counterclockwise, and move forward one cell in the direction he is facing.

Constraints

• 1 \leq H, W \leq 100
• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

3 4 5

Sample Output 1

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

The cells of the grid change as follows due to the operations:

....   #...   ##..   ##..   ##..   .#..
.... → .... → .... → .#.. → ##.. → ##..
....   ....   ....   ....   ....   ....

Sample Input 2

2 2 1000

Sample Output 2

..
..

Sample Input 3

10 10 10

Sample Output 3

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

Problem Statement

In AtCoder City, N types of garbage are collected regularly. The i-th type of garbage (i=1,2,\dots,N) is collected on days when the date modulo q_i equals r_i.

Answer Q queries. In the j-th query (j=1,2,\dots,Q), given that the t_j-th type of garbage is put out on day d_j, answer the next day on which it will be collected.

Here, if the i-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

• 1 \leq N \leq 100
• 0 \leq r_i < q_i \leq 10^9
• 1 \leq Q \leq 100
• 1 \leq t_j \leq N
• 1 \leq d_j \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
3
10
17
10

• 1st query: The 1st type of garbage is collected on day 3 for the first time after day 1.
• 2nd query: The 1st type of garbage is collected on day 3 for the first time after day 3.
• 3rd query: The 1st type of garbage is collected on day 10 for the first time after day 4.

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

• There exists a pair of positive integers (a,b) such that X = 2^a \times b^2.

For example, 400 is a good integer because 400 = 2^2 \times 10^2.

Given a positive integer N, find the number of good integers between 1 and N, inclusive.

Constraints

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

Sample Input 1

20

Sample Output 1

5

There are five good integers between 1 and 20: 2, 4, 8, 16, and 18.
Thus, print 5.

Sample Input 2

400

Sample Output 2

24

Sample Input 3

1234567890

Sample Output 3

42413

Note that the input might not fit in a 32-bit integer type.

Problem Statement

This problem is a simplified version of Problem F.

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).

Constraints

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

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

• For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
• For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
• For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
• For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.

Therefore, the maximum sum is 5 for i=2,3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

8

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

AtCoder in another world holds 10 types of contests called AAC, ..., AJC. There will be N contests from now on.
The types of these N contests are given to you as a string S: if the i-th character of S is x, the i-th contest will be AxC.
AtCoDeer will choose and participate in one or more contests from the N so that the following condition is satisfied.

• In the sequence of contests he will participate in, the contests of the same type are consecutive.
  • Formally, when AtCoDeer participates in x contests and the i-th of them is of type T_i, for every triple of integers (i,j,k) such that 1 \le i < j < k \le x, T_i=T_j must hold if T_i=T_k.

Find the number of ways for AtCoDeer to choose contests to participate in, modulo 998244353.
Two ways to choose contests are considered different when there is a contest c such that AtCoDeer participates in c in one way but not in the other.

Constraints

• 1 \le N \le 1000
• |S|=N
• S consists of uppercase English letters from A through J.

Sample Input 1

4
BGBH

Sample Output 1

13

For example, participating in the 1-st and 3-rd contests is valid, and so is participating in the 2-nd and 4-th contests.
On the other hand, participating in the 1-st, 2-nd, 3-rd, and 4-th contests is invalid, since the participations in ABCs are not consecutive, violating the condition for the triple (i,j,k)=(1,2,3).
Additionally, it is not allowed to participate in zero contests.
In total, there are 13 valid ways to participate in some contests.

Sample Input 2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

Sample Output 2

330219020

Be sure to find the count modulo 998244353.

Problem Statement

There is a sequence A. Initially, A=(0). (That is, A is a sequence of length 1 containing 0 as its only element).

You are given Q queries to process in order. The i-th query (1\leq i\leq Q) has one of the following forms:

• 1 x: Insert i immediately after the location where x appears in A. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p such that A_p=x, update A to (A_1,\dots,A_p,i,A_{p+1},\dots,A_n). It is guaranteed that A contains x immediately before processing this query.
• 2 x y: Remove all elements between x and y in A, and output the sum of the values of the removed elements. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p and q such that A_p=x and A_q=y, output A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1} and update A to (A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n). It is guaranteed that A contains both x and y immediately before processing this query.

Note that for any sequence of queries, the same value never appears multiple times in A during the process of handling queries, and thus the position where a value appears in A is unique (if it exists).

Constraints

• 1\leq Q \leq 5\times 10^5
• For the i-th query:
  • If it is a type 1 query:
    • 0\leq x < i
    • A contains x immediately before processing the query.
  • If it is a type 2 query:
    • 0\leq x < y < i
    • A contains both x and y immediately before processing the query.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
5

Initially, A=(0).

• 1st query: Insert 1 immediately after 0. A becomes (0,1).
• 2nd query: Insert 2 immediately after 1. A becomes (0,1,2).
• 3rd query: Insert 3 immediately after 0. A becomes (0,3,1,2).
• 4th query: Remove the elements between 2 and 3, namely 1, and output the sum of the removed values, which is 1. A becomes (0,3,2).
• 5th query: Insert 5 immediately after 2. A becomes (0,3,2,5).
• 6th query: Remove the elements between 0 and 5, namely 3,2, and output the sum of the removed values, which is 5. A becomes (0,5).

Sample Input 2

2
1 0
2 0 1

Sample Output 2

0

In the 2nd query, we remove all elements between 0 and 1, but there are actually no such elements, so no elements are removed and the output value is 0.

Sample Input 3

10
1 0
1 1
2 0 2
2 0 2
1 0
1 5
2 0 5
2 2 6
1 6
1 9

Sample Output 3

1
0
0
0