Problem Statement

There are N people numbered from 1 to N visiting a conveyor belt sushi restaurant. The gourmet level of person i is A_i.

Now, M pieces of sushi will be placed on the conveyor belt. The deliciousness of the j-th sushi is B_j. Each piece of sushi passes in front of people 1, 2, \dots, N in this order. Each person, when a sushi whose deliciousness is not less than their gourmet level passes in front of them, will take and eat that sushi; otherwise, they do nothing. A sushi that person i takes and eats will no longer pass in front of person j\ (j > i).

For each of the M pieces of sushi, determine who eats that sushi, or if nobody eats it.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 3
3 8 2
5 2 1

Sample Output 1

1
3
-1

• For the 1st sushi:
  • It first passes in front of person 1. Since B_1 \geq A_1, person 1 takes and eats it.
  • It will not pass in front of person 2 and 3.
• For the 2nd sushi:
  • It first passes in front of person 1. Since B_2 < A_1, person 1 does nothing.
  • Next, it passes in front of person 2. Since B_2 < A_2, person 2 does nothing.
  • Finally, it passes in front of person 3. Since B_2 \geq A_3, person 3 takes and eats it.
• For the 3rd sushi:
  • It first passes in front of person 1. Since B_3 < A_1, person 1 does nothing.
  • Next, it passes in front of person 2. Since B_3 < A_2, person 2 does nothing.
  • Finally, it passes in front of person 3. Since B_3 < A_3, person 3 does nothing.
  • Therefore, nobody eats this sushi.

Sample Input 2

3 3
1 1 1
1 1 1

Sample Output 2

1
1
1

Sample Input 3

10 5
60 83 76 45 70 91 37 58 94 22
70 39 52 33 18

Sample Output 3

1
7
4
10
-1

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Initially, there is one wall in each cell.
After processing Q queries explained below in the order they are given, find the number of remaining walls.

In the q-th query, you are given two integers R_q and C_q.
You place a bomb at (R_q, C_q) to destroy walls. As a result, the following process occurs.

• If there is a wall at (R_q, C_q), destroy that wall and end the process.
• If there is no wall at (R_q, C_q), destroy the first walls that appear when looking up, down, left, and right from (R_q, C_q). More precisely, the following four processes occur simultaneously:
  • If there exists an i \lt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all i \lt k \lt R_q, destroy the wall at (i, C_q).
  • If there exists an i \gt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all R_q \lt k \lt i, destroy the wall at (i, C_q).
  • If there exists a j \lt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all j \lt k \lt C_q, destroy the wall at (R_q, j).
  • If there exists a j \gt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all C_q \lt k \lt j, destroy the wall at (R_q, j).

Constraints

• 1 \leq H, W
• H \times W \leq 4 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq R_q \leq H
• 1 \leq C_q \leq W
• All input values are integers.

Sample Input 1

2 4 3
1 2
1 2
1 3

Sample Output 1

2

The process of handling the queries can be explained as follows:

• In the 1st query, (R_1, C_1) = (1, 2). There is a wall at (1, 2), so the wall at (1, 2) is destroyed.
• In the 2nd query, (R_2, C_2) = (1, 2). There is no wall at (1, 2), so the walls at (2,2),(1,1),(1,3), which are the first walls that appear when looking up, down, left, and right from (1, 2), are destroyed.
• In the 3rd query, (R_3, C_3) = (1, 3). There is no wall at (1, 3), so the walls at (2,3),(1,4), which are the first walls that appear when looking up, down, left, and right from (1, 3), are destroyed.

After processing all queries, there are two remaining walls, at (2, 1) and (2, 4).

Sample Input 2

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

Sample Output 2

10

Sample Input 3

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

Sample Output 3

2

Problem Statement

Solve the following problem for T test cases.

Given an integer N and a string S, find the number of strings X that satisfy all of the conditions below, modulo 998244353.

• X is a string of length N consisting of uppercase English letters.
• X is a palindrome.
• X \le S in lexicographical order.
  • That is, X=S or X is lexicographically smaller than S.

Constraints

• 1 \le T \le 250000
• N is an integer between 1 and 10^6 (inclusive).
• In a single input, the sum of N over the test cases is at most 10^6.
• S is a string of length N consisting of uppercase English letters.

Sample Input 1

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

Sample Output 1

24
29
212370247
36523399
231364016

This input contains five test cases.

Test case #1:
The 24 strings satisfying the conditions are AAA, ABA, ACA,..., AXA.

Test case #2:
S may not be a palindrome.

Test case #3:
Be sure to find the count modulo 998244353.

Problem Statement

As the factory manager of Keyence, you want to monitor several sections on a conveyor belt. There are a total of N sections you want to monitor, and the length of the i-th section is D_i meters.

There are two types of sensors to choose from, and below is some information about each sensor.

• Type-j sensor (1\leq j \leq 2): Can monitor a section of length L_j meters. The price is C_j per sensor, and you can use at most K_j sensors of this type in total.

You can divide one section into several sections for monitoring. It is fine if the sections monitored by the sensors overlap, or if they monitor more than the length of the section you want to monitor. For example, when L_1=4 and L_2=2, you can use one type-1 sensor to monitor a section of length 3 meters, or use one type-1 and one type-2 sensor to monitor a section of length 5 meters.

Determine whether it is possible to monitor all N sections, and if it is possible, find the minimum total cost of the necessary sensors.

Constraints

• 1\leq N \leq 100
• 1\leq D_i,L_j \leq 10^5
• 1\leq C_j \leq 10^9
• 1\leq K_j \leq 10^3
• All input values are integers.

Sample Input 1

3
3 5 10
4 3 3
2 2 6

Sample Output 1

17

You can monitor all sections by using three type-1 sensors and four type-2 sensors as follows.

• Use one type-1 sensor to monitor the first section.
• Use one type-1 and one type-2 sensor to monitor the second section.
• Use one type-1 and three type-2 sensors to monitor the third section.

In this case, the total cost of the necessary sensors is 3\times 3 + 2\times 4 = 17, which is the minimum.

Sample Input 2

3
3 5 10
4 3 3
2 2 3

Sample Output 2

-1

Sample Input 3

2
4 8
3 1 100
4 10000 100

Sample Output 3

5

It is fine if one type of sensor is not used at all.