Problem Statement

You are given a string S consisting of lowercase English letters and |. S is guaranteed to contain exactly two |s.

Remove the characters between the two |s, including the |s themselves, and print the resulting string.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and |.
• S contains exactly two |s.

Sample Input 1

atcoder|beginner|contest

Sample Output 1

atcodercontest

Remove all the characters between the two |s and print the result.

Sample Input 2

|spoiler|

Sample Output 2

It is possible that all characters are removed.

Sample Input 3

||xyz

Sample Output 3

xyz

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

• 1 \leq N,M,L \leq 100
• 0 \leq A_i, B_i ,C_i \leq 10^8
• 1 \leq Q \leq 2\times 10^5
• 0 \leq X_i \leq 3\times 10^8
• All input values are integers.

Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No

• It is impossible to select one element from each of A, B, and C so that their sum is 1.
• Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
• Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
• It is impossible to select one element from each of A, B, and C so that their sum is 50.

Problem Statement

You initially have an empty string S.
Additionally, there are bags 1, 2, \dots, N, each containing some strings.
Bag i contains A_i strings S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.

You will repeat the following steps for i = 1, 2, \dots, N:

• Choose and perform one of the following two actions:
  • Pay 1 yen, select exactly one string from bag i, and concatenate it to the end of S.
  • Do nothing.

Given a string T, find the minimum amount of money required to make the final S equal T.
If there is no way to make the final S equal T, print -1.

Constraints

• T is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• N is an integer between 1 and 100, inclusive.
• A_i is an integer between 1 and 10, inclusive.
• S_{i,j} is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final S equal T with two yen, which can be shown to be the minimum amount required.

• For i=1, select abc from bag 1 and concatenate it to the end of S, making S= abc.
• For i=2, do nothing.
• For i=3, select de from bag 3 and concatenate it to the end of S, making S= abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final S equal T, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. The elements of A are distinct.

Process Q queries in the order they are given. Each query is of one of the following two types:

• 1 x y : Insert y immediately after the element x in A. It is guaranteed that x exists in A when this query is given.
• 2 x : Remove the element x from A. It is guaranteed that x exists in A when this query is given.

It is guaranteed that after processing each query, A will not be empty, and its elements will be distinct.

Print A after processing all the queries.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i \neq A_j
• For queries of the first type, 1 \leq x,y \leq 10^9.
• When a query of the first type is given, x exists in A.
• For queries of the second type, 1 \leq x \leq 10^9.
• When a query of the second type is given, x exists in A.
• After processing each query, A is not empty, and its elements are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4 5 1 3

The queries are processed as follows:

• Initially, A=(2,1,4,3).
• The first query removes 1, making A=(2,4,3).
• The second query inserts 5 immediately after 4, making A=(2,4,5,3).
• The third query removes 2, making A=(4,5,3).
• The fourth query inserts 1 immediately after 5, making A=(4,5,1,3).

Sample Input 2

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

Sample Output 2

5 1 7 2 3

Problem Statement

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

Takahashi is initially at square (1,1) with zero money.

When Takahashi is at square (i,j), he can perform one of the following in one action:

• Stay at the same square and increase his money by P_{i,j}.
• Pay R_{i,j} from his money and move to square (i,j+1).
• Pay D_{i,j} from his money and move to square (i+1,j).

He cannot make a move that would make his money negative or take him outside the grid.

If Takahashi acts optimally, how many actions does he need to reach square (N,N)?

Constraints

• 2 \leq N \leq 80
• 1 \leq P_{i,j} \leq 10^9
• 1 \leq R_{i,j},D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

It is possible to reach square (3,3) in eight actions as follows:

• Stay at square (1,1) and increase money by 1. His money is now 1.
• Pay 1 money and move to square (2,1). His money is now 0.
• Stay at square (2,1) and increase money by 3. His money is now 3.
• Stay at square (2,1) and increase money by 3. His money is now 6.
• Stay at square (2,1) and increase money by 3. His money is now 9.
• Pay 4 money and move to square (2,2). His money is now 5.
• Pay 3 money and move to square (3,2). His money is now 2.
• Pay 2 money and move to square (3,3). His money is now 0.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Sample Output 2

4000000004

Problem Statement

Pay attention to the special input format.

There are N points (X_i,Y_i) in the xy-plane. You are given these points in the input.

Also, Q pairs of integers (A_j,B_j) are given.
Define f(A_j,B_j) as the number of indices i satisfying Y_i \ge A_j \times X_i + B_j.

Find \displaystyle \sum^{Q}_{j=1} f(A_j,B_j).

Here, Q gets very large, so (A_j,B_j) are not given directly.
Instead, G_0, R_a, and R_b are given, and (A_j,B_j) are generated as follows:

• First, for n \ge 0, define G_{n+1} = (48271 \times G_n) \mod (2^{31}-1).
• For j=1,2,\dots,Q, generate (A_j,B_j) as follows:
  • A_j = -R_a + (G_{3j - 2} \mod (2 \times R_a + 1) )
  • B_j = -R_b + ((G_{3j - 1} \times (2^{31}-1) + G_{3 j}) \mod (2 \times R_b + 1) )

From this method, it can be shown that A_j and B_j satisfy the following constraints:

• -R_a \le A_j \le R_a
• -R_b \le B_j \le R_b

Constraints

• All input values are integers.
• 1 \le N \le 5000
• 1 \le Q \le 10^7
• |X_i|, |Y_i| \le 10^8
• The pairs (X_i,Y_i) are distinct.
• 0 \le G_0 < (2^{31}-1)
• 0 \le R_a \le 10^8
• 0 \le R_b \le 10^{16}

Sample Input 1

7
2 -2
-1 -2
0 1
2 1
-2 2
1 2
0 -1
10
1 5 5

Sample Output 1

36

This input contains ten questions.
The generated (A_j,B_j) are (-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2).