Problem Statement

Print a number between A and B (inclusive) that is a multiple of C.

If there is no such number, print -1.

Constraints

• 1 \leq A \leq B \leq 1000
• 1 \leq C \leq 1000
• All values in input are integers.

Sample Input 1

123 456 100

Sample Output 1

200

300 or 400 would also be accepted.

Sample Input 2

630 940 314

Sample Output 2

-1

Problem Statement

Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.

He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)

Constraints

• 2 \leq N \leq 100
• 1 \leq H \lt X \leq 999
• 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
• All input values are integers.

Sample Input 1

3 100 200
50 200 999

Sample Output 1

2

Below is the change in the monster's health when one of the potions is given to the monster.

• If potion 1 is given, the monster's health becomes 100 + 50 = 150.
• If potion 2 is given, the monster's health becomes 100 + 200 = 300.
• If potion 3 is given, the monster's health becomes 100 + 999 = 1099.

The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.

Sample Input 2

2 10 21
10 999

Sample Output 2

2

Sample Input 3

10 500 999
38 420 490 585 613 614 760 926 945 999

Sample Output 3

4

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

• L\leq X_i \leq R.
• For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

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

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

• |4-3|=1
• |5-3|=2
• |6-3|=3
• |7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

• 100 \leq N \leq 919
• N is an integer.

Sample Input 1

320

Sample Output 1

326

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.

Sample Input 2

144

Sample Output 2

144

144 is a 326-like number.

Sample Input 3

516

Sample Output 3

600

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

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

This is an interactive task (where your program interacts with the judge's program via input and output).

We have an N-by-N chessboard and N rooks. Below, the square at the i-th row from the top and j-th column from the left is denoted by (i, j).
Consider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied.

• No row contains two or more rooks.
• No column contains two or more rooks.

Now, N-1 rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.)

However, you cannot directly see which squares of the chessboard are occupied by a rook.
Instead, you may ask at most 20 questions to the judge in the following manner.

• You choose integers A, B, C, and D such that 1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N, and ask the number of rooks in the rectangular region formed by the squares (i, j) such that A \leq i \leq B, C \leq j \leq D.

Find a square to place a rook.

Constraints

• 2 \leq N \leq 10^3
• N is an integer.

Input and Output

This is an interactive task (where your program interacts with the judge's program via input and output).

First, receive the size of the chessboard, N, from Standard Input.

N

Next, repeat asking a question until you find a square to place a rook.
A question should be printed to Standard Output in the following format:

? A B C D

The response will be given from Standard Input in the following format:

T

Here, T is the response to the question, or -1 if the question is invalid or more than 20 questions have been asked.

When the judge returns -1, the submission is already regarded as incorrect. In this case, terminate the program immediately.

When you find a square to place a rook, let (X, Y) be that square and print an answer in the following format. Then, terminate the program immediately.

! X Y

If there are multiple appropriate answers, any of them will be accepted.

Notes

• Each time you print something, end it with a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, the verdict will be indeterminate.
• Terminate the program immediately after printing an answer. Otherwise, the verdict will be indeterminate.

Sample Interaction

Below is an interaction where N=3 and the rooks are placed on (1, 2) and (2, 1).

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507