Problem Statement

A positive integer X is called a "Neq Number" if it satisfies the following condition:

• When X is written in decimal notation, no two adjacent characters are the same.

For example, 1, 173, and 9090 are Neq Numbers, while 22 and 6335 are not.

You are given a positive integer K. Find the K-th smallest Neq Number.

You have T test cases to solve.

Constraints

• 1 \leq T \leq 100
• 1 \leq K \leq 10^{12}
• All input values are integers.

Sample Input 1

3
25
148
998244353

Sample Output 1

27
173
2506230721

For the first test case, here are the smallest 25 Neq Numbers in ascending order:

• The nine integers from 1 to 9
• The nine integers from 10 to 19, excluding 11
• The seven integers from 20 to 27, excluding 22

Thus, the 25-th smallest Neq Number is 27.

Problem Statement

There are N distinct points on a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

We want to create as many (non-degenerate) triangles as possible using these points as the vertices. Here, the same point cannot be used as a vertex of multiple triangles.

Find the maximum number of triangles that can be created.

Constraints

• 3 \leq N \leq 300
• -10^9 \leq x_i,y_i \leq 10^9
• If i \neq j, then (x_i,y_i) \neq (x_j,y_j)
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

For example, if we create a triangle from the first, third, and sixth points and another from the second, fourth, and fifth points, we can create two triangles.

The same point cannot be used as a vertex for multiple triangles, but the triangles may have overlapping areas.

Sample Input 2

3
0 0
0 1000000000
0 -1000000000

Sample Output 2

0

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of integers from 1 to N.

For each i=1,2,\dots,N, print the minimum value of r-l+1 for a pair of integers (l,r) that satisfies all of the following conditions. If no such (l,r) exists, print -1.

• 1 \leq l \leq i \leq r \leq N
• r-l+1 is odd.
• The median of the contiguous subsequence (P_l,P_{l+1},\dots,P_r) of P is not P_i.

Here, the median of A for an integer sequence A of length L (odd) is defined as the \frac{L+1}{2}-th value of the sequence A' obtained by sorting A in ascending order.

Constraints

• 3 \leq N \leq 3 \times 10^5
• (P_1,P_2,\dots,P_N) is a permutation of integers from 1 to N.
• All input values are integers.

Sample Input 1

5
1 3 5 4 2

Sample Output 1

3 3 3 5 3

For example, when i=2, if we set (l,r)=(2,4), then r-l+1=3 is odd, and the median of (P_2,P_3,P_4)=(3,5,4) is 4, which is not P_2, so the conditions are satisfied. Thus, the answer is 3.

On the other hand, when i=4, the median of (P_l,\dots,P_r) for any of (l,r)=(4,4),(2,4),(3,5) is P_4=4. If we set (l,r)=(1,5), the median of (P_1,P_2,P_3,P_4,P_5)=(1,3,5,4,2) is 3, which is not P_4, so the conditions are satisfied. Thus, the answer is 5.

Sample Input 2

3
2 1 3

Sample Output 2

-1 3 3

When i=1, no pair of integers (l,r) satisfies the conditions.

Sample Input 3

14
7 14 6 8 10 2 9 5 4 12 11 3 13 1

Sample Output 3

5 3 3 7 3 3 3 5 3 3 5 3 3 3

Problem Statement

You are given a directed graph G with N vertices and M edges. The vertices are numbered from 1 to N, and each edge is labeled with ( or ). The i-th edge is directed from vertex u_i to vertex v_i with a label c_i. The graph does not contain multi-edges or self-loops.

In this graph, for any two vertices s and t, there is a path from s to t.

Determine if there is a walk on the graph G that satisfies all of the following conditions:

• The start and end vertices of the walk are the same.
• For i=1,2,\dots,M, the i-th edge is used at least once in the walk.
• The string obtained by arranging the labels of the edges used in the walk in the order of their usage is a regular bracket sequence.

Constraints

• 2 \leq N \leq 4000
• N \leq M \leq 8000
• 1 \leq u_i,v_i \leq N
• c_i is ( or ).
• u_i \neq v_i
• If i \neq j, then (u_i,v_i) \neq (u_j,v_j).
• All input values are integers.
• In the input graph, for any two vertices s and t, there is a path from s to t.

Sample Input 1

5 7
1 2 (
2 3 )
3 4 (
4 1 )
2 4 )
4 5 (
5 1 )

Sample Output 1

Yes

The walk that uses edges 1,2,3,4,1,5,6,7 in this order uses all the edges at least once, and the string ()()()() obtained by arranging the labels of the edges in the order of their usage is a regular bracket sequence, so all conditions are satisfied.

The walk may use the same edge multiple times or visit the same vertex multiple times.

Sample Input 2

2 2
1 2 )
2 1 )

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Problem Statement

You are given a sequence of N non-negative integers A=(A_1,A_2,\dots,A_N). Consider performing the following operation N-1 times on this sequence to obtain a sequence of length 1:

• Let n be the length of A. First, rearrange the elements in A in any order you like. Then, replace A with a sequence of n-1 non-negative integers (A_1 \oplus A_2, A_2 \oplus A_3, \dots, A_{n-1} \oplus A_n).

Here, \oplus represents the bitwise \mathrm{XOR} operation.

Let X be the value of the term contained in the sequence of length 1 obtained after N-1 operations. Find the maximum possible value of X.

Constraints

• 2 \leq N \leq 100
• 0 \leq A_i < 2^{60}
• All input values are integers.

Sample Input 1

4
1 2 3 4

Sample Output 1

7

The sequence A can be transformed into A=(7) by the following three operations:

• In the first operation, rearrange A=(1,2,3,4) to (3,1,4,2). A is replaced with (3 \oplus 1, 1 \oplus 4, 4 \oplus 2) = (2,5,6).
• In the second operation, rearrange A=(2,5,6) to (2,6,5). A is replaced with (2 \oplus 6, 6 \oplus 5) = (4,3).
• In the third operation, rearrange A=(4,3) to (4,3). A is replaced with (4 \oplus 3) = (7).

Sample Input 2

13
451745518671773958 43800508384422957 153019271028231120 577708532586013562 133532134450358663 619750463276496276 615201966367277237 943395749975730789 813856754125382728 705285621476908966 912241698686715427 951219919930656543 124032597374298654

Sample Output 2

1152905479775702586

Problem Statement

There is a blackboard with a set of positive integers written on it. Initially, the set S=\lbrace 1,2,\dots,A,A+1,A+2,\dots,A+B\rbrace is written on the blackboard.

Takahashi wants to perform the following operation N-1 times to have N sets on the blackboard:

• From the sets of integers written on the blackboard, choose a set S_0 that contains at least one element not greater than A and at least one element not less than A+1. From the chosen set S_0, choose one element a not greater than A and one element b not less than A+1. Erase the set S_0 from the blackboard and write two sets S_1 and S_2 of his choice that satisfy all of the following conditions:
  • The union of S_1 and S_2 is S_0, and they have no common elements.
  • a \in S_1, b \in S_2

Find the number of possible ways to perform the series of operations, modulo 998244353.

Here, two series of operations are distinguished when there is an i\ (1 \leq i \leq N-1) such that S_0, a, b, S_1, or S_2 chosen in the i-th operation of one series is different from that of the other series.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A,B \leq 2 \times 10^5
• N \leq A+B
• All input values are integers.

Sample Input 1

3 2 4

Sample Output 1

1728

One possible series of operations is as follows:

• Choose S_0=\lbrace 1,2,3,4,5,6\rbrace, let a=2 and b=5, and let S_1 =\lbrace 1,2,3,6\rbrace and S_2=\lbrace 4,5\rbrace. There are now two sets of integers written on the blackboard: \lbrace 1,2,3,6\rbrace and \lbrace 4,5\rbrace.
• Choose S_0=\lbrace 1,2,3,6\rbrace, let a=1 and b=3, and let S_1 = \lbrace1,2\rbrace and S_2=\lbrace 3,6\rbrace. There are now three sets of integers written on the blackboard: \lbrace 1,2\rbrace, \lbrace 3,6\rbrace, and \lbrace 4,5\rbrace.

Sample Input 2

4 1 3

Sample Output 2

6

If we let a=1 and b=2 and let S_1 = \lbrace 1\rbrace and S_2 = \lbrace 2,3,4\rbrace in the first operation, we can no longer perform the second and subsequent operations.

Do not count these cases where we cannot complete N-1 operations.

Sample Input 3

5 6 6

Sample Output 3

84486693

Sample Input 4

173173 173173 173173

Sample Output 4

446948086