Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

• Buy one apple for X yen (the currency in Japan).
• Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

• 1 \leq X \leq Y \leq 100
• 1 \leq N \leq 100
• All values in input are integers.

Sample Input 1

10 25 10

Sample Output 1

85

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

100

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

200

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

3400

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

• x and y are the same character.
• One of x and y is 1 and the other is l.
• One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

• for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

• N is an integer between 1 and 100.
• Each of S and T is a string of length N consisting of lowercase English letters and digits.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

• 2 \leq H, W \leq 50
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
2 1 4
3 1 3
6 4 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

Constraints

• 0 \leq N \leq 21
• N is an integer.

Sample Input 1

3

Sample Output 1

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

Sample Input 2

4

Sample Output 2

0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 3 0
0 3 1
0 4 0
1 0 0
1 0 1
1 0 2
1 0 3
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 3 0
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
3 0 0
3 0 1
3 1 0
4 0 0

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.

You are given M pieces of information in the following form:

• From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.

Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i, B_i \leq N
• A_i \neq B_i
• -10^9 \leq X_i,Y_i \leq 10^9
• All input values are integers.
• The given information is consistent.

Sample Input 1

3 2
1 2 2 1
1 3 -1 -2

Sample Output 1

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 2

3 2
2 1 -2 -1
2 3 -3 -3

Sample Output 2

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

Sample Output 3

0 0
0 0
0 0
undecidable
undecidable

The same piece of information may be given multiple times, and multiple people may be at the same coordinates.

Problem Statement

For positive integers X and Y, a rectangle in a two-dimensional plane that satisfies the conditions below is said to be good.

• Every edge is parallel to the x- or y-axis.
• For every vertex, its x-coordinate is an integer between 0 and X (inclusive), and y-coordinate is an integer between 0 and Y (inclusive).

Determine whether it is possible to place the following three good rectangles without overlapping: a good rectangle of an area at least A, another of an area at least B, and another of an area at least C.

Here, three rectangles are considered to be non-overlapping when the intersection of any two of them has an area of 0.

Constraints

• 1 \leq X, Y \leq 10^9
• 1 \leq A, B, C \leq 10^{18}
• All values in input are integers.

Sample Input 1

3 3 2 2 3

Sample Output 1

Yes

The figure below shows a possible placement, where the number in a rectangle represents its area.

We can see that 2 \geq A, 3 \geq B, 3 \geq C, satisfying the conditions.

Sample Input 2

3 3 4 4 1

Sample Output 2

No

There is no possible placement under the conditions.

Sample Input 3

1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

No

Problem Statement

Given an integer N not less than 2, find the number of integers b not less than 2 such that:

• when N is written in base b, every digit is 0 or 1.

Find the answer for T independent test cases.

It can be proved that there is a finite number of desired integers b not less than 2 under the constraints of this problem.

Constraints

• 1 \leq T \leq 1000
• 2 \leq N \leq 10^{18}
• All values in the input are integers.

Sample Input 1

3
12
2
36

Sample Output 1

4
1
5

For the first test case, four b's satisfy the condition in the problem statement: b = 2, 3, 11, 12. Indeed, when N=12 is written in base 2, 3, 11, and 12, it becomes 1100, 110, 11 and 10, respectively.