Problem Statement

Takahashi set task goals for N days.

He aimed to complete A_i tasks on day i (1 \leq i \leq N), and actually completed B_i tasks.

Find the number of days when he completed more tasks than his goal.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i, B_i \leq 100
• All input values are integers.

Sample Input 1

4
2 8
5 5
5 4
6 7

Sample Output 1

2

Takahashi completed more tasks than his goal on the 1st and 4th days.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

3

Problem Statement

You are given the name S of a certain person. The first character of S is an uppercase English letter, and the other characters are lowercase English letters.

The name of this person's handmaid is the string obtained by converting the first letter of S to lowercase and adding Of to the beginning. Find the name of this handmaid.

Constraints

• S is a string of length between 1 and 10, inclusive.
• The first character of S is an uppercase English letter.
• The characters of S other than the first are lowercase English letters.

Sample Input 1

Glen

Sample Output 1

Ofglen

Converting the first letter of Glen to lowercase gives glen, and adding Of to the beginning gives Ofglen.

Sample Input 2

I

Sample Output 2

Ofi

Sample Input 3

Fred

Sample Output 3

Offred

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

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

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

• a
• y
• ay
• ya
• yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54

Problem Statement

There are N people standing in a line. The person standing at the i-th position from the front is person P_i.

Process Q queries. The i-th query is as follows:

• You are given integers A_i and B_i. Between person A_i and person B_i, print the person number of the person standing further to the front.

Constraints

• All inputs are integers.
• 1 \leq N \leq 100
• 1 \leq P_i \leq N
• P_i \neq P_j\ (i \neq j)
• 1 \leq Q \leq 100
• 1 \leq A_i < B_i \leq N

Sample Input 1

3
2 1 3
3
2 3
1 2
1 3

Sample Output 1

2
2
1

In the first query, person 2 is at the first position from the front, and person 3 is at the third position, so person 2 is further to the front.

In the second query, person 1 is at the second position from the front, and person 2 is at the first position, so person 2 is further to the front.

In the third query, person 1 is at the second position from the front, and person 3 is at the third position, so person 1 is further to the front.

Sample Input 2

7
3 7 2 1 6 5 4
13
2 3
1 2
1 3
3 6
3 7
2 4
3 7
1 3
4 7
1 6
2 4
1 3
1 3

Sample Output 2

3
2
3
3
3
2
3
3
7
1
2
3
3

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

• 1 \leq N \leq 5 \times 10^5
• |A_i| \leq 10^9 (i=1,2,\dots,N)
• |B_j| \leq 10^9 (j=1,2,\dots,N)
• All input values are integers.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33

Problem Statement

Takahashi is at coordinate 0.5 on a number line.

He will make N moves.
In the i-th move, he chooses either the positive direction or the negative direction, and moves L_i in that direction.

What is the maximum number of times he can pass through coordinate 0?
Under the constraints of this problem, no move will end at coordinate 0.

Constraints

• 1 \le N \le 20
• 1 \le L_i \le 10^9
• All input values are integers.

Sample Input 1

5
2 5 2 2 1

Sample Output 1

4

For example, by choosing the directions of movement as follows, he can pass through coordinate 0 four times, which is the maximum.

• In the first move, choose the negative direction and move 2. He moves from coordinate 0.5 to -1.5, passing through coordinate 0.
• In the second move, choose the positive direction and move 5. He moves from coordinate -1.5 to 3.5, passing through coordinate 0.
• In the third move, choose the negative direction and move 2. He moves from coordinate 3.5 to 1.5.
• In the fourth move, choose the negative direction and move 2. He moves from coordinate 1.5 to -0.5, passing through coordinate 0.
• In the fifth move, choose the positive direction and move 1. He moves from coordinate -0.5 to 0.5, passing through coordinate 0.

Sample Input 2

5
100 1 2 3 4

Sample Output 2

1

Sample Input 3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

20

Problem Statement

You are given a string S consisting of a, b, c.

Find the number of non-empty subsequences of S in which no two adjacent characters are the same, modulo 998244353.

Two subsequences are considered distinct if they are taken from different positions, even if they are identical as strings.

Constraints

• S is a string of length between 1 and 3 \times 10^5, inclusive, consisting of a, b, c.

Sample Input 1

abbc

Sample Output 1

11

The subsequences in which no two adjacent characters are the same are the following 11:

• a (the 1st character of S)
• b (the 2nd character of S)
• b (the 3rd character of S)
• c (the 4th character of S)
• ab (the 1st, 2nd characters of S)
• ab (the 1st, 3rd characters of S)
• ac (the 1st, 4th characters of S)
• bc (the 2nd, 4th characters of S)
• bc (the 3rd, 4th characters of S)
• abc (the 1st, 2nd, 4th characters of S)
• abc (the 1st, 3rd, 4th characters of S)

Note that, as with the 2nd and 3rd entries, two subsequences are considered distinct if they are taken from different positions, even if they are identical as strings.

Sample Input 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

Sample Output 2

378217423

Output the count modulo 998244353.

Problem Statement

We have an integer sequence A and a notebook. The notebook has 10^9 pages.

You are given Q queries. Each query is of one of the following four kinds:

ADD x: append an integer x to the tail of A.

DELETE: remove the last term of A if A is not empty; do nothing otherwise.

SAVE y: erase the sequence recorded on the y-th page of the notebook, and record the current A onto the y-th page.

LOAD z: replace A with the sequence recorded on the z-th page of the notebook.

Initially, A is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process Q queries successively in the given order and print the last term of A after processing each query.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• 1 \leq Q \leq 5 \times 10^5
• 1 \leq x, y, z \leq 10^9
• Q, x, y, and z are integers.
• Each of the given queries is of one of the four kinds in the Problem Statement.

Sample Input 1

11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

Sample Output 1

3 3 4 4 3 -1 -1 4 4 -1 4

Initially, A is an empty sequence, so A = (), and an empty sequence is recorded on each page of the notebook.

• By the 1-st query, 3 is appended to the tail of A, resulting in A = (3).
• By the 2-nd query, the sequence recorded on the 1-st page of the notebook becomes (3). It remains that A = (3).
• By the 3-rd query, 4 is appended to the tail of A, resulting in A = (3, 4).
• By the 4-th query, the sequence recorded on the 2-nd page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 5-th query, A is replaced by (3), which is recorded on the 1-st page of the notebook, resulting in A = (3).
• By the 6-th query, the last term of A is removed, resulting in A = ().
• By the 7-th query, nothing happens because A is already empty. It remains that A = ().
• By the 8-th query, A is replaced by (3,4), which is recorded on the 2-nd page of the notebook, resulting in A = (3, 4).
• By the 9-th query, the sequence recorded on the 1-st page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 10-th query, A is replaced by (), which is recorded on the 3-rd page of the notebook, resulting in A = ().
• By the 11-th query, A is replaced by (3, 4), which is recorded on the 1-st page of the notebook, resulting in A = (3, 4).

Sample Input 2

21
ADD 4
ADD 3
DELETE
ADD 10
LOAD 7
SAVE 5
SAVE 5
ADD 4
ADD 4
ADD 5
SAVE 5
ADD 2
DELETE
ADD 1
SAVE 5
ADD 7
ADD 8
DELETE
ADD 4
DELETE
LOAD 5

Sample Output 2

4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1

Problem Statement

There is an N\times N grid. Let cell (i,j) denote the cell in the i-th row from the top and j-th column from the left. Each cell contains a digit from 1 to 9; cell (i,j) contains A_{i,j}.

Initially, a token is on cell (1,1). Let S be an empty string. Repeat the following operation 2N-1 times:

• Append to the end of S the digit in the current cell.
• Move the token one cell down or one cell to the right. However, do not move it in the (2N-1)-th operation.

After 2N-1 operations, the token is on cell (N,N) and the length of S is 2N-1.

Interpret S as an integer. The score is the remainder when this integer is divided by M.

Find the maximum achievable score.

Constraints

• 1 \leq N \leq 20
• 2 \leq M \leq 10^9
• 1 \leq A_{i,j} \leq 9
• All input values are integers.

Sample Input 1

2 7
1 2
3 1

Sample Output 1

5

There are two ways to move the token:

• Move through (1,1),(1,2),(2,2). Then S= 121, and the score is the remainder when 121 is divided by 7, which is 2.
• Move through (1,1),(2,1),(2,2). Then S= 131, and the score is the remainder when 131 is divided by 7, which is 5.

The maximum score is 5, so print 5.

Sample Input 2

3 100000
1 2 3
3 5 8
7 1 2

Sample Output 2

13712

Sample Input 3

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

Sample Output 3

384