Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N) and an integer X.
For i=1,2,\dots,N in this order, do the following.

• If A_i<X, update X=A_i and output 1.
• Otherwise, output 0.

Constraints

• All input values are integers.
• 1 \le N,X,A_i \le 100

Sample Input 1

5 10
6 4 7 1 3

Sample Output 1

1
1
0
1
0

• Initially, X=10.
• For i=1: since A_1=6<X=10, update X=6 and output 1.
• For i=2: since A_2=4<X=6, update X=4 and output 1.
• For i=3: since A_3=7 \ge X=4, output 0.
• For i=4: since A_4=1<X=4, update X=1 and output 1.
• For i=5: since A_5=3 \ge X=1, output 0.

Sample Input 2

1 1
1

Sample Output 2

0

Sample Input 3

8 20
9 19 14 17 17 4 18 4

Sample Output 3

1
0
0
0
0
1
0
0

Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

• 2 \le |S| \le 20
• S consists of lowercase English letters.
• S ends with er or ist.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 1000
• All input values are integers.
• The lost integer is uniquely determined.

Sample Input 1

3
2 3 5

Sample Output 1

4

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

7

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

151

Problem Statement

You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query (1\le i\le Q) is described as follows:

You are given a character c_i and integers X_i,V_i. If c_i= A, change A_{X_i} to V_i; if c_i= B, change B_{X_i} to V_i. Then, output \displaystyle \sum_{k=1}^N \min(A_k,B_k).

Constraints

• 1\le N,Q \le 2 \times 10^5
• 1\le A_i,B_i \le 10^9
• c_i is either A or B.
• 1\le X_i \le N
• 1\le V_i \le 10^9
• All input values are integers.

Sample Input 1

4 3
3 1 4 1
2 7 1 8
A 2 3
B 3 3
A 1 7

Sample Output 1

7
9
9

After the 1st query, A=(3,3,4,1),B=(2,7,1,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 on the 1st line.

After the 2nd query, A=(3,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 2nd line.

After the 3rd query, A=(7,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 3rd line.

Sample Input 2

1 3
1
1000000000
A 1 1
A 1 1
A 1 1

Sample Output 2

1
1
1

Sample Input 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3

421
420
420

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 a maze consisting of a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. The type of cell (i,j) is given as a character S_{i,j}, where each character has the following meaning:

• . : Empty cell
• # : Obstacle cell
• Lowercase English letter (a - z): Warp cell

In the maze, you can perform the following two types of actions any number of times in any order:

• Walk: Move from the current cell to a cell that is one cell away in one of the four directions (up, down, left, right). However, you cannot move to an obstacle cell or outside the grid.
• Warp: When you are at a warp cell, move to any warp cell with the same character written on it.

Determine whether it is possible to move from cell (1,1) to cell (H,W), and if possible, find the minimum total number of actions required.

Constraints

• 1\leq H,W \leq 1000
• H\times W \geq 2
• H and W are integers.
• S_{i,j} is ., #, or a lowercase English letter.
• S_{1,1}\neq #
• S_{H,W}\neq #

Sample Input 1

3 4
..a.
####
ba#b

Sample Output 1

5

You can move from cell (1,1) to cell (3,4) by performing actions as follows:

1. Move from cell (1,1) to cell (1,2) by walking.
2. Move from cell (1,2) to cell (1,3) by walking.
3. Move from cell (1,3) to cell (3,2) by warping.
4. Move from cell (3,2) to cell (3,1) by walking.
5. Move from cell (3,1) to cell (3,4) by warping.

The total number of actions is 5, which is the minimum.

Sample Input 2

3 4
..a.
####
b.#b

Sample Output 2

-1

It is impossible to move from cell (1,1) to cell (3,4).

Sample Input 3

4 4
xxxx
xxxx
xxxx
xxxx

Sample Output 3

1

Sample Input 4

7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.

Sample Output 4

12

Problem Statement

Aoki, an employee at AtCoder Inc., has his salary for this month determined by an integer N and a sequence A of length N as follows.
First, he is given an N-sided die (dice) that shows the integers from 1 to N with equal probability, and a variable x=0.

Then, the following steps are repeated until terminated.

• Roll the die once and let y be the result.
  • If x<y, pay him A_y yen and let x=y.
  • Otherwise, terminate the process.

Aoki's salary for this month is the total amount paid through this process.
Find the expected value of Aoki's salary this month, modulo 998244353.

Constraints

• All inputs are integers.
• 1 \le N \le 3 \times 10^5
• 0 \le A_i < 998244353

Sample Input 1

3
3 2 6

Sample Output 1

776412280

Here is an example of how the process goes.

• Initially, x=0.
• Roll the die once, and it shows 1. Since 0<1, pay him A_1 = 3 yen and let x=1.
• Roll the die once, and it shows 3. Since 1<3, pay him A_3 = 6 yen and let x=3.
• Roll the die once, and it shows 1. Since 3 \ge 1, terminate the process.

In this case, his salary for this month is 9 yen.

It can be calculated that the expected value of his salary this month is \frac{49}{9} yen, whose representation modulo 998244353 is 776412280.

Sample Input 2

1
998244352

Sample Output 2

998244352

Sample Input 3

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

Sample Output 3

545252774

Problem Statement

On a circle, 2N points are placed at equal intervals and numbered 1,2,\dots,2N in clockwise order starting from an arbitrary point.

There are M line segments numbered 1,2,\dots,M connecting these points. Segment i connects points A_i and B_i. Here, A_i and B_i are distinct even numbers. It is guaranteed that no two of these segments share a point.

Process Q queries. The j‑th query is as follows:

• You are given two distinct odd numbers C_j and D_j. Among the M segments 1,2,\dots,M, find how many share a point with the segment connecting points C_j and D_j.

Constraints

• 2 \le N \le 10^6
• 1\leq M \leq \min\left(\lfloor\frac{N}{2}\rfloor, 2\times 10^5\right)
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i < B_i \le 2N
• 1 \le C_j < D_j \le 2N
• A_i and B_i are even.
• C_j and D_j are odd.
• For any i_1 and i_2 (i_1 \neq i_2), segments i_1 and i_2 do not share a point.
• All input values are integers.

Sample Input 1

4 2
2 4
6 8
3
1 3
3 7
1 5

Sample Output 1

1
2
0

The figure above illustrates Sample Input 1. Black dots are the 2N\ (=8) points, blue solid lines are the initial M\ (=2) segments, and red dashed lines are the Q\ (=3) query segments.

• For the first query, the segment connecting points 1 and 3 intersects one initial segment: segment 1.
• For the second query, the segment connecting points 3 and 7 intersects two initial segments: segments 1 and 2.
• For the third query, the segment connecting points 1 and 5 intersects zero initial segments.

Sample Input 2

20 7
24 34
26 28
18 38
2 14
8 12
30 32
20 22
10
7 29
31 39
9 21
19 29
15 21
11 39
17 21
15 31
5 25
25 31

Sample Output 2

3
3
4
1
2
2
2
3
3
1