Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

• 1 \leq N \leq 2024
• N is an integer.

Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.

Sample Input 2

1

Sample Output 2

Long

Problem Statement

You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).

Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

3
3 4 6

Sample Output 1

12 24

We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.

Sample Input 2

5
22 75 26 45 72

Sample Output 2

1650 1950 1170 3240

Problem Statement

You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).

The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.

Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:

• S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).

Constraints

• 1 \leq M \leq N \leq 50
• N and M are integers.
• Each of S_{i,j} and T_{i,j} is . or #.
• There is exactly one pair (a,b) satisfying the condition.

Sample Input 1

3 2
#.#
..#
##.
.#
#.

Sample Output 1

2 2

The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.

Sample Input 2

2 1
#.
##
.

Sample Output 2

1 2

Problem Statement

One day, Takahashi performed N operations on a certain web site.

The i‑th operation (1 \le i \le N) is represented by a string S_i, which is one of the following:

• S _ i= login: He performs a login operation and becomes logged in to the site.
• S _ i= logout: He performs a logout operation and becomes not logged in to the site.
• S _ i= public: He accesses a public page of the site.
• S _ i= private: He accesses a private page of the site.

The site returns an authentication error if and only if he accesses a private page while he is not logged in.

Logging in again while already logged in, or logging out again while already logged out, does not cause an error. Even after an authentication error is returned, he continues performing the remaining operations.

Initially, he is not logged in.

Print the number of operations among the N operations at which he receives an authentication error.

Constraints

• 1 \le N \le 100
• N is an integer.
• Each S_i is one of login, logout, public, private. (1 \le i \le N)

Sample Input 1

6
login
private
public
logout
private
public

Sample Output 1

1

The result of each operation is as follows:

• Takahashi becomes logged in.
• He accesses a private page. He is logged in, so no error is returned.
• He accesses a public page.
• He becomes logged out.
• He accesses a private page. He is not logged in, so an authentication error is returned.
• He accesses a public page.

An authentication error occurs only at the 5th operation, so print 1.

Sample Input 2

4
private
private
private
logout

Sample Output 2

3

If he tries to access private pages consecutively while not logged in, he receives an authentication error for each such operation.

Note that logging out again while already logged out does not cause an authentication error.

Sample Input 3

20
private
login
private
logout
public
logout
logout
logout
logout
private
login
login
private
login
private
login
public
private
logout
private

Sample Output 3

3

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq D\leq 2\times 10^5
• 1\leq P\leq 10^9
• 1\leq F_i\leq 10^9
• All input values are integers.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

• if A _ i=-1, person i is at the front of the line;
• if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

• 1\leq N\leq3\times10 ^ 5
• A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
• There is exactly one way to arrange the N people consistent with the information given.
• All input values are integers.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

• person 1 is standing right behind person 4,
• person 2 is standing right behind person 1,
• person 3 is at the front of the line,
• person 4 is standing right behind person 5,
• person 5 is standing right behind person 3, and
• person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Problem Statement

The sky is represented by a 2000 \times 2000 grid.
When looking up at the sky, the cell at the r-th row from the top and c-th column from the left is called (r,c).

Currently, there are clouds 1,2,\dots,N floating in this sky.
The cell (r,c) is covered by cloud i if and only if it satisfies U_i \le r \le D_i and L_i \le c \le R_i.

For k=1,2,\dots,N, answer the following question:

• Remove only cloud k from the N clouds. At this point, there are N-1 clouds floating in the sky. How many cells are not covered by any cloud?

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le U_i \le D_i \le 2000
• 1 \le L_i \le R_i \le 2000
• All input values are integers.

Sample Input 1

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

Sample Output 1

3999983
3999976
3999982
3999978
3999977

The figure shows the top-left 5 \times 6 region of the sky.

• When cloud 1 is removed, the number of cells covered by some cloud is 17, so the number of cells not covered by any cloud is 3999983.
• When cloud 2 is removed, the number of cells covered by some cloud is 24, so the number of cells not covered by any cloud is 3999976.
• When cloud 3 is removed, the number of cells covered by some cloud is 18, so the number of cells not covered by any cloud is 3999982.
• When cloud 4 is removed, the number of cells covered by some cloud is 22, so the number of cells not covered by any cloud is 3999978.
• When cloud 5 is removed, the number of cells covered by some cloud is 23, so the number of cells not covered by any cloud is 3999977.

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

• (1,2,1,2,1)
• (1,2,1,3,1)
• (1,3,1,2,1)
• (1,3,1,3,1)

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

There are N sticks, and the length of the i-th stick is A_i.
You will perform the following operation M times:

• Choose one stick of length at least 2, and let l be the length of this stick. Divide this stick into two sticks of lengths \left\lfloor\frac{l}{2}\right\rfloor and \left\lceil\frac{l}{2}\right\rceil.

From the constraints, it can be proved that it is possible to perform the operation M times.
After M operations, N+M sticks will remain. Find the maximum possible value of the median of the lengths of these sticks.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq M \leq \sum_{i=1}^{N}{A_i} - N
• N+M is odd.
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

3
5 2
14 2 5 19 1
10 1
10 6 7 6 2 20 9 16 3 3
4 1
444 444 44 444

Sample Output 1

7
7
444

In the first test case, if you choose the stick of length 14 in the first operation, it is divided into two sticks of length 7, and now you have six sticks of lengths 7,7,2,5,19,1. If you choose the stick of length 19 in the second operation, it is divided into two sticks of lengths 9,10, and now you have seven sticks of lengths 7,7,2,5,9,10,1. In this case, the median of the stick lengths is 7.