Problem Statement

This problem is an easier version of Problem G.

There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.

Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.

Constraints

• 1 \leq M \leq 100
• M is an integer.
• S_i is a string of length M consisting of digits.

Sample Input 1

10
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.

• Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays 8, the ((0 \bmod 10)+1=1)-st character of S_2.
• Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays 8, the ((2 \bmod 10)+1=3)-rd character of S_3.
• Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays 8, the ((6 \bmod 10)+1=7)-th character of S_1.

There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.

Sample Input 2

20
01234567890123456789
01234567890123456789
01234567890123456789

Sample Output 2

20

Note that he must stop all the reels and make them display the same character.

Sample Input 3

5
11111
22222
33333

Sample Output 3

-1

It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

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

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

12

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

• buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
• buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
• buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
• buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
• buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

0

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

112

Problem Statement

There are N ropes numbered 1 through N. One end of each rope is painted red, and the other is painted blue.

You are going to perform M operations of tying ropes. In the i-th operation, you tie the end of rope A_i painted B_i with the end of rope C_i painted D_i, where R means red and B means blue. For each rope, an end with the same color is not tied multiple times.

Find the number of groups of connected ropes that form cycles, and the number of those that do not, after all the operations.

Here, a group of connected ropes \lbrace v_0, v_1, \ldots, v_{x-1} \rbrace is said to form a cycle if one can rearrange the elements of v so that, for each 0 \leq i < x, rope v_i is tied to rope v_{(i+1) \bmod x}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, C_i \leq N
• (A_i, B_i) \neq (A_j, B_j), (C_i, D_i) \neq (C_j, D_j) (i \neq j)
• (A_i, B_i) \neq (C_j, D_j)
• N, M, A_i, and C_i are integers.
• B_i is R or B, and so is D_i.

Sample Input 1

5 3
3 R 5 B
5 R 3 B
4 R 2 B

Sample Output 1

1 2

There are three groups of connected ropes: \lbrace 1 \rbrace, \lbrace 2,4 \rbrace, and \lbrace 3,5 \rbrace.

The group of ropes \lbrace 3,5 \rbrace forms a cycle, while the groups of rope \lbrace 1 \rbrace and ropes \lbrace 2,4 \rbrace do not. Thus, X = 1 and Y = 2.

Sample Input 2

7 0

Sample Output 2

0 7

Sample Input 3

7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B

Sample Output 3

2 1

Problem Statement

There are N towns numbered 1, \dots, N, and M roads numbered 1, \dots, M.
Every road is directed; road i (1 \leq i \leq M) leads you from Town A_i to Town B_i. The length of road i is C_i.

You are given a sequence E = (E_1, \dots, E_K) of length K consisting of integers between 1 and M. A way of traveling from town 1 to town N using roads is called a good path if:

• the sequence of the roads' numbers arranged in the order used in the path is a subsequence of E.

Note that a subsequence of a sequence is a sequence obtained by removing 0 or more elements from the original sequence and concatenating the remaining elements without changing the order.

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, report that fact.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M, K \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)
• 1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)
• 1 \leq E_i \leq M \, (1 \leq i \leq K)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4

There are two possible good paths as follows:

• Using road 4. In this case, the sum of the length of the used road is 5.
• Using road 1 and 2 in this order. In this case, the sum of the lengths of the used roads is 2 + 2 = 4.

Therefore, the desired minimum value is 4.

Sample Input 2

3 2 3
1 2 1
2 3 1
2 1 1

Sample Output 2

-1

There is no good path.

Sample Input 3

4 4 5
3 2 2
1 3 5
2 4 7
3 4 10
2 4 1 4 3

Sample Output 3

14

Problem Statement

We have a grid with N rows and M columns. The square (i,j) at the i-th row from the top and j-th column from the left has an integer (i-1) \times M + j written on it.
Let us perform the following operation on this grid.

• For every square (i,j) such that i+j is odd, replace the integer on that square with 0.

Answer Q questions on the grid after the operation.
The i-th question is as follows:

• Find the sum of the integers written on all squares (p,q) that satisfy all of the following conditions, modulo 998244353.
  • A_i \le p \le B_i.
  • C_i \le q \le D_i.

Constraints

• All values in the input are integers.
• 1 \le N,M \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i \le B_i \le N
• 1 \le C_i \le D_i \le M

Sample Input 1

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

Sample Output 1

28
27
36
14
0
104

The grid in this input is shown below.

This input contains six questions.

• The answer to the first question is 0+3+0+6+0+8+0+11+0=28.
• The answer to the second question is 1+0+9+0+17=27.
• The answer to the third question is 17+0+19+0=36.
• The answer to the fourth question is 14.
• The answer to the fifth question is 0.
• The answer to the sixth question is 104.

Sample Input 2

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

Sample Output 2

716070898
240994972
536839100

For the first question, note that although the integer written on the square (10^9,10^9) is 10^{18}, you are to find it modulo 998244353.

Sample Input 3

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

Sample Output 3

712559605
648737448
540261130