Problem Statement

You are given a string S of length N consisting of three kinds of characters: ., |, and *. S contains exactly two | and exactly one *.

Determine whether the * is between the two |, and if so, print in; otherwise, print out.

More formally, determine whether one of the characters before the * is | and one of the characters after the * is |.

Constraints

• 3\leq N\leq 100
• N is an integer.
• S is a string of length N consisting of ., |, and *.
• S contains exactly two |.
• S contains exactly one *.

Sample Input 1

10
.|..*...|.

Sample Output 1

in

Between the two |, we have |..*...|, which contains *, so you should print in.

Sample Input 2

10
.|..|.*...

Sample Output 2

out

Between the two |, we have |..|, which does not contain *, so you should print out.

Sample Input 3

3
|*|

Sample Output 3

in

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

• If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
• If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq R_i \leq 10^9
• i \neq j \implies R_i \neq R_j
• All values in the input are integers.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

• It is a string of length L+1 consisting of o and -.
• Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

• There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

• 1\leq N\leq 2\times10^5
• S is a string of length N consisting of o and -.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7

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

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

• At least one vertex is painted black.
• For every i = 1, 2, \ldots, K, the following holds:
  • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

• 1 \leq N \leq 2000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
• 1 \leq u_i, v_i \leq N
• 0 \leq K \leq N
• 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
• 0 \leq d_i \leq N
• The given graph is simple and connected.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1

Problem Statement

You are given a string S consisting of lowercase English letters. Print the number of non-empty strings T that satisfy the following condition, modulo 998244353.

The concatenation TT of two copies of T is a subsequence of S (not necessarily contiguous).

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

ababbaba

Sample Output 1

8

The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.

Sample Input 2

zzz

Sample Output 2

1

The only string satisfying the condition is z. Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz, and S_2S_3 = zz.

Sample Input 3

ppppqqppqqqpqpqppqpqqqqpppqppq

Sample Output 3

580

Problem Statement

We have a sequence A of length N consisting of integers between 1 and M. Here, every integer from 1 to M appears at least once in A.

Among the length-M subsequences of A where each of 1, \ldots, M appears once, find the lexicographically smallest one.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq M
• Every integer between 1 and M, inclusive, appears at least once in A.
• All values in the input are integers.

Sample Input 1

4 3
2 3 1 3

Sample Output 1

2 1 3

The length-3 subsequences of A where each of 1, 2, 3 appears once are (2, 3, 1) and (2, 1, 3). The lexicographically smaller among them is (2, 1, 3).

Sample Input 2

4 4
2 3 1 4

Sample Output 2

2 3 1 4

Sample Input 3

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

Sample Output 3

3 5 8 10 9 6 1 4 2 7

Problem Statement

Takahashi has an unbiased six-sided die and a positive integer R less than 10^9. Each time the die is cast, it shows one of the numbers 1,2,3,4,5,6 with equal probability, independently of the outcomes of the other trials.

Takahashi will perform the following procedure. Initially, C=0.

1. Cast the die and increment C by 1.
2. Let X be the sum of the numbers shown so far. If X-R is a multiple of 10^9, quit the procedure.
3. Go back to step 1.

Find the expected value of C at the end of the procedure, modulo 998244353.

Notes

Under the constraints of this problem, it can be shown that the expected value of C is represented as an irreducible fraction p/q, and there is a unique integer x\ (0\leq x\lt998244353) such that xq \equiv p\pmod{998244353}. Print this x.

Constraints

• 0\lt R\lt10^9
• R is an integer.

Sample Input 1

1

Sample Output 1

291034221

The expected value of C at the end of the procedure is approximately 833333333.619047619, and 291034221 when represented modulo 998244353.

Sample Input 2

720357616

Sample Output 2

153778832