Problem Statement

There are four types of oysters, labeled 1, 2, 3, and 4. Exactly one of these types causes stomach trouble if eaten. The other types do not cause stomach trouble when eaten.

Takahashi ate oysters 1 and 2, and Aoki ate oysters 1 and 3. The information on whether each person got sick is given as two strings S_1 and S_2. Specifically, S_1 = sick means Takahashi got sick, and S_1 = fine means Takahashi did not get sick. Likewise, S_2 = sick means Aoki got sick, and S_2 = fine means Aoki did not get sick.

Based on the given information, find which type of oyster causes stomach trouble.

Constraints

• Each of S_1 and S_2 is sick or fine.

Sample Input 1

sick fine

Sample Output 1

2

Takahashi (who ate oysters 1 and 2) got sick, and Aoki (who ate oysters 1 and 3) did not get sick, so it can be concluded that oyster 2 causes stomach trouble.

Sample Input 2

fine fine

Sample Output 2

4

Neither Takahashi (who ate oysters 1 and 2) nor Aoki (who ate oysters 1 and 3) got sick, so it can be concluded that oyster 4 causes stomach trouble.

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 two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

Constraints

• S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

• 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
• |S| < i \leq |T|.
• |T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

• S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

abcde
abedc

Sample Output 1

3

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

6

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

0

S and T are equal, so print 0.

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Initially, nothing is placed on the grid.

You will now perform M operations. The i-th operation (1\leq i\leq M) is as follows:

• Place a block that occupies a 2 \times 2 region with cell (R_i,C_i) as the top-left corner on the grid if and only if its position does not overlap with any other blocks already placed. More precisely, for the set of cells S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace, if there exists a block already placed on the grid that occupies any cell in S, do nothing; otherwise, place a block that occupies all four cells in S.

After performing all operations, find how many blocks are placed on the grid.

Constraints

• 2\leq N \leq 10^9
• 1\leq M \leq 2\times 10^5
• 1\leq R_i,C_i \leq N-1
• All input values are integers.

Sample Input 1

4 3
1 1
2 2
2 3

Sample Output 1

2

The following diagram shows the operations, where black-filled regions represent blocks and red-framed regions represent where the next block is to be placed.

• Operation 1: Nothing is placed in the 2 \times 2 region with cell (1,1) as the top-left corner, so place a block there.
• Operation 2: Among the 2 \times 2 region with cell (2,2) as the top-left corner, there is already another block on cell (2,2), so do nothing.
• Operation 3: Nothing is placed in the 2 \times 2 region with cell (2,3) as the top-left corner, so place a block there.

Thus, after performing all operations, two blocks are placed on the grid.

Sample Input 2

1000000000 4
1 1
1 101
101 1
101 101

Sample Output 2

4

Blocks can be placed in all operations.

Sample Input 3

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

Sample Output 3

8

There may exist i,j\ (i\neq j) such that (R_i,C_i)=(R_j,C_j).

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

Snuke is observing a snake and is curious about which parts are the head, body, and tail. He divided the snake into N blocks and evaluated the head-likeness, body-likeness, and tail-likeness of each block. Then, he decided to find the division that maximizes the sum of the likeness values.

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

Find the maximum possible value of \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i for a pair of integers (x, y) satisfying 1 \leq x < y < N.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i, B_i, C_i \leq 10^6
• All input values are integers.

Sample Input 1

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

Sample Output 1

16

With (x, y) = (2, 3), we have \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16.

Sample Input 2

3
1 1 1
1 1 1
1 1 1

Sample Output 2

3

Sample Input 3

6
2 10 7 7 7 11
5 7 9 10 9 12
6 6 7 10 12 7

Sample Output 3

50

Problem Statement

We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.

• 1 \leq L \leq R \leq N
• The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq Y \leq X \leq 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair (L,R) satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that X=Y.

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

Problem Statement

There is a sequence A. Initially, A=(0). (That is, A is a sequence of length 1 containing 0 as its only element).

You are given Q queries to process in order. The i-th query (1\leq i\leq Q) has one of the following forms:

• 1 x: Insert i immediately after the location where x appears in A. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p such that A_p=x, update A to (A_1,\dots,A_p,i,A_{p+1},\dots,A_n). It is guaranteed that A contains x immediately before processing this query.
• 2 x y: Remove all elements between x and y in A, and output the sum of the values of the removed elements. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p and q such that A_p=x and A_q=y, output A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1} and update A to (A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n). It is guaranteed that A contains both x and y immediately before processing this query.

Note that for any sequence of queries, the same value never appears multiple times in A during the process of handling queries, and thus the position where a value appears in A is unique (if it exists).

Constraints

• 1\leq Q \leq 5\times 10^5
• For the i-th query:
  • If it is a type 1 query:
    • 0\leq x < i
    • A contains x immediately before processing the query.
  • If it is a type 2 query:
    • 0\leq x < y < i
    • A contains both x and y immediately before processing the query.
• All input values are integers.

Sample Input 1

6
1 0
1 1
1 0
2 2 3
1 2
2 0 5

Sample Output 1

1
5

Initially, A=(0).

• 1st query: Insert 1 immediately after 0. A becomes (0,1).
• 2nd query: Insert 2 immediately after 1. A becomes (0,1,2).
• 3rd query: Insert 3 immediately after 0. A becomes (0,3,1,2).
• 4th query: Remove the elements between 2 and 3, namely 1, and output the sum of the removed values, which is 1. A becomes (0,3,2).
• 5th query: Insert 5 immediately after 2. A becomes (0,3,2,5).
• 6th query: Remove the elements between 0 and 5, namely 3,2, and output the sum of the removed values, which is 5. A becomes (0,5).

Sample Input 2

2
1 0
2 0 1

Sample Output 2

0

In the 2nd query, we remove all elements between 0 and 1, but there are actually no such elements, so no elements are removed and the output value is 0.

Sample Input 3

10
1 0
1 1
2 0 2
2 0 2
1 0
1 5
2 0 5
2 2 6
1 6
1 9

Sample Output 3

1
0
0
0