Problem Statement

You are given an integer N between 1 and 9, inclusive, as input.

Concatenate N copies of the digit N and print the resulting string.

Constraints

• N is an integer between 1 and 9, inclusive.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit 3 to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

• Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
• S_1 \neq S_2
• T_1 \neq T_2

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

Problem Statement

A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.

Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.

Constraints

• N is an integer between 1 and 333, inclusive.

Sample Input 1

5

Sample Output 1

113

The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.

Note that the three repunits do not have to be distinct.

Sample Input 2

19

Sample Output 2

2333

Sample Input 3

333

Sample Output 3

112222222233

Problem Statement

You are given a tree with N vertices: vertex 1, vertex 2, \ldots, vertex N. The i-th edge (1\leq i\lt N) connects vertex u _ i and vertex v _ i.

Consider repeating the following operation some number of times:

• Choose one leaf vertex v and delete it along with all incident edges.

Find the minimum number of operations required to delete vertex 1.

Constraints

• 2\leq N\leq3\times10^5
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

The given graph looks like this:

For example, you can choose vertices 9,8,7,6,1 in this order to delete vertex 1 in five operations.

Vertex 1 cannot be deleted in four or fewer operations, so print 5.

Sample Input 2

6
1 2
2 3
2 4
3 5
3 6

Sample Output 2

1

In the given graph, vertex 1 is a leaf. Hence, you can choose and delete vertex 1 in the first operation.

Sample Input 3

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

Sample Output 3

12

Problem Statement

Takahashi will embark on an adventure.

During the adventure, N events will occur. The i-th event (1\leq i\leq N) is represented by a pair of integers (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) and is as follows:

• If t _ i=1, he finds one potion of type x _ i. He can choose to pick it up or discard it.
• If t _ i=2, he encounters one monster of type x _ i. If he has a potion of type x _ i, he can use one to defeat the monster. If he does not defeat it, he will be defeated.

Determine whether he can defeat all the monsters without being defeated.

If he cannot defeat all the monsters, print -1.

Otherwise, let K be the maximum number of potions he has at some point during the adventure. Let K _ {\min} be the minimum value of K across all strategies where he will not be defeated. Print the value of K _ {\min} and the actions of Takahashi that achieve K _ {\min}.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq t _ i\leq2\ (1\leq i\leq N)
• 1\leq x _ i\leq N\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

13
1 2
1 3
1 1
1 3
1 2
2 3
1 3
1 3
2 3
1 3
2 2
2 3
2 1

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:

• Find potions of types 2,3,1 in this order. Pick up all of them.
• Find potions of types 3,2 in this order. Do not pick up any of them.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Find a type-3 potion. Pick it up.
• Find a type-3 potion. Do not pick it up.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Find a type-3 potion. Pick it up.
• Encounter a type-2 monster. Use one type-2 potion to defeat it.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Encounter a type-1 monster. Use one type-1 potion to defeat it.

In this sequence of actions, the value of K is 3.

There is no way to avoid defeat with K\leq 2, so the sought value of K _ {\min} is 3. There are multiple sequences of actions that satisfy K=3 and allow him to avoid defeat; you may print any of them.

Sample Input 2

4
2 3
1 4
2 1
1 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 3

30
1 25
1 2
1 10
1 18
2 18
1 11
2 11
1 21
1 6
2 2
2 10
1 11
1 24
1 11
1 3
1 2
1 18
2 25
1 8
1 10
1 11
2 18
2 10
1 10
2 2
1 24
1 10
2 10
1 25
2 6

Sample Output 3

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

Problem Statement

There are N people standing in a line, with person i standing at the i-th position from the front.

Repeat the following operation until there is only one person left in the line:

• Remove the person at the front of the line with a probability of \frac{1}{2}, otherwise move them to the end of the line.

For each person i=1,2,\ldots,N, find the probability that person i is the last person remaining in the line, modulo 998244353. (All choices to remove or not are random and independent.)

Constraints

• 2\leq N\leq 3000
• All input values are integers.

Sample Input 1

2

Sample Output 1

332748118 665496236

Person 1 will be the last person remaining in the line with probability \frac{1}{3}.

Person 2 will be the last person remaining in the line with probability \frac{2}{3}.

Sample Input 2

5

Sample Output 2

235530465 792768557 258531487 238597268 471060930

Problem Statement

You are given a positive real number r less than 1, and a positive integer N.

Among the pair of integers (p,q) such that 0\leq p\leq q\leq N and \gcd(p,q)=1, find the one that minimizes \left\vert r-\dfrac pq\right\vert.

If multiple such pairs (p,q) exist, print the one with the smallest value of \dfrac pq.

Constraints

• 0\lt r\lt 1
• r is given as a real number with at most 18 decimal places.
• 1\leq N\leq 10^{10}
• N is an integer.

Sample Input 1

0.333
33

Sample Output 1

1 3

\left\vert0.333-\dfrac13\right\vert=\dfrac1{3000}. There is no 0\leq p\leq q\leq33,\gcd(p,q)=1 such that \left\vert0.333-\dfrac pq\right\vert\lt\dfrac1{3000}, so print 1 3.

Sample Input 2

0.45
5

Sample Output 2

2 5

\left\vert0.45-\dfrac12\right\vert=\left\vert0.45-\dfrac25\right\vert=\dfrac1{20}. There is no 0\leq p\leq q\leq5,\gcd(p,q)=1 such that \left\vert0.45-\dfrac pq\right\vert\lt\dfrac1{20}, and we have \dfrac12\gt\dfrac25, so print 2 5.

Sample Input 3

0.314159265358979323
10000

Sample Output 3

71 226

\left\vert0.314159265358979323-\dfrac{71}{226}\right\vert=\dfrac{3014435336501}{113000000000000000000}.

Sample Input 4

0.007735339533561113
7203576162

Sample Output 4

34928144 4515398949