Problem Statement

In the country of AtCoder where Takahashi lives, there is a peculiar law: "You must not write a string whose length is a multiple of 5."

Takahashi wrote a string S. Determine whether he is violating this law.

Constraints

• S is a string of length between 1 and 10, inclusive.
• S consists of lowercase English letters.

Sample Input 1

legal

Sample Output 1

Yes

legal is a string of length 5. Thus, Takahashi is violating the law, so output Yes.

Sample Input 2

atcoder

Sample Output 2

No

atcoder is a string of length 7. Thus, Takahashi is not violating the law, so output No.

Sample Input 3

illegal

Sample Output 3

No

Problem Statement

The company where Takahashi works has N employees, each assigned an employee number from 1, 2, \dots, N. There are M departments in the company, called departments 1, 2, \dots, M.

Employee i belongs to department A_i this term and will belong to department B_i next term.

For each of departments 1, 2, \dots, M, find the number of members next term minus the number of members this term.

Constraints

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

Sample Input 1

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

Sample Output 1

1
-1
-1
1

• For department 1: this term, one employee (employee number 1) belongs; next term, two employees (employee numbers 2, 3) belong.
• For department 2: this term, three employees (employee numbers 2, 4, 5) belong; next term, two employees (employee numbers 1, 4) belong.
• For department 3: this term, one employee (employee number 3) belongs; next term, no one belongs.
• For department 4: this term, no one belongs; next term, one employee (employee number 5) belongs.

Sample Input 2

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

Sample Output 2

0
4
-5
1
0

Problem Statement

Takahashi is managing the number of trees in his garden. Initially, there are no trees in the garden.

Q queries are given in order. Each query is one of the following two types. Immediately after processing each query, output the number of trees currently in the garden.

• 1 h : Add one new tree of height h to the garden.
• 2 h : Remove all trees currently in the garden whose height is at most h.

Constraints

• 1 \le Q \le 3 \times 10^5
• 1 \le h \le 10^9
• All input values are integers.

Sample Input 1

5
1 5
1 7
1 8
2 7
1 3

Sample Output 1

1
2
3
1
2

The number of trees changes as follows.

• A tree of height 5 is added. The garden contains one tree of height 5.
• A tree of height 7 is added. The garden contains two trees of heights 5, 7.
• A tree of height 8 is added. The garden contains three trees of heights 5, 7, 8.
• Trees of height at most 7 are removed. The garden contains one tree of height 8.
• A tree of height 3 is added. The garden contains two trees of heights 8, 3.

Sample Input 2

12
2 256601193
1 85138616
1 202564041
2 276477192
1 55551662
1 170271057
2 754166580
1 854388209
1 772036624
2 651124113
1 301137866
2 290875185

Sample Output 2

0
1
2
0
1
2
0
1
2
2
3
3

Problem Statement

We call a positive integer a good integer if it satisfies the following condition.

• Condition: It can be obtained by choosing one or more powers of 2 (1, 2, 4, 8, 16, \dots) (repetition and reordering allowed), concatenating them as strings, and interpreting the result as an integer.

Find the N-th smallest good integer. It is guaranteed that the N-th smallest good integer is at most 10^9.

Constraints

• N is a positive integer.
• The N-th smallest good integer is at most 10^9.

Sample Input 1

10

Sample Output 1

21

Listing good integers in ascending order gives 1, 2, 4, 8, 11, 12, 14, 16, 18, 21, \dots.

Sample Input 2

69

Sample Output 2

328

Sample Input 3

1099898

Sample Output 3

819264512

Problem Statement

Determine whether there exists a weighted undirected tree with N vertices satisfying the following condition.

• For any two integers i and j with 1 \le i \lt j \le N, the distance between vertices i and j is A_{i,j}.

Here, the distance between vertices i and j is defined as the sum of the weights of the edges on the unique simple path connecting these two vertices.

Constraints

• 2 \le N \le 3000
• 1 \le A_{i,j} \le 9999
• All input values are integers.

Sample Input 1

4
2 5 4
3 2
5

Sample Output 1

Yes

For example, the tree with the following edges satisfies the condition.

• Edge (1, 2) has weight 2.
• Edge (2, 3) has weight 3.
• Edge (2, 4) has weight 2.

Thus, output Yes.

Sample Input 2

4
2 5 4
3 2
6

Sample Output 2

No

No tree satisfying the condition exists. Thus, output No.

Sample Input 3

10
1039 1802 3781 231 5828 1944 392 262 1481
763 2742 1270 4789 905 1431 1301 442
1979 2033 5552 142 2194 2064 1205
4012 7531 2121 4173 4043 3184
6059 2175 161 493 1712
5694 6220 6090 5231
2336 2206 1347
654 1873
1743

Sample Output 3

Yes

Problem Statement

There is an undirected graph G with N vertices numbered 1 through N and zero edges.

Q queries are given. In the i-th query, an edge connecting vertices u_i and v_i is added to graph G.

Immediately after processing each query, determine whether it is possible to color each vertex of G white or black so that the following condition is satisfied, and if possible, find the minimum possible number of vertices colored black.

• For every edge, the two endpoints have different colors.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 1 \le u_i \lt v_i \le N
• (u_i, v_i) \ne (u_j, v_j) \ (i \ne j)
• All input values are integers.

Sample Input 1

4 4
1 2
2 3
3 4
1 3

Sample Output 1

1
1
2
-1

Immediately after processing queries 1, 2, 3, a valid coloring exists.

For example, immediately after processing the third query, vertices 1, 2, 3, 4 can be colored white, black, white, black, respectively. No valid coloring with fewer black vertices exists, so output 2.

Immediately after processing the fourth query, no valid coloring exists. Thus, output -1.

Sample Input 2

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

Sample Output 2

1
2
2
3
3
3
3
4
4
4

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 through N and the edges are numbered 1 through M; edge i is an undirected edge of weight W_i connecting vertices U_i and V_i.

The weight of a walk connecting two vertices is defined as the total XOR of the weights of the edges contained in the walk. If the same edge is traversed multiple times, that edge's weight contributes to the total XOR that many times.

You are given a non-negative integer K. Find the number of pairs of integers (x, y) (1 \leq x \lt y \leq N) such that the minimum weight of a walk connecting vertices x and y is at most K.

T test cases are given; solve each one.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 0 \leq K \lt 2^{30}
• 1 \leq U_i \lt V_i \leq N
• 0 \leq W_i \lt 2^{30}
• The given graph is simple and connected.
• All input values are integers.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.
• The sum of M over all test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
4 4 2
3 4 3
1 3 4
1 2 3
2 3 2
5 7 14032
1 2 24681
3 5 25665
1 5 14154
2 3 23215
1 3 21259
4 5 24874
3 4 26495
8 10 109312507
6 8 793188457
7 8 501937135
1 2 954888411
2 7 109497327
1 6 791995625
2 6 665857693
1 3 101233808
1 7 114788578
4 6 953503358
5 8 624700613

Sample Output 1

4
9
22

In the first test case, for example, the weight of the walk visiting vertices 1, 3, 2, 1, 3 in order is 4 \oplus 2 \oplus 3 \oplus 4 = 1.

It can be shown that the minimum weight of a walk connecting each pair of distinct vertices is as follows.

• Vertices 1 and 2: minimum 3
• Vertices 1 and 3: minimum 1
• Vertices 1 and 4: minimum 2
• Vertices 2 and 3: minimum 2
• Vertices 2 and 4: minimum 1
• Vertices 3 and 4: minimum 3

Among these, four pairs have a minimum value of at most K(=2). Thus, output 4 on the first line.