Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

• 0 \leq A \leq 23
• 0 \leq B \leq 59
• 0 \leq C \leq 23
• 0 \leq D \leq 59
• All values in input are integers.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.

Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

• All input values are integers.
• 4 \leq N \leq 8
• 100 \leq S_i \leq 675
• 100 \leq X \leq 675

Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.

Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0

Problem Statement

There are non-negative integers A, B, C, D, E, and F, which satisfy A\times B\times C\geq D\times E\times F.
Find the remainder when (A\times B\times C)-(D\times E\times F) is divided by 998244353.

Constraints

• 0\leq A,B,C,D,E,F\leq 10^{18}
• A\times B\times C\geq D\times E\times F
• A, B, C, D, E, and F are integers.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since A\times B\times C=2\times 3\times 5=30 and D\times E\times F=1\times 2\times 4=8,
we have (A\times B\times C)-(D\times E\times F)=22. Divide this by 998244353 and print the remainder, which is 22.

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since A\times B\times C=1000000000 and D\times E\times F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000. Divide this by 998244353 and print the remainder, which is 1755647.

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have (A\times B\times C)-(D\times E\times F)=0. Divide this by 998244353 and print the remainder, which is 0.

Problem Statement

N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.

A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq P \leq 100
• 0 \leq a_i \leq 100 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4 50
80 60 40 0

Sample Output 1

2

Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.

Sample Input 2

3 90
89 89 89

Sample Output 2

3

Sample Input 3

2 22
6 37

Sample Output 3

1

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

• P is a permutation of (1, \dots, N).
• For every pair of integers i, j between 1 and N (inclusive), the following holds.
  • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
• (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

Sample Input 2

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

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

• All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

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

Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

Problem Statement

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

The judge has a string of length N consisting of 0 and 1: S = S_1S_2\ldots S_N. Here, S_1 = 0 and S_N = 1.

You are given the length N of S, but not the contents of S. Instead, you can ask the judge at most 20 questions as follows.

• Choose an integer i such that 1 \leq i \leq N and ask the value of S_i.

Print an integer p such that 1 \leq p \leq N-1 and S_p \neq S_{p+1}.
It can be shown that such p always exists under the settings of this problem.

Constraints

• 2 \leq N \leq 2 \times 10^5

Input and Output

First, receive the length N of the string S from Standard Input:

N

Then, you get to ask the judge at most 20 questions as described in the problem statement.

Print each question to Standard Output in the following format, where i is an integer satisfying 1 \leq i \leq N:

? i

In response to this, the value of S_i will be given from Standard Input in the following format:

S_i

Here, S_i is 0 or 1.

When you find an integer p satisfying the condition in the problem statement, print it in the following format, and immediately quit the program:

! p

If multiple solutions exist, you may print any of them.

Notes

• Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
• If there is malformed output during the interaction or your program quits prematurely, the verdict will be indeterminate.
• After printing the answer, immediately quit the program. Otherwise, the verdict will be indeterminate.
• The string S will be fixed at the start of the interaction and will not be changed according to your questions or other factors.

Sample Input and Output

In the following interaction, N = 7 and S = 0010011.

For the presented p = 5, we have 1 \leq p \leq N-1 and S_p \neq S_{p+1}. Thus, if the program immediately quits here, this case will be judged as correctly solved.

Problem Statement

There are N rectangular cuboids in a three-dimensional space.

These cuboids do not overlap. Formally, for any two different cuboids among them, their intersection has a volume of 0.

The diagonal of the i-th cuboid is a segment that connects two points (X_{i,1},Y_{i,1},Z_{i,1}) and (X_{i,2},Y_{i,2},Z_{i,2}), and its edges are all parallel to one of the coordinate axes.

For each cuboid, find the number of other cuboids that share a face with it.
Formally, for each i, find the number of j with 1\leq j \leq N and j\neq i such that the intersection of the surfaces of the i-th and j-th cuboids has a positive area.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq X_{i,1} < X_{i,2} \leq 100
• 0 \leq Y_{i,1} < Y_{i,2} \leq 100
• 0 \leq Z_{i,1} < Z_{i,2} \leq 100
• Cuboids do not have an intersection with a positive volume.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
1
0
0

The 1-st and 2-nd cuboids share a rectangle whose diagonal is the segment connecting two points (0,0,1) and (1,1,1).
The 1-st and 3-rd cuboids share a point (1,1,1), but do not share a surface.

Sample Input 2

3
0 0 10 10 10 20
3 4 1 15 6 10
0 9 6 1 20 10

Sample Output 2

2
1
1

Sample Input 3

8
0 0 0 1 1 1
0 0 1 1 1 2
0 1 0 1 2 1
0 1 1 1 2 2
1 0 0 2 1 1
1 0 1 2 1 2
1 1 0 2 2 1
1 1 1 2 2 2

Sample Output 3

3
3
3
3
3
3
3
3

Problem Statement

Snuke is planning on giving one gift each to Takahashi and Aoki.
There are N candidates for the gifts. Takahashi's impression of the i-th candidate is A_i, and Aoki's impression of it is B_i.

The two are very jealous. If Takahashi's impression of the gift Aoki gets is greater than Takahashi's impression of the gift Takahashi gets, Takahashi gets jealous of Aoki and starts fighting, and vice versa.

Among the N^2 possible ways of giving the gifts, how many do not lead to fighting?

Constraints

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

Sample Input 1

3
50 100 150
1 3 2

Sample Output 1

4

For example, if we give the 1-st candidate to Takahashi and the 2-nd candidate to Aoki, Takahashi's impression of the gift Aoki gets is 100, while Takahashi's impression of the gift Takahashi gets is 50, so Takahashi gets jealous of Aoki and starts fighting.

As another example, if we give the 3-rd candidate to Takahashi and the 2-nd candidate to Aoki, the two will not start fighting.

Note that it is allowed to give the same gift to the two.

Sample Input 2

3
123456789 123456 123
987 987654 987654321

Sample Output 2

6

Sample Input 3

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

Sample Output 3

37