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

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

There are N sleighs numbered 1,2,\ldots, N.

R_i reindeer are required to pull sleigh i.

Additionally, each reindeer can pull at most one sleigh. More precisely, \sum_{k=1}^{m} R_{i_k} reindeer are required to pull m sleighs i_1, i_2, \ldots, i_m.

Find the answer to Q queries of the following form:

• You are given an integer X. Determine the maximum number of sleighs that can be pulled when there are X reindeer.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq R_i \leq 10^9
• 1 \leq X \leq 2 \times 10^{14}
• All input values are integers.

Sample Input 1

4 3
5 3 11 8
16
7
1000

Sample Output 1

3
1
4

When there are 16 reindeer, sleighs 1,2,4 can be pulled.

It is impossible to pull four sleighs with 16 reindeer, so the answer to query 1 is 3.

Sample Input 2

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

Sample Output 2

1
1
2
2
2
3

Sample Input 3

2 2
1000000000 1000000000
200000000000000
1

Sample Output 3

2
0

Problem Statement

Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting N times. In each teleportation, he makes one of the following moves:

• Move from the current coordinates (x,y) to (x+A,y+B)
• Move from the current coordinates (x,y) to (x+C,y+D)
• Move from the current coordinates (x,y) to (x+E,y+F)

There are obstacles on M points (X_1,Y_1),\ldots,(X_M,Y_M) on the plane; he cannot teleport to these coordinates.

How many paths are there resulting from the N teleportations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 300
• 0 \leq M \leq 10^5
• -10^9 \leq A,B,C,D,E,F \leq 10^9
• (A,B), (C,D), and (E,F) are distinct.
• -10^9 \leq X_i,Y_i \leq 10^9
• (X_i,Y_i)\neq(0,0)
• (X_i,Y_i) are distinct.
• All values in input are integers.

Sample Input 1

2 2
1 1 1 2 1 3
1 2
2 2

Sample Output 1

5

The following 5 paths are possible:

• (0,0)\to(1,1)\to(2,3)
• (0,0)\to(1,1)\to(2,4)
• (0,0)\to(1,3)\to(2,4)
• (0,0)\to(1,3)\to(2,5)
• (0,0)\to(1,3)\to(2,6)

Sample Input 2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

Sample Output 2

0

Sample Input 3

300 0
0 0 1 0 0 1

Sample Output 3

292172978

Problem Statement

Given is a string S. From this string, Takahashi will make a new string T as follows.

• First, mark one or more characters in S. Here, no two marked characters should be adjacent.
• Next, delete all unmarked characters.
• Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.

How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

4

There are four strings that can be obtained as T: a, b, c, and ac.

Marking the first character of S yields a;

marking the second character of S yields b;

marking the third character of S yields c;

marking the first and third characters of S yields ac.

Note that it is forbidden to, for example, mark both the first and second characters.

Sample Input 2

aa

Sample Output 2

1

There is just one string that can be obtained as T, which is a. Note that marking different positions may result in the same string.

Sample Input 3

acba

Sample Output 3

6

There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.

Sample Input 4

chokudai

Sample Output 4

54