Problem Statement

You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N
• P is a permutation of (1,2,…,N).
• All values in the input are integers.

Sample Input 1

4 3
2 3 1 4

Sample Output 1

2

We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.

Sample Input 2

5 2
3 5 1 4 2

Sample Output 2

5

Sample Input 3

6 6
1 2 3 4 5 6

Sample Output 3

6

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

• First, he painted the part from X=L_1 to X=R_1 red.
• Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

• 0\leq L_1<R_1\leq 100
• 0\leq L_2<R_2\leq 100
• All values in input are integers.

Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

• 1 \leq A \leq B \leq 10^9
• 2 \leq K \leq 10^9
• All values in input are integers.

Sample Input 1

1 4 2

Sample Output 1

2

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

0

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

6

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N and a positive integer M.

Your goal is to make the following condition false by performing this operation between 0 and N times (inclusive): remove the last element of A.

• Condition: A contains every integer from 1 through M.

Find the minimum number of operations required.

Under the constraints of this problem, it can be proved that it is always possible to make the condition false by performing the operation between 0 and N times.

Constraints

• 1 \le M \le N \le 100
• 1 \le A_i \le M
• All input values are integers.

Sample Input 1

5 3
3 2 3 1 2

Sample Output 1

2

Initially, A = (3,2,3,1,2). Since A contains every integer from 1 through 3, the condition holds.

If you perform the operation once, A = (3,2,3,1). The condition still holds.

If you perform the operation once more, A = (3,2,3). The integer 1 is missing, so the condition no longer holds.

Therefore, the minimum required number of operations is 2.

Sample Input 2

4 3
1 3 1 3

Sample Output 2

0

Since A initially lacks the integer 2, the condition is already false, so no operation is needed.

Sample Input 3

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

Sample Output 3

6

Problem Statement

You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.

• The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
  • That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.

Constraints

• N is an integer.
• 0 \le N < 2^{60}
• In the binary representation of N, at most 15 digit positions contain 1.

Sample Input 1

11

Sample Output 1

0
1
2
3
8
9
10
11

The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:

• 0000_{(2)}=0_{(10)}
• 0001_{(2)}=1_{(10)}
• 0010_{(2)}=2_{(10)}
• 0011_{(2)}=3_{(10)}
• 1000_{(2)}=8_{(10)}
• 1001_{(2)}=9_{(10)}
• 1010_{(2)}=10_{(10)}
• 1011_{(2)}=11_{(10)}

Sample Input 2

0

Sample Output 2

0

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a 32-bit signed integer.

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

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that for any i\ (1\le i\le N), A_i is not 0.

Determine whether there exists a permutation B=(B_1,B_2,\ldots,B_N) of A such that B forms a geometric sequence.

A sequence S=(S_1,S_2,\ldots,S_N) is a geometric sequence if there exists a real number r such that S_{i+1}=rS_i for all integers 1\le i\lt N.

Solve T test cases per input file.

Constraints

• 1\le T\le10^5
• 2\le N\le2\times10^5
• -10^9\le A_i\le10^9\ (1\le i\le N)
• A_i\ne0\ (1\le i\le N)
• The sum of N over all test cases in a single input file is at most 2\times10^5.
• All input values are integers.

Sample Input 1

3
5
1 8 2 4 16
5
-16 24 54 81 -36
7
90000 8100 -27000 729 -300000 -2430 1000000

Sample Output 1

Yes
No
Yes

In the first test case, the rearrangement (16,8,4,2,1) of A forms a geometric sequence with common ratio r=\frac{1}{2}. Thus, print Yes on the first line.

In the second test case, no rearrangement of A satisfies the condition. Thus, print No on the second line.

Problem Statement

Takahashi is playing sugoroku, a board game.

The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.

The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.

For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 4 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.

When Takahashi arrives at square N, he wins and the game ends.

Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.

Constraints

• M \leq N \leq 1000
• 1 \leq M \leq 10
• 1 \leq K \leq 1000
• All values in the input are integers.

Sample Input 1

2 2 1

Sample Output 1

499122177

Takahashi wins in one spin if the wheel shows 2. Therefore, the probability of winning is \frac{1}{2}.

We have 2\times 499122177 \equiv 1 \pmod{998244353}, so the answer to be printed is 499122177.

Sample Input 2

10 5 6

Sample Output 2

184124175

Sample Input 3

100 1 99

Sample Output 3

0

Problem Statement

This is an interactive problem (where your program and the judge program interact through Standard Input and Output).

There is a simple connected undirected graph with N vertices and M edges. The vertices are numbered with integers from 1 to N.

Initially, you are at vertex 1. Repeat moving to an adjacent vertex at most 2N times to reach vertex N.

Here, you do not initially know all edges of the graph, but you will be informed of the vertices adjacent to the vertex you are at.

Constraints

• 2\leq N\leq100
• N-1\leq M\leq\dfrac{N(N-1)}2
• The graph is simple and connected.
• All input values are integers.

Input and Output

First, receive the number of vertices N and the number of edges M in the graph from Standard Input:

N M

Next, you get to repeat the operation described in the problem statement at most 2N times against the judge.

At the beginning of each operation, the vertices adjacent to the vertex you are currently at are given from Standard Input in the following format:

k v _ 1 v _ 2 \ldots v _ k

Here, v _ i\ (1\leq i\leq k) are integers between 1 and N such that v _ 1\lt v _ 2\lt\cdots\lt v _ k.

Choose one of v _ i\ (1\leq i\leq k) and print it to Standard Output in the following format:

v _ i

After this operation, you will be at vertex v _ i.

If you perform more than 2N operations or print invalid output, the judge will send -1 to Standard Input.

If the destination of a move is vertex N, the judge will send OK to Standard Input and terminate.

When receiving -1 or OK, immediately terminate the program.

Notes

• In each output, insert a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
• The verdict will be indeterminate if the program prints invalid output or quits prematurely in the middle of the interaction.
• Terminate the program immediately after reaching vertex N. Otherwise, the verdict will be indeterminate.
• The judge for this problem is adaptive. This means that the graph may change without contradicting the constraints or previous outputs.

Sample Interaction

In the following sample interaction, we have N=4, M=5, and the graph in the figure below.

You will be judged as correct if you immediately terminate the program after receiving OK.