Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N\times 26
• All values in input are integers.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.

Problem Statement

Takahashi has recorded the number of steps he walked for N weeks. He walked A_i steps on the i-th day.

Find the total number of steps Takahashi walked each week.
More precisely, find the sum of the steps for the first week (the 1-st through 7-th day), the sum of the steps for the second week (the 8-th through 14-th day), and so on.

Constraints

• 1 \leq N \leq 10
• 0 \leq A_i \leq 10^5
• All input values are integers.

Sample Input 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

Sample Output 1

28000 35000

For the first week, he walked 1000+2000+3000+4000+5000+6000+7000=28000 steps, and for the second week, he walked 2000+3000+4000+5000+6000+7000+8000=35000 steps.

Sample Input 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

Sample Output 2

314333 419427 335328

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

• For each i (0\leq i \leq N-1), the length of A_i is i+1.
• For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
  • a_{i,j}=1, if j=0 or j=i.
  • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

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

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

• 3 \leq N \leq 10^5
• 1 \leq a_i \lt b_i \leq N
• The given graph is a tree.

Sample Input 1

5
1 4
2 4
3 4
4 5

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

4
2 4
1 4
2 3

Sample Output 2

No

The given graph is not a star.

Sample Input 3

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

Sample Output 3

Yes

Problem Statement

You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.

• The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
  • That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.

Constraints

• N is an integer.
• 0 \le N < 2^{60}
• In the binary representation of N, at most 15 digit positions contain 1.

Sample Input 1

11

Sample Output 1

0
1
2
3
8
9
10
11

The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:

• 0000_{(2)}=0_{(10)}
• 0001_{(2)}=1_{(10)}
• 0010_{(2)}=2_{(10)}
• 0011_{(2)}=3_{(10)}
• 1000_{(2)}=8_{(10)}
• 1001_{(2)}=9_{(10)}
• 1010_{(2)}=10_{(10)}
• 1011_{(2)}=11_{(10)}

Sample Input 2

0

Sample Output 2

0

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a 32-bit signed integer.

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

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

Problem Statement

There are N cards with an integer written on each side. Card i (1 \leq i \leq N) has an integer a_i written on the front and an integer b_i written on the back.

You may choose whether to place each card with its front or back side visible.

Determine if you can place the cards so that the sum of the visible integers exactly equals S. If possible, find a placement of the cards to realize it.

Constraints

• 1 \leq N \leq 100
• 1 \leq S \leq 10000
• 1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)
• All values in the input are integers.

Sample Input 1

3 11
1 4
2 3
5 7

Sample Output 1

Yes
THH

For example, the following placements make the sum of the visible integers exactly equal S (= 11):

• Place the 1-st card with its front side visible, 2-nd with its back, and 3-rd with its back.
• Place the 1-st card with its back side visible, 2-nd with its front, and 3-rd with its front.

Therefore, outputs like HTT and THH are accepted.

Sample Input 2

5 25
2 8
9 3
4 11
5 1
12 6

Sample Output 2

No

You cannot place the cards so that the sum of the visible integers exactly equals S (= 25).

Problem Statement

Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting N times. In each teleportation, he makes one of the following moves:

• Move from the current coordinates (x,y) to (x+A,y+B)
• Move from the current coordinates (x,y) to (x+C,y+D)
• Move from the current coordinates (x,y) to (x+E,y+F)

There are obstacles on M points (X_1,Y_1),\ldots,(X_M,Y_M) on the plane; he cannot teleport to these coordinates.

How many paths are there resulting from the N teleportations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 300
• 0 \leq M \leq 10^5
• -10^9 \leq A,B,C,D,E,F \leq 10^9
• (A,B), (C,D), and (E,F) are distinct.
• -10^9 \leq X_i,Y_i \leq 10^9
• (X_i,Y_i)\neq(0,0)
• (X_i,Y_i) are distinct.
• All values in input are integers.

Sample Input 1

2 2
1 1 1 2 1 3
1 2
2 2

Sample Output 1

5

The following 5 paths are possible:

• (0,0)\to(1,1)\to(2,3)
• (0,0)\to(1,1)\to(2,4)
• (0,0)\to(1,3)\to(2,4)
• (0,0)\to(1,3)\to(2,5)
• (0,0)\to(1,3)\to(2,6)

Sample Input 2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

Sample Output 2

0

Sample Input 3

300 0
0 0 1 0 0 1

Sample Output 3

292172978

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq r_i,c_i,x_i \leq 10^9
• (r_i,c_i) \neq (r_j,c_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4
1 1 2
1 2 9
2 1 8
3 2 3

Sample Output 1

20

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068