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

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N\times 26
• All values in input are integers.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

• L\leq X_i \leq R.
• For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq L\leq R \leq 10^9
• 1\leq A_i\leq 10^9
• All input values are integers.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

• |4-3|=1
• |5-3|=2
• |6-3|=3
• |7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq N-2
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 < X_1 < \ldots < X_M < N
• 1 \leq Y_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

• Takahashi is initially in Room 1, and the time limit is 10.
• He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
• He consumes a time of 7 to move to Room 3. Now the time limit is 8.
• He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.

Problem Statement

You are given an integer N and a string S of length N consisting of o and x.

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Initially, A=(1,2,\ldots,N).

Perform the following operation on A for k=1,2,\ldots,N in this order.

• If S_k= o, reverse the first k terms of A. Specifically, replace A with (A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N).
• If S_k= x, do nothing.

Find A after all the operations are completed.

Constraints

• 2\le N\le 5\times 10^5
• N is an integer.
• S is a string of length N consisting of o and x.

Sample Input 1

5
ooxoo

Sample Output 1

5 2 1 3 4

A changes as follows with each operation:

• For k=1: reverse the first 1 term of A. A becomes (1,2,3,4,5).
• For k=2: reverse the first 2 terms of A. A becomes (2,1,3,4,5).
• For k=3: do nothing.
• For k=4: reverse the first 4 terms of A. A becomes (4,3,1,2,5).
• For k=5: reverse the first 5 terms of A. A becomes (5,2,1,3,4).

After all the operations are completed, A is A=(5,2,1,3,4).

Sample Input 2

7
ooooooo

Sample Output 2

7 5 3 1 2 4 6

Sample Input 3

15
xooxoxoxoxoxxoo

Sample Output 3

15 11 10 7 6 3 1 2 4 5 8 9 12 13 14

Problem Statement

At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.

Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:

• Pressing button A appends 0 to the end of t.
• Pressing button B replaces every digit in t with the next digit: for digits 0 through 8 the next digit is the one whose value is larger by 1; the next digit after 9 is 0.

For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.

You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.

Constraints

• S is a string consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
• 1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.

Sample Input 1

21

Sample Output 1

4

The following sequence of presses makes t equal to 21.

1. Press button A. t becomes 0.
2. Press button B. t becomes 1.
3. Press button A. t becomes 10.
4. Press button B. t becomes 21.

It is impossible to obtain 21 with fewer than four presses, so output 4.

Sample Input 2

407

Sample Output 2

17

Sample Input 3

2025524202552420255242025524

Sample Output 3

150

Problem Statement

There is an infinitely large two-dimensional grid, with a campfire at coordinate (0,0).
At time t=0, smoke exists only at cell (0,0).

You are given a length-N string S consisting of N, W, S, E. At times t=1,2,\dots,N, the following happen in order:

• Wind blows, and all the smoke present at that time moves as follows:
  • If the t-th character of S is N, smoke in cell (r,c) moves to cell (r-1,c).
  • If it is W, smoke in cell (r,c) moves to cell (r,c-1).
  • If it is S, smoke in cell (r,c) moves to cell (r+1,c).
  • If it is E, smoke in cell (r,c) moves to cell (r,c+1).
• If there is no smoke in cell (0,0), new smoke is generated at cell (0,0).

Takahashi is standing at cell (R,C).
For each integer 1 \le t \le N, determine if smoke exists at cell (R,C) at time t+0.5, and print the response according to the required format.

Constraints

• N is an integer between 1 and 200000, inclusive.
• S is a length N string consisting of N, W, S, E.
• R and C are integers between -N and N, inclusive.
• (R,C) \neq (0,0)

Sample Input 1

6 -2 1
NNEEWS

Sample Output 1

001010

At times 1.5,2.5,4.5,6.5, there is no smoke at cell (-2,1). At times 3.5,5.5, there is smoke at cell (-2,1).
Hence, output 001010.

In the figures below, taking cell (0,0) with the campfire as a reference, cell (r,c) is drawn:

• -r cells up if r < 0,
• r cells down if r \ge 0,
• -c cells left if c < 0,
• c cells right if c \ge 0.

The grid at time 0.5 looks like:

The grid at time 1.5 looks like:

The grid at time 2.5 looks like:

The grid at time 3.5 looks like:

The grid at time 4.5 looks like:

The grid at time 5.5 looks like:

The grid at time 6.5 looks like:

Sample Input 2

10 1 2
NEESESWEES

Sample Output 2

0001101011

Sample Input 3

20 -1 -2
WWNNWSWEWNSWWENSNWWN

Sample Output 3

00100111111000101111

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and an integer K.
There are 2^{N-1} ways to divide A into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to K? Find the count modulo 998244353.

Here, "to divide A into several contiguous subsequences" means the following procedure.

• Freely choose the number k (1 \leq k \leq N) of subsequences and an integer sequence (i_1, i_2, \dots, i_k, i_{k+1}) satisfying 1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1.
• For each 1 \leq n \leq k, the n-th subsequence is formed by taking the i_n-th through (i_{n+1} - 1)-th elements of A, maintaining their order.

Here are some examples of divisions for A = (1, 2, 3, 4, 5):

• (1, 2, 3), (4), (5)
• (1, 2), (3, 4, 5)
• (1, 2, 3, 4, 5)

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^{15} \leq K \leq 10^{15}
• -10^9 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

• (1), (2, 3)
• (1, 2, 3)

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428

Problem Statement

You are given a positive integer N and sequences of N positive integers each: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

We have an N \times N grid. The square at the i-th row from the top and the j-th column from the left is called the square (i,j). For each pair of integers (i,j) such that 1 \le i,j \le N, the square (i,j) has the integer A_i + B_j written on it. Process Q queries of the following form.

• You are given a quadruple of integers h_1,h_2,w_1,w_2 such that 1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N. Find the greatest common divisor of the integers contained in the rectangle region whose top-left and bottom-right corners are (h_1,w_1) and (h_2,w_2), respectively.

Constraints

• 1 \le N,Q \le 2 \times 10^5
• 1 \le A_i,B_i \le 10^9
• 1 \le h_1 \le h_2 \le N
• 1 \le w_1 \le w_2 \le N
• All values in input are integers.

Sample Input 1

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

Sample Output 1

2
1
11
6
10

Let C_{i,j} denote the integer on the square (i,j).

For the 1-st query, we have C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8, so the answer is their greatest common divisor, which is 2.

Sample Input 2

1 1
9
100
1 1 1 1

Sample Output 2

109