Problem Statement

You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).

Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

3
3 4 6

Sample Output 1

12 24

We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.

Sample Input 2

5
22 75 26 45 72

Sample Output 2

1650 1950 1170 3240

Problem Statement

Takahashi had a report whose deadline was B minutes past A o'clock on May 17, 2025. He submitted it at D minutes past C o'clock on May 17, 2025.
It is guaranteed that "B minutes past A o'clock" and "D minutes past C o'clock" are different times.

Output Yes if Takahashi submitted the report before the deadline, and No otherwise.

Constraints

• 0 \leq A, C \leq 23
• 0 \leq B, D \leq 59
• (A, B) \neq (C, D)
• A, B, C, and D are integers.

Sample Input 1

22 40 22 30

Sample Output 1

Yes

The deadline is 22:40, and he submitted at 22:30, so he submitted before the deadline. Hence, output Yes.

Sample Input 2

22 40 22 45

Sample Output 2

No

The deadline is 22:40, and he submitted at 22:45, so he submitted after the deadline. Hence, output No.

Sample Input 3

12 0 11 30

Sample Output 3

Yes

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

• All of the four digits are the same.
• For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

• 0 \leq X_1, X_2, X_3, X_4 \leq 9
• X_1, X_2, X_3, and X_4 are integers.

Sample Input 1

7777

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.

Sample Input 2

0112

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.

Sample Input 3

9012

Sample Output 3

Weak

Note that 0 follows 9.

Problem Statement

There are three dice, each with six faces.
The j-th face of the i-th die has A_{i,j} written on it.
For each die, each face comes up with probability \frac{1}{6}.

When these dice are rolled simultaneously, find the probability that the values 4,5,6 each appear exactly once.

Constraints

• A_{i,j} is an integer between 1 and 6, inclusive.

Sample Input 1

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

Sample Output 1

0.0277777778

The desired probability is \frac{1}{36}. An output such as 0.027778 is also accepted.

Sample Input 2

4 5 6 4 5 6
4 4 5 5 6 6
6 5 4 4 5 6

Sample Output 2

0.2222222222

The desired probability is \frac{2}{9}.

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

• You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
• The test result is represented by a single English letter R_i.
  • R_i = o means that Door X opened in the i-th test.
  • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

• N, M, K, C_i, and A_{i,j} are integers.
• 1 \le K \le N \le 15
• 1 \le M \le 100
• 1 \le C_i \le N
• 1 \le A_{i,j} \le N
• A_{i,j} \neq A_{i,k} if j \neq k.
• R_i is o or x.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

• In the first test, keys 1, 2, 3 were used, and Door X opened.
• In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

• Key 1 is real, key 2 is a dummy, and key 3 is real.
• Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

Problem Statement

N couples are seated in a line.
Count the number of pairs of couples such that neither couple was originally sitting next to each other, and both couples can end up sitting next to each other by swapping seats among those four people.

There is a sequence A = (A_1, A_2, \dots, A_{2N}) of length 2N. Each of the integers 1, 2, \dots, N appears exactly twice in A.

Find the number of integer pairs (a, b) satisfying 1 \leq a < b \leq N and all of the following conditions:

• The two occurrences of a in A are not adjacent.
• The two occurrences of b in A are not adjacent.
• By performing the following operation one or more times in any order, it is possible to reach a state where the two occurrences of a in A are adjacent and the two occurrences of b in A are also adjacent.
  • Choose an integer pair (i, j) (1 \leq i \leq 2N, 1 \leq j \leq 2N) such that A_i = a and A_j = b, and swap A_i with A_j.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• Each of 1, 2, \dots, N appears exactly twice in A.
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
0
4

Consider the first test case.
(a, b) = (1, 2) satisfies the conditions in the problem statement, for the following reasons:

• The two occurrences of 1 in A are not adjacent.
• The two occurrences of 2 in A are not adjacent.
• By performing the operation where (i, j) = (1, 6) and swapping A_1 with A_6, you can reach a state where the two occurrences of 1 are adjacent and the two occurrences of 2 are also adjacent.

(1, 2) is the only pair (a, b) that satisfies the conditions.

Problem Statement

Takahashi is with N animals. The N animals are called Animal 1, Animal 2, \ldots, Animal N.

Takahashi will perform the following N kinds of action. Each action can be performed any number of (possibly zero) times.

• Pay A_1 yen (the currency in Japan) to feed Animals 1 and 2.
• Pay A_2 yen to feed Animals 2 and 3.
• Pay A_3 yen to feed Animals 3 and 4.
• \cdots
• Pay A_i yen to feed Animals i and (i+1).
• \cdots
• Pay A_{N-2} yen to feed Animals (N-2) and (N-1).
• Pay A_{N-1} yen to feed Animals (N-1) and N.
• Pay A_N yen to feed Animals N and 1.

Note that the N-th action above feeds "Animals N and 1."

Print the minimum possible total cost to feed every animal at least once.

Constraints

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

Sample Input 1

5
2 5 3 2 5

Sample Output 1

7

If Takahashi performs the 1-st, 3-rd, and 4-th actions once each, Animals 1, 2, 3, 4, and 5 are fed once, once, once, twice, once, respectively, so every animal is fed at least once. The total cost to do so is A_1 + A_3 + A_4 = 2 + 3 + 2 = 7 yen, which is the minimum possible.

Sample Input 2

20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

Sample Output 2

426

Problem Statement

You are given Q triples of integers (a_1, b_1, d_1), (a_2, b_2, d_2), \ldots, (a_Q, b_Q, d_Q).

A subset S of the set \lbrace 1, 2, \ldots, Q\rbrace is defined to be a good set if there exists an integer sequence (X_1, X_2, \ldots, X_N) of length N that satisfies:

X_{a_i} - X_{b_i} = d_i for all i \in S.

Starting with S as an empty set, perform the following operation for i = 1, 2, \ldots, Q in this order:

If S \cup \lbrace i \rbrace is a good set, then replace S with S \cup \lbrace i \rbrace.

Print all elements of the final set S in ascending order.

Constraints

• All input values are integers.
• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq a_i, b_i \leq N
• -10^9 \leq d_i \leq 10^9

Sample Input 1

3 5
1 2 2
3 2 -3
2 1 -1
3 3 0
1 3 5

Sample Output 1

1 2 4 5

Starting with S as an empty set, perform the operation described in the problem statement for i = 1, 2, 3, 4, 5 in this order, as follows.

• For i = 1, the set S \cup \lbrace i \rbrace = \lbrace 1 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, 4) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1\rbrace.
• For i = 2, the set S \cup \lbrace i \rbrace = \lbrace 1, 2 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2\rbrace.
• For i = 3, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 3 \rbrace is not a good set.
• For i = 4, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 4 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2, 4\rbrace.
• For i = 5, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 4, 5 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2, 4, 5\rbrace.

Therefore, the final set S is \lbrace 1, 2, 4, 5\rbrace.

Sample Input 2

200000 1
1 1 1

Sample Output 2

The final set S is empty.

Sample Input 3

5 20
4 2 125421359
2 5 -191096267
3 4 -42422908
3 5 -180492387
3 3 174861038
2 3 -82998451
3 4 -134761089
3 1 -57159320
5 2 191096267
2 4 -120557647
4 2 125421359
2 3 142216401
4 5 -96172984
3 5 -108097816
1 5 -50938496
1 2 140157771
5 4 65674908
4 3 35196193
4 4 0
3 4 188711840

Sample Output 3

1 2 3 6 8 9 11 14 15 16 17 19