Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

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 - 1 white balls and one black ball. These N balls are arranged in a row, with the black ball initially at the leftmost position.

Takahashi will perform the following operation exactly K times.

• Choose an integer uniformly at random between 1 and N, inclusive, twice. Let a and b the chosen integers. If a \neq b, swap the a-th and b-th balls from the left.

After K operations, let the black ball be at the x-th position from the left. Find the expected value of x, modulo 998244353.

Constraints

• 1 \leq N \leq 998244352
• 1 \leq K \leq 10^5

Sample Input 1

2 1

Sample Output 1

499122178

After one operation, the probabilities that the black ball is at the 1st position and the 2nd position from the left are both \displaystyle \frac{1}{2}. Thus, the expected value is \displaystyle \frac{3}{2}.

Sample Input 2

3 2

Sample Output 2

554580198

Sample Input 3

4 4

Sample Output 3

592707587

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq r_i,c_i,x_i \leq 10^9
• (r_i,c_i) \neq (r_j,c_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4
1 1 2
1 2 9
2 1 8
3 2 3

Sample Output 1

20

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068