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

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

• 1 \leq N,M,L \leq 100
• 0 \leq A_i, B_i ,C_i \leq 10^8
• 1 \leq Q \leq 2\times 10^5
• 0 \leq X_i \leq 3\times 10^8
• All input values are integers.

Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No

• It is impossible to select one element from each of A, B, and C so that their sum is 1.
• Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
• Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
• It is impossible to select one element from each of A, B, and C so that their sum is 50.

Problem Statement

N people, with ID numbers 1, 2, \dots, N, are lining up in front of a bank.
There will be Q events. The following three kinds of events can happen.

• 1 : The teller calls the person with the smallest ID number who has not been called.
• 2 x : The person with the ID number x comes to the teller for the first time. (Here, person x has already been called by the teller at least once.)
• 3 : The teller again calls the person with the smallest ID number who has already been called but has not come.

Print the ID numbers of the people called by the teller in events of the third kind.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 2 \leq Q \leq 5 \times 10^5
• There will not be an event of the first kind when all people have already been called at least once.
• For each event of the second kind, the person with the ID number x has already been called by the teller at least once.
• For each event of the second kind, the person with the ID number x will not come to the teller more than once.
• There will not be an event of the third kind when all people who have already been called have come to the teller.
• There is at least one event of the third kind.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
2
4

For each i = 1, 2, \dots, Q, shown below is the set of people who have already been called but have not come just before the i-th event.

• i=1 : \lbrace \rbrace
• i=2 : \lbrace 1\rbrace
• i=3 : \lbrace 1,2\rbrace
• i=4 : \lbrace 1,2\rbrace
• i=5 : \lbrace 2\rbrace
• i=6 : \lbrace 2,3\rbrace
• i=7 : \lbrace 2\rbrace
• i=8 : \lbrace 2\rbrace
• i=9 : \lbrace 2,4\rbrace
• i=10 : \lbrace 4\rbrace

The events for i=3,7,10 are of the third kind, so you should print the persons with the smallest ID numbers in the sets for those events: 1, 2, 4.

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

The following operation will be performed K times:

• For i=1,2,\ldots,N, simultaneously update P_i to P_{P_i}.

Print P after all operations.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq K\leq10^{18}
• 1\leq P_i\leq N\ (1\leq i\leq N)
• P_i\neq P_j\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

6 3
5 6 3 1 2 4

Sample Output 1

6 1 3 2 4 5

With each operation, P changes as follows:

• After the first operation, P is (2,4,3,5,6,1).
• After the second operation, P is (4,5,3,6,1,2).
• After the third operation, P is (6,1,3,2,4,5).

Thus, print 6 1 3 2 4 5.

Sample Input 2

5 1000000000000000000
1 2 3 4 5

Sample Output 2

1 2 3 4 5

Since P_i=i, P does not change no matter how many operations are performed.

Sample Input 3

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

Sample Output 3

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

Problem Statement

There are N cities numbered city 1, city 2, \ldots, and city N.
There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city i (1\leq i\leq N) to another is represented by a length-M string S_i consisting of 0 and 1. Specifically, for 1\leq j\leq N,

• if 1\leq j-i\leq M and the (j-i)-th character of S_i is 1, then a teleporter can send you directly from city i to city j;
• otherwise, it cannot send you directly from city i to city j.

Solve the following problem for k=2,3,\ldots, N-1:

Can you travel from city 1 to city N without visiting city k by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print -1.

Constraints

• 3 \leq N \leq 10^5
• 1\leq M\leq 10
• M<N
• S_i is a string of length M consisting of 0 and 1.
• If i+j>N, then the j-th character of S_i is 0.
• N and M are integers.

Sample Input 1

5 2
11
01
11
10
00

Sample Output 1

2 3 2

A teleporter sends you

• from city 1 to cities 2 and 3;
• from city 2 to city 4;
• from city 3 to cities 4 and 5;
• from city 4 to city 5; and
• from city 5 to nowhere.

Therefore, there are three paths to travel from city 1 to city 5:

• path 1 : city 1 \to city 2 \to city 4 \to city 5;
• path 2 : city 1 \to city 3 \to city 4 \to city 5; and
• path 3 : city 1 \to city 3 \to city 5.

Among these paths,

• two paths, path 2 and path 3, do not visit city 2. Among them, path 3 requires the minimum number of teleporter uses (twice).
• Path 1 is the only path without city 3. It requires using a teleporter three times.
• Path 3 is the only path without city 4. It requires using a teleporter twice.

Thus, 2, 3, and 2, separated by spaces, should be printed.

Sample Input 2

6 3
101
001
101
000
100
000

Sample Output 2

-1 3 3 -1

The only path from city 1 to city 6 is city 1 \to city 2 \to city 5 \to city 6.
For k=2,5, there is no way to travel from city 1 to city 6 without visiting city k.
For k=3,4, the path above satisfies the condition; it requires using a teleporter three times.

Thus, -1, 3, 3, and -1, separated by spaces, should be printed.

Note that a teleporter is one-way; a teleporter can send you from city 3 to city 4, but not from city 4 to city 3,
so the following path, for example, is invalid: city 1 \to city 4 \to city 3 \to city 6.