Problem Statement

There are four cards with integers A,B,C,D written on them.
Determine whether a Full House can be formed by adding one card.

A set of five cards is called a Full House if and only if the following condition is satisfied:

• For two distinct integers x and y, there are three cards with x written on them and two cards with y written on them.

Constraints

• All input values are integers.
• 1 \le A,B,C,D \le 13

Sample Input 1

7 7 7 1

Sample Output 1

Yes

Adding 1 to 7,7,7,1 forms a Full House.

Sample Input 2

13 12 11 10

Sample Output 2

No

Adding anything to 13,12,11,10 does not form a Full House.

Sample Input 3

3 3 5 5

Sample Output 3

Yes

Adding 3,3,5,5 to 3 forms a Full House.
Also, adding 5 forms a Full House.

Sample Input 4

8 8 8 8

Sample Output 4

No

Adding anything to 8,8,8,8 does not form a Full House.
Note that five identical cards do not form a Full House.

Sample Input 5

1 3 4 1

Sample Output 5

No

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

7

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

• The length of the string written on the spine is N.
• For each rib i = 1, \dots, N, the following hold.
  • The length of the string written on rib i is A_i.
  • The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
• Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

• Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

• N is an integer.
• 1 \leq N \leq 10
• A_i and B_i are integers. (1 \leq i \leq N)
• 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
• M is an integer.
• 1 \leq M \leq 200\,000
• S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
• 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
• S_1, \cdots, S_M are pairwise distinct.

Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

• The length of retro is 5.
• For each rib, the following hold.
  • The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
  • The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
  • The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
  • The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
  • The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.

Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

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

There is a grid with H rows and W columns. Initially, all cells are painted with color 0.

You will perform the following operations in the order i = 1, 2, \ldots, M.

• If T_i = 1, repaint all cells in the A_i-th row with color X_i.

• If T_i = 2, repaint all cells in the A_i-th column with color X_i.

After all operations are completed, for each color i that exists on the grid, find the number of cells that are painted with color i.

Constraints

• 1 \leq H, W, M \leq 2 \times 10^5
• T_i \in \lbrace 1, 2 \rbrace
• 1 \leq A_i \leq H for each i such that T_i = 1,
• 1 \leq A_i \leq W for each i such that T_i = 2.
• 0 \leq X_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
0 5
2 4
5 3

The operations will change the colors of the cells in the grid as follows:

0000   0000   0000   0000   0000
0000 → 5555 → 5550 → 5550 → 5550 
0000   0000   0000   3333   2222

Eventually, there are five cells painted with color 0, four with color 2, and three with color 5.

Sample Input 2

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

Sample Output 2

1
10000 1

Sample Input 3

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

Sample Output 3

5
6 5
7 5
8 5
9 5
10 5

Problem Statement

You are given a tree with N vertices numbered from 1 to N and an integer K. The i-th edge bidirectionally connects vertices u_i and v_i.

You are currently at vertex 1. You can repeat the following operation zero or more times:

• Choose a vertex whose distance from the vertex you are currently at is K, and move to that vertex. Here, the distance between two vertices is the number of edges in the simple path connecting the two vertices.

For each k=2,\ldots,N, determine whether you can move to vertex k by repeating the operation, and if you can move, find the minimum number of operations.

You have T test cases, so solve each of them.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 2\times 10^5
• 1\leq K\leq 20
• 1\leq u_i\lt v_i\leq N
• The given graph is a tree.
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

-1 1 1 -1 2

This sample input/output consists of one test case.

The vertices whose distance from vertex 1 is 2 are vertices 3 and 4, so you can move to these two vertices with one operation.

Also, by moving from vertex 1 to vertex 4, then moving to vertex 6 whose distance from vertex 4 is 2, you can move to vertex 6 with two operations.

You cannot move to vertices 2 and 5 no matter how you perform the operations.

Sample Input 2

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

Sample Output 2

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