Problem Statement

Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)

Is it possible that the total amount of money in the purse is X yen?

Constraints

• 0 \leq X \leq 1000
• All values in input are integers.

Sample Input 1

500

Sample Output 1

Yes

If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.

Sample Input 2

40

Sample Output 2

No

Sample Input 3

0

Sample Output 3

No

Note that the purse has at least one 100-yen coin.

Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.

Constraints

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

Sample Input 1

27

Sample Output 1

3

3^3 = 27, so print 3.

Sample Input 2

100

Sample Output 2

-1

There is no A such that A^A = B.

Sample Input 3

10000000000

Sample Output 3

10

Problem Statement

N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.

• Accumulates two yellow cards.
• Receives a red card.

Once a player is removed, that player will no longer receive any cards.

You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x from the input, where c is 1, 2, or 3. The events are as follows.

• 1 x: Player x receives a yellow card.
• 2 x: Player x receives a red card.
• 3 x: You are asked whether player x has been removed from the game. Answer Yes or No.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 100
• 1 \leq x \leq N in all events.
• There is at least one event of the third kind.
• A player who has been removed will no longer receive any cards.
• All values in the input are integers.

Sample Input 1

3 9
3 1
3 2
1 2
2 1
3 1
3 2
1 2
3 2
3 3

Sample Output 1

No
No
Yes
No
Yes
No

Here are all the events in chronological order.

In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No.

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

• 1 \leq N \leq 200
• Each of S and T consists of # and ..
• Each of S and T contains at least one #.

Sample Input 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

Problem Statement

N people, with ID numbers 1, 2, \dots, N, are lining up in front of a bank.
There will be Q events. The following three kinds of events can happen.

• 1 : The teller calls the person with the smallest ID number who has not been called.
• 2 x : The person with the ID number x comes to the teller for the first time. (Here, person x has already been called by the teller at least once.)
• 3 : The teller again calls the person with the smallest ID number who has already been called but has not come.

Print the ID numbers of the people called by the teller in events of the third kind.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 2 \leq Q \leq 5 \times 10^5
• There will not be an event of the first kind when all people have already been called at least once.
• For each event of the second kind, the person with the ID number x has already been called by the teller at least once.
• For each event of the second kind, the person with the ID number x will not come to the teller more than once.
• There will not be an event of the third kind when all people who have already been called have come to the teller.
• There is at least one event of the third kind.
• All values in the input are integers.

Sample Input 1

4 10
1
1
3
2 1
1
2 3
3
1
2 2
3

Sample Output 1

1
2
4

For each i = 1, 2, \dots, Q, shown below is the set of people who have already been called but have not come just before the i-th event.

• i=1 : \lbrace \rbrace
• i=2 : \lbrace 1\rbrace
• i=3 : \lbrace 1,2\rbrace
• i=4 : \lbrace 1,2\rbrace
• i=5 : \lbrace 2\rbrace
• i=6 : \lbrace 2,3\rbrace
• i=7 : \lbrace 2\rbrace
• i=8 : \lbrace 2\rbrace
• i=9 : \lbrace 2,4\rbrace
• i=10 : \lbrace 4\rbrace

The events for i=3,7,10 are of the third kind, so you should print the persons with the smallest ID numbers in the sets for those events: 1, 2, 4.

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

We have a simple undirected graph G with (S+T) vertices and M edges. The vertices are numbered 1 through (S+T), and the edges are numbered 1 through M. Edge i connects Vertices u_i and v_i.
Here, vertex sets V_1 = \lbrace 1, 2,\dots, S\rbrace and V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace are both independent sets.

A cycle of length 4 is called a 4-cycle.
If G contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.
If G does not contain a 4-cycle, print -1.

Constraints

• 2 \leq S \leq 3 \times 10^5
• 2 \leq T \leq 3000
• 4 \leq M \leq \min(S \times T,3 \times 10^5)
• 1 \leq u_i \leq S
• S + 1 \leq v_i \leq S + T
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1 2 4 5

There are edges between Vertices 1 and 4, 4 and 2, 2 and 5, and 5 and 1, so Vertices 1, 2, 4, and 5 form a 4-cycle. Thus, 1, 2, 4, and 5 should be printed.
The vertices may be printed in any order. Besides the Sample Output, 2 5 1 4 is also considered correct, for example.

Sample Input 2

3 2 4
1 4
1 5
2 5
3 5

Sample Output 2

-1

Some inputs may give G without a 4-cycle.

Sample Input 3

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

Sample Output 3

1 7 2 9