Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N) and an integer X.
For i=1,2,\dots,N in this order, do the following.

• If A_i<X, update X=A_i and output 1.
• Otherwise, output 0.

Constraints

• All input values are integers.
• 1 \le N,X,A_i \le 100

Sample Input 1

5 10
6 4 7 1 3

Sample Output 1

1
1
0
1
0

• Initially, X=10.
• For i=1: since A_1=6<X=10, update X=6 and output 1.
• For i=2: since A_2=4<X=6, update X=4 and output 1.
• For i=3: since A_3=7 \ge X=4, output 0.
• For i=4: since A_4=1<X=4, update X=1 and output 1.
• For i=5: since A_5=3 \ge X=1, output 0.

Sample Input 2

1 1
1

Sample Output 2

0

Sample Input 3

8 20
9 19 14 17 17 4 18 4

Sample Output 3

1
0
0
0
0
1
0
0

Problem Statement

Takahashi is wearing armor.

This armor blocks all attacks with power (strength represented as an integer) of D or less, but does not block attacks with power greater than D.

Does this armor block an attack with power A?

Constraints

• 1 \leq A \leq 100
• 1 \leq D \leq 100
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In this sample, A = 4 and D = 5. Since A = 4 is at most D = 5, the armor blocks the attack, so the answer is Yes.

Sample Input 2

5 5

Sample Output 2

Yes

In this sample, A = 5 and D = 5. Since A = 5 is at most D = 5, the armor blocks the attack, so the answer is Yes.

Sample Input 3

6 5

Sample Output 3

No

In this sample, A = 6 and D = 5. Since A = 6 is not at most D = 5, the armor does not block the attack, so the answer is No.

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

• A_i is 0 or 1.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

13

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

Problem Statement

There is a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i, j).

Cells (x_1, y_1) and (x_2, y_2) are said to be edge-adjacent when |x_1 - x_2| + |y_1 - y_2| = 1.

For every cell, find the number of cells that are edge-adjacent to it.

Constraints

• 1 \leq H, W \leq 50
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

2 3 3 3 2
3 4 4 4 3
3 4 4 4 3
2 3 3 3 2

The cells edge-adjacent to cell (1, 5) are cells (1, 4), (2, 5), for a total of two cells.

The cells edge-adjacent to cell (2, 3) are cells (1, 3), (2, 2), (2, 4), (3, 3), for a total of four cells.

The cells edge-adjacent to cell (4, 2) are cells (3, 2), (4, 1), (4, 3), for a total of three cells.

Sample Input 2

1 1

Sample Output 2

0

There are no cells edge-adjacent to cell (1, 1).

Sample Input 3

12 8

Sample Output 3

2 3 3 3 3 3 3 2
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
2 3 3 3 3 3 3 2

Problem Statement

You are given an integer N. Consider permuting the digits in N and separate them into two positive integers.

For example, for the integer 123, there are six ways to separate it, as follows:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer 101 into 1 and 01. Additionally, since the resulting integers must be positive, it is not allowed to separate 101 into 11 and 0, either.

What is the maximum possible product of the two resulting integers, obtained by the optimal separation?

Constraints

• N is an integer between 1 and 10^9 (inclusive).
• N contains two or more digits that are not 0.

Sample Input 1

123

Sample Output 1

63

As described in Problem Statement, there are six ways to separate it:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

The products of these pairs, in this order, are 36, 63, 26, 62, 23, 32, with 63 being the maximum.

Sample Input 2

1010

Sample Output 2

100

There are two ways to separate it:

• 100 and 1,
• 10 and 10.

In either case, the product is 100.

Sample Input 3

998244353

Sample Output 3

939337176

Problem Statement

Currently, there are N Takahashi in a conference room. The i-th (1\le i\le N) Takahashi has a height of H _ i and will leave the room L _ i minutes from now. Once a Takahashi leaves the room, he never returns.

You are given Q queries, so answer them in order. For the i-th (1\le i\le Q) query, you are given an integer T _ i, so find the maximum height among the Takahashi who are in the room T _ i+\dfrac12 minutes from now. Under the constraints of this problem, it is guaranteed that at least one Takahashi will be in the room T _ i+\dfrac12 minutes from now.

Constraints

• 1\le N\le3\times10 ^ 5
• 1\le H _ i\le10 ^ 9\ (1\le i\le N)
• 1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9
• 1\le Q\le3\times10 ^ 5
• 0\le T _ i\lt L _ N\ (1\le i\le Q)
• All input values are integers.

Sample Input 1

4
31 4
26 5
3 5
15 9
4
3 4 5 6

Sample Output 1

31
26
15
15

3+\dfrac12 minutes from now, all Takahashi currently in the room are still there. Thus, the answer to the first query is 31, the maximum of \lbrace31,26,3,15\rbrace.

5+\dfrac12 minutes from now, only the fourth Takahashi is in the room. Thus, the answer to the third query is 15, the maximum of \lbrace15\rbrace.

Sample Input 2

10
587 138
772 155
755 404
519 408
529 432
169 586
114 632
249 656
329 972
299 984
14
443 801 824 276 399 314 300 510 311 580 498 930 359 5

Sample Output 2

329
329
329
755
755
755
755
329
755
329
329
329
755
772

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (i,j,k) that satisfy all of the following:

• 1 \le i,j,k \le N
• A_i : A_j : A_k = 7:5:3
• \min(i,j,k) = j or \max(i,j,k) = j.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

10
3 10 7 10 7 6 7 6 5 14

Sample Output 1

7

The seven triples of integers (i,j,k) that satisfy the conditions are:

• (3,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (5,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (7,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (10,2,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,2,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.

Sample Input 2

6
210 210 210 210 210 210

Sample Output 2

0

Sample Input 3

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

Sample Output 3

34

Problem Statement

There are two multisets of strings, X and Y, both initially empty.

You are given Q queries to process in order. In the i-th query, you receive an integer T_i and a string S_i. If T_i=1, insert S_i into X; if T_i=2, insert S_i into Y.

After processing each query, print this value:

• the number of strings in Y that have no element of X as a prefix.

Constraints

• Q is an integer between 1 and 2 \times 10^5, inclusive.
• T_i \in \{1,2\}
• Each S_i is a string of length between 1 and 5\times 10^5, inclusive, consisting of lowercase English letters.
• \displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5

Sample Input 1

4
1 at
2 watcoder
2 atcoder
1 wa

Sample Output 1

0
1
1
0

The counts after processing the queries for i=1,2,3,4 are as follows.

• i=1: Y is empty, so the count is 0.
• i=2: watcoder has no element of X as a prefix, so the count is 1.
• i=3: watcoder has no element of X as a prefix, while atcoder has at as a prefix, so the count is 1.
• i=4: watcoder has wa as a prefix, and atcoder has at as a prefix, so the count is 0.

Sample Input 2

10
1 w
1 avko
2 atcoder
1 bzginn
2 beginner
1 atco
2 contest
1 ntxcdg
1 atc
1 contest

Sample Output 2

0
0
1
1
2
1
2
2
2
1

Problem Statement

You are given a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) of length N.

You can perform the following operation on A zero or more times:

• Choose an integer i with 1 \le i \le N - 1, decrease A_i by 1, and increase A_{i+1} by 1.

Find the minimum number of operations required to make A strictly increasing.

It can be proved that the answer is less than 2^{63}.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 3 \times 10^5
• 1 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• The sum of N across all test cases is at most 6 \times 10^5.
• All input values are integers.

Sample Input 1

4
3
0 1 0
4
4 6 3 5
7
1 2 3 4 5 6 7
10
11 9 1 3 17 19 10 19 17 3

Sample Output 1

3
5
0
78

Consider the first test case.

By performing the following operations, A can be made strictly increasing in three operations:

• Choose i=1. A becomes (-1, 2, 0).
• Choose i=2. A becomes (-1, 1, 1).
• Choose i=2. A becomes (-1, 0, 2).

It is impossible to make A strictly increasing in fewer than three operations, so output 3.