Problem Statement

Given a string S of length N consisting of lowercase English alphabets, print the last character of S.

Constraints

• N is an integer.
• 1 ≤ N ≤ 1000
• S is a string of length N consisting of lowercase English alphabets.

Sample Input 1

5
abcde

Sample Output 1

e

The last character of S = {}abcde is e, so e should be printed.

Sample Input 2

1
a

Sample Output 2

a

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

Restore run-length encoding. If the result is too long, output Too Long.

You are given N pairs of characters and integers (c_1,l_1),(c_2,l_2),\ldots,(c_N,l_N).

Let S be the string formed by concatenating l_1 characters c_1, l_2 characters c_2, \ldots, and l_N characters c_N in this order.

Output S. However, if the length of S exceeds 100, output Too Long instead.

Constraints

• 1\leq N\leq 100
• 1\leq l_i\leq 10^{18}
• N and l_i are integers.
• Each c_i is a lowercase English letter.
• c_i\neq c_{i+1}

Sample Input 1

8
m 1
i 1
s 2
i 1
s 2
i 1
p 2
i 1

Sample Output 1

mississippi

S is mississippi. Since the length of S is not greater than 100, output S.

Sample Input 2

7
a 1000000000000000000
t 1000000000000000000
c 1000000000000000000
o 1000000000000000000
d 1000000000000000000
e 1000000000000000000
r 1000000000000000000

Sample Output 2

Too Long

The length of S is 7\times 10^{18}, so output Too Long.

Sample Input 3

1
a 100

Sample Output 3

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Input 4

6
g 4
j 1
m 4
e 4
d 3
i 4

Sample Output 4

ggggjmmmmeeeedddiiii

Problem Statement

There is a calculator with the buttons 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
When a string x is displayed on this calculator and you press a button b, the resulting displayed string becomes the string x with b appended to its end.

Initially, the calculator displays the empty string (a string of length 0).
Find the minimum number of button presses required to display the string S on this calculator.

Constraints

• S is a string of length at least 1 and at most 1000, consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• The first character of S is not 0.

Sample Input 1

1000000007

Sample Output 1

6

To display 1000000007, you can press the buttons 1, 00, 00, 00, 00, 7 in this order. The total number of button presses is 6, and this is the minimum possible.

Sample Input 2

998244353

Sample Output 2

9

Sample Input 3

32000

Sample Output 3

4

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

Given is a string S consisting of X and ..

You can do the following operation on S between 0 and K times (inclusive).

• Replace a . with an X.

What is the maximum possible number of consecutive Xs in S after the operations?

Constraints

• 1 \leq |S| \leq 2 \times 10^5
• Each character of S is X or ..
• 0 \leq K \leq 2 \times 10^5
• K is an integer.

Sample Input 1

XX...X.X.X.
2

Sample Output 1

5

After replacing the Xs at the 7-th and 9-th positions with X, we have XX...XXXXX., which has five consecutive Xs at 6-th through 10-th positions.
We cannot have six or more consecutive Xs, so the answer is 5.

Sample Input 2

XXXX
200000

Sample Output 2

4

It is allowed to do zero operations.

Problem Statement

There are N islands and M bidirectional bridges connecting two islands. The islands and bridges are numbered 1, 2, \ldots, N and 1, 2, \ldots, M, respectively.
Bridge i connects islands U_i and V_i, and the time it takes to cross it in either direction is T_i.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.

You are given Q queries, so answer each of them. The i-th query is as follows:

You are given K_i distinct bridges: bridges B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}.
Find the minimum time required to travel from island 1 to island N using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.

Constraints

• 2 \leq N \leq 400
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_i < V_i \leq N
• 1 \leq T_i \leq 10^9
• 1 \leq Q \leq 3000
• 1 \leq K_i \leq 5
• 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
• All input values are integers.
• It is possible to travel between any two islands using some bridges.

Sample Input 1

3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

Sample Output 1

25
70

For the first query, we need to find the minimum time to travel from island 1 to island 3 while using bridge 1. The minimum time is achieved by using bridge 1 to move from island 1 to island 2, then using bridge 4 to move from island 2 to island 3. The time taken is 10 + 15 = 25. Hence, print 25 on the first line.

For the second query, we need to find the minimum time to travel from island 1 to island 3 while using both bridges 3 and 5. The minimum time is achieved by using bridge 3 to move from island 1 to island 3, then using bridge 5 to move to island 2, and finally using bridge 4 to return to island 3. The time taken is 30 + 25 + 15 = 70. Hence, print 70 on the second line.

Sample Input 2

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

Sample Output 2

5
3

For each query, you can cross the specified bridges in either direction.

Sample Input 3

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

Sample Output 3

4000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

You are given integers N, M and a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N).

For k = 0, 1, \ldots, M-1, solve the following problem:

Define an integer sequence B = (B_1, B_2, \ldots, B_N) so that B_i is the remainder of A_i + k when divided by M. Find the inversion number in B.

Constraints

• 1 \le N,M \le 2\times 10^5
• 0 \le A_i < M
• All input values are integers.

Sample Input 1

3 3
2 1 0

Sample Output 1

3
1
1

• For k=0: B=(2, 1, 0). The inversion number is 3.
• For k=1: B=(0, 2, 1). The inversion number is 1.
• For k=2: B=(1, 0, 2). The inversion number is 1.

Sample Input 2

5 6
5 3 5 0 1

Sample Output 2

7
3
3
1
1
5

Sample Input 3

7 7
0 1 2 3 4 5 6

Sample Output 3

0
6
10
12
12
10
6