Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

• X and Y are integers.
• 1 \le X,Y \le 1000

Sample Input 1

80 94

Sample Output 1

2

• After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
• After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
• After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.

Sample Input 3

270 750

Sample Output 3

48

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N in this order.

Print S_N,S_{N-1},\ldots,S_1 in this order.

Constraints

• 1\leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.

Sample Input 1

3
Takahashi
Aoki
Snuke

Sample Output 1

Snuke
Aoki
Takahashi

We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.

Thus, you should print Snuke, Aoki, and Takahashi in this order.

Sample Input 2

4
2023
Year
New
Happy

Sample Output 2

Happy
New
Year
2023

The given strings may contain digits.

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
• For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
• All values in input are integers.

Sample Input 1

3
1 3 2 3 3 2 2 1 1 1 2

Sample Output 1

3

Takahashi removed a card with 3 written on it.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

2

Problem Statement

There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

• We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

• 1 \leq N \leq 300
• 1 \leq W \leq 10^6
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

• N is an integer between 1 and 2\times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters, ,, and ".
• S contains an even number of ".

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

• 4 \leq N \leq 2000
• 0 \leq x_i, y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

1

Problem Statement

You are given a sequence of N-1 integers S = (S_1, S_2, \ldots, S_{N-1}), and M distinct integers X_1, X_2, \ldots, X_M, which are called lucky numbers.

A sequence of N integers A = (A_1, A_2, \ldots, A_N) satisfying the following condition is called a good sequence.

A_i + A_{i+1} = S_i holds for every i = 1, 2, \ldots, N-1.

Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10
• -10^9 \leq S_i \leq 10^9
• -10^9 \leq X_i \leq 10^9
• X_1 \lt X_2 \lt \cdots \lt X_M
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

A good sequence A = (3, -1, 4, -1, 5, -9, 2, -6, 5) contains four terms that are lucky numbers: A_2, A_4, A_5, A_9, which is the maximum possible count.

Sample Input 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

Sample Output 2

8

Problem Statement

There are N cities numbered 1 through N, and M buses that go between these cities. The i-th bus (1 \leq i \leq M) departs from City A_i at time S_i+0.5 and arrive at City B_i at time T_i+0.5.

Takahashi will travel between these N cities. When he is in City p at time t, he will do the following.

1. If there is a bus that departs from City p not earlier than time t, take the bus that departs the earliest among those buses to get to another city.
2. If there is no such bus, do nothing and stay in City p.

Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all M buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.

Here is your task: process Q queries, the i-th (1 \leq i \leq Q) of which is as follows.

• If Takahashi begins his travel in City Y_i at time X_i, in which city or on which bus will he be at time Z_i?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)
• A_i \neq B_i\ (1 \leq i \leq M)
• 1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)
• S_i \neq S_j\ (i \neq j)
• 1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)
• 1 \leq Y_i \leq N\ (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2 3
2
3

In the first query, Takahashi will travel as follows.

1. Start in City 1 at time 1.
2. Take the bus that departs from City 1 at time 1.5 and arrives at City 2 at time 3.5.
3. Take the bus that departs from City 2 at time 3.5 and arrives at City 3 at time 5.5.
4. Since no bus departs from City 3 at time 5.5 or later, stay in City 3 (forever).

At time 5, he will be on the bus that departs from City 2 and arrives at City 3. Thus, as specified in the Output section, we should print 2 and 3 with a space between them.

Sample Input 2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

Sample Output 2

4
6 1
4 1
8
6 1
1
2
2
7 2
1