Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

• 1 \leq N \leq 1000
• N is an integer.

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

• After each output, you must flush Standard Output. Otherwise, you may get TLE.
• After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
• If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

There is a staircase with infinite steps. The foot of the stairs is the 0-th step, the next step is the 1-st step, the next is the 2-nd, and so on.

There is a stair-climbing robot on the 0-th step. The robot can climb up A _ 1,A _ 2,\ldots, or A _ N steps at a time. In other words, when the robot is on the i-th step, it can step onto one of the (i+A _ 1)-th step, (i+A _ 2)-th step, \ldots, and (i+A _ N)-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.

There are traps on the B _ 1-th, B _ 2-th, \ldots, and B _ M-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.

The robot wants to step onto the X-th step. Determine whether it is possible to do so.

Constraints

• 1\leq N\leq10
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
• 1\leq M\leq10^5
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
• All values in the input are integers.

Sample Input 1

3
3 4 5
4
4 5 6 8
15

Sample Output 1

Yes

For example, the robot can reach the 15-th step as follows.

• Climb up 3 steps. The robot is now on the 3-rd step.
• Climb up 4 steps. The robot is now on the 7-th step.
• Climb up 5 steps. The robot is now on the 12-th step.
• Climb up 3 steps. The robot is now on the 15-th step.

Sample Input 2

4
2 3 4 5
4
3 4 5 6
8

Sample Output 2

No

No matter how the robot moves, it cannot step onto the 8-th step.

Sample Input 3

4
2 5 7 8
5
2 9 10 11 19
20

Sample Output 3

Yes

Problem Statement

You are given a weighted simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N, and edges are numbered 1 to M. Additionally, a positive integer K is given.
Edge i\ (1\leq i\leq M) connects vertices u_i and v_i and has a weight of w_i.

For a spanning tree T of this graph, the cost of T is defined as the sum, modulo K, of the weights of the edges in T. Find the minimum cost of a spanning tree of this graph.

Constraints

• 2\leq N\leq8
• N-1\leq M\leq\dfrac{N(N-1)}2
• 1\leq K\leq10^{15}
• 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
• 0\leq w_i\lt K\ (1\leq i\leq M)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

Sample Output 1

33

The given graph is shown below:

The cost of the spanning tree containing edges 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33. The cost of every spanning tree of this graph is at least 33, so print 33.

Sample Input 2

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

Sample Output 2

325437688

Print the cost of the only spanning tree of this graph, which is 325437688.

Sample Input 3

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

Sample Output 3

11360716373

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is black or white, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is white;
• if the j-th character of S_i is #, square (i,j) is black.

The grid is said to be beautiful when the following condition is satisfied.

• For every pair of integers (i,j) such that 1 \le i \le N, 1 \le j \le M, if square (i,j) is black, the square under (i,j) and the square to the immediate lower right of (i,j) are also black (if they exist).
• Formally, all of the following are satisfied.
  • If square (i,j) is black and square (i+1,j) exists, square (i+1,j) is also black.
  • If square (i,j) is black and square (i+1,j+1) exists, square (i+1,j+1) is also black.

Takahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.
Find the number of different beautiful grids he can make, modulo 998244353.
Two grids are considered different when there is a square that has different colors in those two grids.

Constraints

• 1 \le N,M \le 2000
• S_i is a string of length M consisting of . and #.

Sample Input 1

2 2
.#
..

Sample Output 1

3

He can make the following three different beautiful grids:

.#  .#  ##
.#  ##  ##

Sample Input 2

5 5
....#
...#.
..#..
.#.#.
#...#

Sample Output 2

92

Sample Input 3

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

Sample Output 3

604936632

Find the count modulo 998244353.