Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

• 1 \leq X,Y \leq 100
• X \neq Y
• All input values are integers.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

• S is a string of length 16 consisting of 0 and 1.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

• 1 \leq N, M \leq 1000
• N and M are integers.
• S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
• T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Sample Input 1

3 3
142857
004159
071028
159
287
857

Sample Output 1

2

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

5 4
235983
109467
823476
592801
000333
333
108
467
983

Sample Output 2

3

Sample Input 3

4 4
000000
123456
987111
000000
000
111
999
111

Sample Output 3

3

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:

• Invalidate the grades given by the N judges who gave the highest grades.
• Invalidate the grades given by the N judges who gave the lowest grades.
• Takahashi's score is defined as the average of the remaining 3N judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):

• Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
• Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
• Takahashi's score is defined as the average of the 3N elements remaining in S.

The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.

Constraints

• 1\leq N\leq 100
• 0\leq X_i\leq 100
• All values in the input are integers.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.

Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.

Problem Statement

You are given an integer sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Find how many pairs of integers (i,j)\ (1\le i\lt j\le N) satisfy j-i=A _ i+A _ j.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le A _ i\le2\times10 ^ 5\ (1\le i\le N)
• All input values are integers.

Sample Input 1

9
3 1 4 1 5 9 2 6 5

Sample Output 1

3

For example, when (i,j)=(4,7), we have j-i=7-4=3 and A _ i+A _ j=1+2=3, so j-i=A _ i+A _ j.

In contrast, when (i,j)=(3,8), we have j-i=8-3=5 and A _ i+A _ j=4+6=10, so j-i\ne A _ i+A _ j.

Only the three pairs (i,j)=(1,9),(2,4),(4,7) satisfy the condition, so output 3.

Sample Input 2

3
123456 123456 123456

Sample Output 2

0

There may be no pairs that satisfy the condition.

Sample Input 3

30
8 3 6 4 9 6 5 6 5 6 3 4 7 3 7 4 9 8 5 8 3 6 8 8 4 5 5 5 6 5

Sample Output 3

17

Problem Statement

There are N users on WAtCoder, numbered from 1 to N, and M contest pages, numbered from 1 to M. Initially, no user has view permission for any contest page.

You are given Q queries to process in order. Each query is of one of the following three types:

• 1 X Y: Grant user X view permission for contest page Y.
• 2 X: Grant user X view permission for all contest pages.
• 3 X Y: Answer whether user X can view contest page Y.

It is possible for a user to be granted permission for the same contest page multiple times.

Constraints

• 1 \le N \le 2\times 10^5
• 1 \le M \le 2\times 10^5
• 1 \le Q \le 2\times 10^5
• 1 \le X \le N
• 1 \le Y \le M
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
Yes
Yes

• In the first query, user 1 is granted permission to view contest page 2.
• At the second query, user 1 can view only page 2; they cannot view page 1, so print No.
• At the third query, user 1 can view page 2, so print Yes.
• In the fourth query, user 2 is granted permission to view all pages.
• At the fifth query, user 2 can view pages 1,2,3; they can view page 3, so print Yes.

Sample Input 2

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

Sample Output 2

No
No
No
Yes

Problem Statement

You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

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

Sample Input 1

4
1 5 4
7 8
6

Sample Output 1

13

If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.

It can be shown that this is the maximum achievable value.

Sample Input 2

3
1 2
3

Sample Output 2

3

N can be odd.

Sample Input 3

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

Sample Output 3

75

Story

There is a long water tank with boards of different heights placed at equal intervals. Takahashi wants to know the time at which water reaches each section separated by the boards when water is poured from one end of the tank.

Problem Statement

You are given a sequence of positive integers of length N: H=(H _ 1,H _ 2,\dotsc,H _ N).

There is a sequence of non-negative integers of length N+1: A=(A _ 0,A _ 1,\dotsc,A _ N). Initially, A _ 0=A _ 1=\dotsb=A _ N=0.

Perform the following operations repeatedly on A:

1. Increase the value of A _ 0 by 1.
2. For i=1,2,\ldots,N in this order, perform the following operation:
   • If A _ {i-1}\gt A _ i and A _ {i-1}\gt H _ i, decrease the value of A _ {i-1} by 1 and increase the value of A _ i by 1.

For each i=1,2,\ldots,N, find the number of operations before A _ i>0 holds for the first time.

Constraints

• 1\leq N\leq2\times10 ^ 5
• 1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

4 5 13 14 26

The first five operations go as follows.

Here, each row corresponds to one operation, with the leftmost column representing step 1 and the others representing step 2.

From this diagram, A _ 1\gt0 holds for the first time after the 4th operation, and A _ 2\gt0 holds for the first time after the 5th operation.

Similarly, the answers for A _ 3, A _ 4, A _ 5 are 13, 14, 26, respectively.

Therefore, you should print 4 5 13 14 26.

Sample Input 2

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

Note that the values to be output may not fit within a 32-bit integer.

Sample Input 3

15
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632

Sample Output 3

749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373

Problem Statement

You are given a string S consisting of digits and positive integers L and R for each of T test cases. Solve the following problem.

For a positive integer x, let us define f(x) as the number of contiguous substrings of the decimal representation of x (without leading zeros) that equal S.

For instance, if S= 22, we have f(122) = 1, f(123) = 0, f(226) = 1, and f(222) = 2.

Find \displaystyle \sum_{k=L}^{R} f(k).

Constraints

• 1 \le T \le 1000
• S is a string consisting of digits whose length is between 1 and 16, inclusive.
• L and R are integers satisfying 1 \le L \le R < 10^{16}.

Sample Input 1

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

Sample Output 1

12
0
14888888888888889
12982260572545
10987664021
1

This input contains six test cases.

• In the first test case, S= 22, L=23, R=234.
  • f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1.
  • f(222)=2.
  • Thus, the answer is 12.
• In the second test case, S= 0295, L=295, R=295.
  • Note that f(295)=0.