Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

• 1 \leq N \leq 1000
• -10^9 \leq A_i, B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054

• The first line should contain A_1 + B_1 = 3 + 5 = 8.
• The second line should contain A_2 + B_2 = 2 + (-6) = -4.
• The third line should contain A_3 + B_3 = (-5) + 0 = -5.
• The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

Constraints

• 1 \leq K \leq N \leq 100
• K and N are integers.
• S_i is a string of length 10 consisting of lowercase English letters.
• S_i \neq S_j if i \neq j.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1

Problem Statement

You are given an integer sequence of length N, A = (A_1, A_2, \ldots, A_N), and a positive integer K.

For each i = 1, 2, \ldots, Q, determine whether a contiguous subsequence of A, (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}), is a good sequence.

Here, a sequence of length n, X = (X_1, X_2, \ldots, X_n), is good if and only if there is a way to perform the operation below some number of times (possibly zero) to make all elements of X equal 0.

Choose an integer i such that 1 \leq i \leq n-K+1 and an integer c (possibly negative). Add c to each of the K elements X_{i}, X_{i+1}, \ldots, X_{i+K-1}.

It is guaranteed that r_i - l_i + 1 \geq K for every i = 1, 2, \ldots, Q.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq \min\lbrace 10, N \rbrace
• -10^9 \leq A_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq l_i, r_i \leq N
• r_i-l_i+1 \geq K
• All values in the input are integers.

Sample Input 1

7 3
3 -1 1 -2 2 0 5
2
1 6
2 7

Sample Output 1

Yes
No

The sequence X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0) is good. Indeed, you can do the following to make all elements equal 0.

• First, do the operation with i = 2, c = 4, making X = (3, 3, 5, 2, 2, 0).
• Next, do the operation with i = 3, c = -2, making X = (3, 3, 3, 0, 0, 0).
• Finally, do the operation with i = 1, c = -3, making X = (0, 0, 0, 0, 0, 0).

Thus, the first line should contain Yes.

On the other hand, for the sequence (A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5), there is no way to make all elements equal 0, so it is not a good sequence. Thus, the second line should contain No.

Sample Input 2

20 4
-19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19
5
13 16
4 11
3 12
13 18
4 10

Sample Output 2

No
Yes
No
Yes
No

Problem Statement

There are N items in a shop, numbered as Item 1, Item 2, \ldots, Item N.
For each i = 1, 2, \ldots, N, the regular price of Item i is A_i yen. For each item, there is only one in stock.

Takahashi wants M items: Item X_1, Item X_2, \ldots, Item X_M.

He repeats the following until he gets all items he wants.

Let r be the number of unsold items now. Choose an integer j such that 1 \leq j \leq r, and buy the item with the j-th smallest item number among the unsold items, for its regular price plus C_j yen.

Print the smallest total amount of money needed to get all items Takahashi wants.

Takahashi may also buy items other than the ones he wants.

Constraints

• 1 \leq M \leq N \leq 5000
• 1 \leq A_i \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

17

Here is a way for Takahashi to get all items he wants with the smallest total amount of money.

• Initially, five items, Items 1, 2, 3, 4, 5, are remaining. Choose j = 5 to buy the item with the fifth smallest item number among the remaining, Item 5, for A_5 + C_5 = 5 + 3 = 8 yen.
• Then, four items, Items 1, 2, 3, 4, are remaining. Choose j = 2 to buy the item with the second smallest item number among the remaining, Item 2, for A_2 + C_2 = 1 + 2 = 3 yen.
• Then, three items, Items 1, 3, 4, are remaining. Choose j = 2 to buy the item with the second smallest item number among the remaining, Item 3, for A_3 + C_2 = 4 + 2 = 6 yen.

Now, Takahashi has all items he wants, Items 3 and 5, (along with Item 2, which is not wanted) for a total cost of 8 + 3 + 6 = 17 yen, the minimum possible.

Sample Input 2

20 8
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
32 38 84 49 93 53 26 13 25 2 76 32 42 34 18 77 14 67 88 12
1 3 4 5 8 14 16 20

Sample Output 2

533

Problem Statement

You are given a positive integer X with N digits in decimal representation. None of the digits of X is 0.
For a subset S of \lbrace 1,2, \ldots, N-1 \rbrace , let f(S) be defined as follows.

See the decimal representation of X as a string of length N, and decompose it into |S| + 1 strings by splitting it between the i-th and (i + 1)-th characters if and only if i \in S.
Then, see these |S| + 1 strings as integers in decimal representation, and let f(S) be the product of these |S| + 1 integers.

There are 2^{N-1} subsets of \lbrace 1,2, \ldots, N-1 \rbrace , including the empty set, which can be S. Find the sum of f(S) over all these S, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• X has N digits in decimal representation, none of which is 0.
• All values in the input are integers.

Sample Input 1

3
234

Sample Output 1

418

For S = \emptyset, we have f(S) = 234.
For S = \lbrace 1 \rbrace, we have f(S) = 2 \times 34 = 68.
For S = \lbrace 2 \rbrace, we have f(S) = 23 \times 4 = 92.
For S = \lbrace 1, 2 \rbrace, we have f(S) = 2 \times 3 \times 4 = 24.
Thus, you should print 234 + 68 + 92 + 24 = 418.

Sample Input 2

4
5915

Sample Output 2

17800

Sample Input 3

9
998244353

Sample Output 3

258280134

Problem Statement

There is zero or one bomb at each of positions 0, 1, 2, \ldots, 3^N-1.
Let us say that positions x and y are neighboring each other if and only if the following condition is satisfied for every i=1, \ldots, N.

• Let x' and y' be the i-th lowest digits of x and y in ternary representation, respectively. Then, |x' - y'| \leq 1.

It is known that there are exactly A_i bombs in total at the positions neighboring position i. Print a placement of bombs consistent with this information.

Constraints

• 1 \leq N \leq 12
• There is a placement of bombs consistent with A_0, A_1, \ldots, A_{3^N-1}.
• All values in the input are integers.

Sample Input 1

1
0 1 1

Sample Output 1

0 0 1

Position 0 is neighboring positions 0 and 1, which have 0 bombs in total.
Position 1 is neighboring positions 0, 1, and 2, which have 1 bomb in total.
Position 2 is neighboring positions 1 and 2, which have 1 bombs in total.
If there is a bomb at only position 2, all conditions above are satisfied, so this placement is correct.

Sample Input 2

2
2 3 2 4 5 3 3 4 2

Sample Output 2

0 1 0 1 0 1 1 1 0

Sample Input 3

2
0 0 0 0 0 0 0 0 0

Sample Output 3

0 0 0 0 0 0 0 0 0

Problem Statement

Print the number of integer sequences of length N, A = (A_1, A_2, \ldots, A_N), that satisfy both of the following conditions, modulo 998244353.

• 0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq M
• A_1 \oplus A_2 \oplus \cdots \oplus A_N = X

Here, \oplus denotes bitwise XOR.

Constraints

• 1 \leq N \leq 200
• 0 \leq M \lt 2^{30}
• 0 \leq X \lt 2^{30}
• All values in the input are integers.

Sample Input 1

3 3 2

Sample Output 1

5

Here are the five sequences of length N that satisfy both conditions in the statement: (0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3).

Sample Input 2

200 900606388 317329110

Sample Output 2

788002104