Problem Statement

There is a triangle ABC with positive area.
The lengths of the three sides of triangle ABC are a,b,c.

Determine whether triangle ABC is isosceles.

Constraints

• 1 \leq a,b,c \leq 10
• A triangle with side lengths a,b,c exists, and its area is positive.
• a,b,c are integers.

Sample Input 1

4 2 4

Sample Output 1

Yes

Since a=c, triangle ABC is isosceles. Thus, output Yes.

Sample Input 2

3 4 5

Sample Output 2

No

Since the three side lengths of triangle ABC are all different, it is not isosceles. Thus, output No.

Sample Input 3

10 10 10

Sample Output 3

Yes

Note that an equilateral triangle is a kind of isosceles triangle.

Problem Statement

N people participated in a programming contest consisting of M problems.
The participants are numbered person 1, person 2, \ldots, person N, and the problems are numbered problem 1, problem 2, \ldots, problem M.

In this contest, K events occurred in order; in the i-th event (1\leq i\leq K), the following happened:

• Person A_i solved problem B_i.

The same event does not occur two or more times. Also, apart from these K events, nobody solves any problem.

Output the numbers of all people who solved all problems.
If there are multiple such people, output them in ascending order of the time at which they solved all problems.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• K \geq 1
• 1 \leq A_i \leq N
• 1 \leq B_i \leq M
• If i\neq j then (A_i,B_i)\neq (A_j,B_j).
• All input values are integers.

Sample Input 1

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

Sample Output 1

3 1

In the contest, the following happened in order.

• Person 1 solved problem 1. So far, person 1 has solved only problem 1.
• Person 3 solved problem 2. So far, person 3 has solved only problem 2.
• Person 2 solved problem 1. So far, person 2 has solved only problem 1.
• Person 3 solved problem 1. So far, person 3 has solved problems 1,2. Thus, at this point person 3 has solved all problems.
• Person 1 solved problem 2. So far, person 1 has solved problems 1,2. Thus, at this point person 1 has solved all problems.

Thus, the people who solved all problems are persons 1,3, and the one who solved all problems earlier is person 3. Thus, output 3,1 in this order, separated by spaces.

Sample Input 2

2 2 2
1 1
2 2

Sample Output 2

If there is no person who solved all problems, output nothing.

Problem Statement

Takahashi is playing a game. This game has N skills numbered 1 through N.

You are given N pairs of integers (A_1,B_1), \dots,(A_N,B_N).
If (A_i,B_i)=(0,0), then Takahashi has already learned skill i.
Otherwise, Takahashi can learn skill i if and only if at least one of skills A_i and B_i has already been learned.

Including the skills already learned, find the number of skills that Takahashi can ultimately learn.

Constraints

• 1\leq N \leq 2\times 10^5
• (A_i,B_i)=(0,0) or 1\leq A_i,B_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

At first, Takahashi has already learned skill 1. Because skill 1 has been learned, skill 2 can be learned, and learning skill 2 enables learning skill 3. Since it is impossible to learn skills 4,5,6, the answer is 3.

Sample Input 2

4
0 0
0 0
0 0
0 0

Sample Output 2

4

Problem Statement

There is a grid with H rows and W columns, and each cell is painted white or black.
Let us denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W) by cell (i,j).
The state of the grid is given by H strings S_1,S_2,\ldots,S_H of length W consisting of . and #.
If the j-th character of S_i is ., then cell (i,j) is white; if it is #, then cell (i,j) is black.

By repainting some black cells (possibly zero) to white, Takahashi wants to make the grid have no 2\times 2 subgrid consisting only of black cells. More precisely, he wants to satisfy the following condition.

For any integer pair (i,j) with 1\leq i\leq H-1 and 1\leq j\leq W-1, among cells (i,j), (i,j+1), (i+1,j), and (i+1,j+1), at least one is white.

Find the minimum number of cells that need to be repainted white in order for Takahashi to achieve his goal.

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

Constraints

• 1\leq T\leq 100
• 2\leq H\leq 7
• 2\leq W\leq 7
• Each S_i is a string of length W consisting of . and #.
• T,H,W are integers.

Sample Input 1

2
5 5
####.
##.##
#####
.####
##.#.
2 2
..
..

Sample Output 1

3
0

For the first test case, the initial state of the grid is as shown in the left figure below. By repainting, for example, the three cells with numbers in the right figure below from black to white, the condition can be satisfied.

It is impossible to satisfy the condition by repainting two or fewer cells from the initial state, so output 3 on the 1-st line.

For the second test case, the grid already satisfies the condition from the beginning. Thus, output 0 on the 2-nd line.

Problem Statement

There are N sticks in a bag, with lengths A_1,\ldots,A_N.

You repeat the following operation K times.

• Take out any one of the longest sticks in the bag, split it into two equal halves, and put the two sticks back into the bag.

After K operations, among the N+K sticks in the bag, find the length of the X-th longest one.

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

Constraints

• 1 \leq T \leq 10^5
• For each test case:
  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq K \leq 10^9
  • 1 \leq X \leq N+K
• The sum of N over all test cases does not exceed 10^5.
• All input values are integers.

Sample Input 1

2
3 4 5
40 20 30
10 100 50
1 2 3 4 5 6 7 8 9 10

Sample Output 1

10.00000000000000000000
0.50000000000000000000

In the 1-st test case, initially the bag contains 3 sticks of lengths 20,30,40. The operations proceed as follows.

• Take out the stick of length 40 from the bag, split it into two sticks of length 20, and put them back. The stick lengths in the bag become 20,20,20,30.
• Take out the stick of length 30 from the bag, split it into two sticks of length 15, and put them back. The stick lengths in the bag become 15,15,20,20,20.
• Take out a stick of length 20 from the bag, split it into two sticks of length 10, and put them back. The stick lengths in the bag become 10,10,15,15,20,20.
• Take out a stick of length 20 from the bag, split it into two sticks of length 10, and put them back. The stick lengths in the bag become 10,10,10,10,15,15,20.

After the operations, the 5-th longest stick has length 10.

Problem Statement

There are N points equally spaced on a circle, numbered 1,2,\dots,N clockwise.

You are given Q queries of the following form; process them in order.

• Draw the line segment connecting points A_i and B_i. However, if this segment intersects a segment that has already been drawn, do not draw it.

Here, it is guaranteed that the 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are all distinct.

For each query, answer whether the segment was drawn.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 3\times 10^5
• 1 \leq A_i < B_i \leq N
• The 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are pairwise distinct.
• All input values are integers.

Sample Input 1

8 3
1 5
2 7
3 4

Sample Output 1

Yes
No
Yes

By the queries, the segments are drawn as in the figure.

• In the 1-st query, the segment connecting points 1 and 5 is drawn.
• In the 2-nd query, the segment connecting points 2 and 7 is not drawn because it intersects the segment drawn in the 1-st query.
• In the 3-rd query, the segment connecting points 3 and 4 is drawn.

Sample Input 2

999999 4
123456 987654
888888 999999
1 3
2 777777

Sample Output 2

Yes
No
Yes
No

Problem Statement

There is a group of N idols: idol 1, idol 2, \ldots, idol N.
There are M candidate songs, numbered song 1, song 2, \ldots, song M.
Takahashi wants to select some of these songs (possibly 0) and hold a live performance.
However, the same song can be selected at most once.

Idol i (1\leq i\leq N) can dance up to A_i songs.
In the live performance, song j (1\leq j\leq M) requires B_j idols to dance, and (regardless of who dances) the excitement of that song is C_j.

Takahashi selects the songs to be performed and, for each selected song, the idols who will dance, without exceeding each idol’s allowed number of dances. Find the maximum possible sum of excitement of the selected songs.

Constraints

• 1\leq N\leq 100
• 1\leq M\leq 100
• 0\leq A_i\leq M
• 0\leq B_i\leq N
• 0\leq C_i\leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 1 3
1 1
2 5
3 10

Sample Output 1

11

For example, he can select songs 1,3 and choose the dancers as follows.

• In song 1, only idol 3 dances.
• In song 3, idols 1,2,3 dance.

Then, the numbers of songs danced by idols 1,2,3 are 1,1,2, respectively, and the conditions are satisfied. Here, the sum of excitement of the selected songs is 1+10=11.

It is impossible to select songs so that the sum of excitement becomes larger while satisfying the conditions, so output 11.

Sample Input 2

2 6
6 0
0 1000000000
0 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1000000000

Sample Output 2

5000000000

For example, he can select songs 1,2,3,4,5 and choose the dancers as follows.

• In song 1, nobody dances.
• In song 2, nobody dances.
• In song 3, only idol 1 dances.
• In song 4, only idol 1 dances.
• In song 5, only idol 1 dances.

Then, the sum of excitement of the selected songs is 5000000000, and this is maximum.