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 two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

• X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

• |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq K \leq 10^9
• 1 \leq A_i,B_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.

Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.

Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes

Problem Statement

You are given a non-empty string S consisting of (, ), and ?.
There are 2^x ways to obtain a new string by replacing each ? in S with ( and ), where x is the number of occurrences of ? in S. Among them, find the number, modulo 998244353, of ways that yield a parenthesis string.

A string is said to be a parenthesis string if one of the following conditions is satisfied.

• It is an empty string.
• It is a concatenation of (, A, and ), for some parenthesis string A.
• It is a concatenation of A and B, for some non-empty parenthesis strings A and B.

Constraints

• S is a non-empty string of length at most 3000 consisting of (, ), and ?.

Sample Input 1

(???(?

Sample Output 1

2

Replacing S with ()()() or (())() yields a parenthesis string.
The other replacements do not yield a parenthesis string, so 2 should be printed.

Sample Input 2

)))))

Sample Output 2

0

Sample Input 3

??????????????(????????(??????)?????????(?(??)

Sample Output 3

603032273

Print the count modulo 998244353.

Problem Statement

There is a simple undirected graph with N vertices and M edges, where vertices are numbered from 1 to N, and edges are numbered from 1 to M. Edge i connects vertex a_i and vertex b_i.
K security guards numbered from 1 to K are on some vertices. Guard i is on vertex p_i and has a stamina of h_i. All p_i are distinct.

A vertex v is said to be guarded when the following condition is satisfied:

• there is at least one guard i such that the distance between vertex v and vertex p_i is at most h_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in the path connecting vertices u and v.

List all guarded vertices in ascending order.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)
• 1 \leq K \leq N
• 1 \leq a_i, b_i \leq N
• The given graph is simple.
• 1 \leq p_i \leq N
• All p_i are distinct.
• 1 \leq h_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
1 2 3 5

The guarded vertices are 1, 2, 3, 5.
These vertices are guarded because of the following reasons.

• The distance between vertex 1 and vertex p_1 = 1 is 0, which is not greater than h_1 = 1. Thus, vertex 1 is guarded.
• The distance between vertex 2 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 2 is guarded.
• The distance between vertex 3 and vertex p_2 = 5 is 1, which is not greater than h_2 = 2. Thus, vertex 3 is guarded.
• The distance between vertex 5 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 5 is guarded.

Sample Input 2

3 0 1
2 3

Sample Output 2

1
2

The given graph may have no edges.

Sample Input 3

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

Sample Output 3

7
1 2 3 5 6 8 9

Problem Statement

The shop supaisu-ya sells 2^N-1 kinds of spices: Spice 1, Spice 2, \ldots, Spice 2^N-1. One pack of each spice is in stock. For each i = 1, 2, \ldots, 2^N-1, Spice i costs c_i yen. Takahashi can buy any of these spices.

He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If k spices, Spice A_1, Spice A_2, \ldots, Spice A_k, are mixed, the hotness of the resulting curry is A_1 \oplus A_2 \oplus \cdots \oplus A_k, where \oplus denotes the bitwise XOR.

Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from 1 through 2^N-1. Print the minimum possible amount of money Takahashi pays.

Constraints

• 2 \leq N \leq 16
• 1 \leq c_i \leq 10^9
• All values in input are integers.

Sample Input 1

2
4 5 3

Sample Output 1

7

If Takahashi buys Spice 1 and 3, he can make curry of any hotness from 1 through 3, as follows.

• To make curry of hotness 1, use just Spice 1.
• To make curry of hotness 2, mix Spice 1 and Spice 3.
• To make curry of hotness 3, use just Spice 3.

Here, Takahashi pays c_1 + c_3 = 4 + 3 = 7 yen, which is the minimum possible amount he pays.

Sample Input 2

4
9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

Sample Output 2

15