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

Given N, print 2^N.

Constraints

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

Sample Input 1

3

Sample Output 1

8

We have 2^3=8.

Sample Input 2

30

Sample Output 2

1073741824

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

• We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

• -1000 \leq a,b \leq 1000
• 1 \leq d \leq 360
• All values in input are integers.

Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).

Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.

Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.

Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.

Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

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

Problem Statement

N people numbered 1 through N tossed a coin several times. We know that person i's tosses resulted in A_i heads and B_i tails.

Person i's success rate of the tosses is defined by \displaystyle\frac{A_i}{A_i+B_i}. Sort people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i, B_i\leq 10^9
• A_i+B_i \geq 1
• All input values are integers.

Sample Input 1

3
1 3
3 1
2 2

Sample Output 1

2 3 1

Person 1's success rate is 0.25, person 2's is 0.75, and person 3's is 0.5.

Sort them in descending order of their success rates to obtain the order in Sample Output.

Sample Input 2

2
1 3
2 6

Sample Output 2

1 2

Note that person 1 and 2 should be printed in ascending order of their numbers, as they have the same success rates.

Sample Input 3

4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

Sample Output 3

3 1 4 2

Problem Statement

Takahashi has decided to enjoy a wired full-course meal consisting of N courses in a restaurant.
The i-th course is:

• if X_i=0, an antidotal course with a tastiness of Y_i;
• if X_i=1, a poisonous course with a tastiness of Y_i.

When Takahashi eats a course, his state changes as follows:

• Initially, Takahashi has a healthy stomach.
• When he has a healthy stomach,
  • if he eats an antidotal course, his stomach remains healthy;
  • if he eats a poisonous course, he gets an upset stomach.
• When he has an upset stomach,
  • if he eats an antidotal course, his stomach becomes healthy;
  • if he eats a poisonous course, he dies.

The meal progresses as follows.

• Repeat the following process for i = 1, \ldots, N in this order.
  • First, the i-th course is served to Takahashi.
  • Next, he chooses whether to "eat" or "skip" the course.
    • If he chooses to "eat" it, he eats the i-th course. His state also changes depending on the course he eats.
    • If he chooses to "skip" it, he does not eat the i-th course. This course cannot be served later or kept somehow.
  • Finally, (if his state changes, after the change) if he is not dead,
    • if i \neq N, he proceeds to the next course.
    • if i = N, he makes it out of the restaurant alive.

An important meeting awaits him, so he must make it out of there alive.
Find the maximum possible sum of tastiness of the courses that he eats (or 0 if he eats nothing) when he decides whether to "eat" or "skip" the courses under that condition.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• X_i \in \{0,1\}
  • In other words, X_i is either 0 or 1.
• -10^9 \le Y_i \le 10^9

Sample Input 1

5
1 100
1 300
0 -200
1 500
1 300

Sample Output 1

600

The following choices result in a total tastiness of the courses that he eats amounting to 600, which is the maximum possible.

• He skips the 1-st course. He now has a healthy stomach.
• He eats the 2-nd course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 300.
• He eats the 3-rd course. He now has a healthy stomach again, and the total tastiness of the courses that he eats amounts to 100.
• He eats the 4-th course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 600.
• He skips the 5-th course. He now has an upset stomach.
• In the end, he is not dead, so he makes it out of the restaurant alive.

Sample Input 2

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

Sample Output 2

0

For this input, it is optimal to eat nothing, in which case the answer is 0.

Sample Input 3

15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

Sample Output 3

4100000000

The answer may not fit into a 32-bit integer type.

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

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge gives you an integer N.
• You print an integer M between 1 and 50000, inclusive.
• You also print M pairs of integers (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) such that 1 \leq l_i \leq r_i \leq N for every i = 1, 2, \ldots, M (the M pairs do not have to be distinct).

(Phase 2)

• The judge gives you an integer Q.
• You and the judge repeats the following Q times.
  • The judge gives you two integers L and R as a query.
  • You respond with two integers a and b between 1 and M, inclusive (possibly with a = b). Here, a and b must satisfy the condition below. Otherwise, your submission will be judged incorrect.
    • The union of the set \lbrace l_a, l_a+1, \ldots, r_a\rbrace and the set \lbrace l_b, l_b+1, \ldots, r_b\rbrace equals the set \lbrace L, L+1, \ldots, R\rbrace.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• 1 \leq N \leq 4000
• 1 \leq Q \leq 10^5
• 1 \leq L \leq R \leq N
• All values in the input are integers.

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, N is given from the input.
• Next, an integer M between 1 and 50000, inclusive, should be printed.
• Then, (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) should be printed, one at a time. Specifically, for each i = 1, 2, \ldots, M, the i-th output should be (l_i, r_i) in the following format:

l_i r_i

(Phase 2)

• First, Q is given from the input.
• In each query, integers L and R representing the query are given in the following format:

L R

• In response to each query, two integers a and b should be printed in the following format:

a b

Cautions

• At the end of each output, print a newline and flush Standard Output. Otherwise, you may get the TLE verdict.
• If your program prints a malformed output or quits prematurely, the verdict will be indeterminate. Particularly, note that in case of a runtime error, the verdict may be WA or TLE instead of RE.
• After phase 2, immediately terminate the program. Otherwise, the verdict will be indeterminate.
• L and R given in phase 2 will be decided according to (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) you print in phase 1.

Sample Interaction

Below is a sample interaction with N = 4 and Q = 4.