Problem Statement

You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.

Constraints

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

Sample Input 1

AtCoderBeginnerContest

Sample Output 1

ACBC

The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.

Sample Input 2

PaymentRequired

Sample Output 2

PR

Sample Input 3

program

Sample Output 3

Note that S may contain no uppercase letters.

Problem Statement

Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 X: One person joins the end of the waiting line holding a ticket with menu number X.
• 2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.

Constraints

• 1 \leq Q \leq 100
• 1 \leq X \leq 100
• For each query of the second type, there is at least one person in the line before guiding.
• All input values are integers.

Sample Input 1

6
1 3
1 1
1 15
2
1 3
2

Sample Output 1

3
1

Initially, the waiting line is empty.

• For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
• For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
• For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
• For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
• For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
• For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.

Sample Input 2

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

Sample Output 2

Note that there may be no queries of the second type.

Problem Statement

The AtCoder Restaurant uses N types of ingredients numbered from 1 to N.

The restaurant offers M dishes numbered from 1 to M. Dish i uses K_i types of ingredients, namely A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

Snuke currently dislikes all N ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.

Over the next N days, he will overcome his dislikes one ingredient per day. On day i, he overcomes ingredient B_i, and from then on he no longer dislikes it.

For each i=1,2,\ldots,N, find:

• the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient B_i on day i.

Constraints

• 1 \leq N \leq 3 \times 10^{5}
• 1 \leq M \leq 3 \times 10^{5}
• 1 \leq K_i \leq N (1 \leq i \leq M)
• The sum of K_i is at most 3 \times 10^{5}.
• 1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
• A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
• 1 \leq B_i \leq N (1 \leq i \leq N)
• B_i \neq B_j (i \neq j )
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
2
3
4

Snuke overcomes his disliked ingredients as follows:

• Day 1: He overcomes ingredient 1. At this time, every dish still uses a disliked ingredient, so print 0.
• Day 2: He overcomes ingredient 3. Dish 4 no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print 1.
• Day 3: He overcomes ingredient 2. Dish 1 no longer uses any disliked ingredient and becomes edible; all dishes except 1 and 4 still use disliked ingredients, so print 2.
• Day 4: He overcomes ingredient 5. Dish 3 no longer uses any disliked ingredient and becomes edible; all dishes except 1, 3, and 4 still use disliked ingredients, so print 3.
• Day 5: He overcomes ingredient 4. Dish 2 no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print 4.

Sample Input 2

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

Sample Output 2

0
0
1
1
1
2
4
6
8

Problem Statement

There are N equally spaced points on a circle labeled clockwise as 1,2,\ldots,N.

There are M distinct lines, where the i-th line passes through two distinct points A_i and B_i (1 \leq i \leq M).

Find the number of pairs (i,j) satisfying:

• 1 \le i < j \le M, and
• the i-th and j-th lines intersect.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq M \leq 3 \times 10^{5}
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• All input values are integers.

Sample Input 1

8 3
1 5
1 8
2 4

Sample Output 1

2

As shown in the diagram below, there are eight points and three lines on the circle.

The 1st and 2nd lines intersect. The 1st and 3rd lines do not intersect. The 2nd and 3rd lines intersect. Since the pairs (i,j)=(1,2),(2,3) satisfy the conditions, print 2.

Sample Input 2

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

Sample Output 2

40

Problem Statement

In the year 30XX, each submission to a certain contest requires a payment.

The contest has N problems. Problem i has S_i points, and each submission costs C_i yen.

When Takahashi submits to the i-th problem, he solves it with probability P_i %. Each submission’s outcome is independent of the others.

He has X yen. He cannot make any submission that would cause his total spending to exceed X yen.

Find the expected value of the total score of the problems he solves when he chooses submissions to maximize this value.

He may decide which problem to submit to next after seeing the result of the previous submission, and solving the same problem more than once awards the same score as solving it once.

Constraints

• 1 \leq N \leq 8
• 1 \leq S_i \leq 2718
• 1 \leq C_i \leq X \leq 5000
• 1 \leq P_i \leq 100
• All input values are integers.

Sample Input 1

3 2
100 1 50
200 1 20
1000 1 1

Sample Output 1

95

Consider the following submission strategy:

• First, submit to the 1st problem.
• If that submission is correct, submit to the 2nd problem; otherwise, submit again to the 1st problem.

The expected total score for this strategy is 95 points. No strategy can exceed an expected score of 95, so print 95.

Sample Input 2

2 7
100 3 50
100 2 50

Sample Output 2

125

Sample Input 3

5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69

Sample Output 3

953.976967020096

Sample Input 4

7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1

Sample Output 4

1976.2441416041121021

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

Problem Statement

You are given integers N,M,A,B_1,B_2.

Find \displaystyle\sum_{k=0}^{N-1}\left\lbrace (Ak+B_1)\ \text{mod}\ M \right\rbrace\left\lbrace (Ak+B_2)\ \text{mod}\ M \right\rbrace.

There are T test cases; solve each one.

Constraints

• 1\le T\le 10^5
• 1\le N\le 10^6
• 1\le M\le 10^6
• 0\le A,B_1,B_2 < M
• All input values are integers.

Sample Input 1

5
4 7 2 1 4
12 15 2 8 7
777 1 0 0 0
100 101 0 100 100
402 402 4 19 256

Sample Output 1

27
866
0
1000000
13728568

Consider the first test case.

• When k=0: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=1,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=4.
• When k=1: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=3,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=6.
• When k=2: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=5,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=1.
• When k=3: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=0,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=3.

Hence, the required value is 1\times 4+3\times 6+5\times 1+0\times 3=27. Thus, print 27 on the first line.