Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

• S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

Problem Statement

Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.

If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?

Constraints

• B and G are different integers between 1 and 1000, inclusive.

Sample Input 1

300 100

Sample Output 1

Bat

The bat is more expensive than the glove, so Santa will give Takahashi the bat.

Sample Input 2

334 343

Sample Output 2

Glove

The glove is more expensive than the bat, so Santa will give Takahashi the glove.

Problem Statement

You are given a positive integer N. Print a string of length (N+1), s_0s_1\ldots s_N, defined as follows.

For each i = 0, 1, 2, \ldots, N,

• if there is a divisor j of N that is between 1 and 9, inclusive, and i is a multiple of N/j, then s_i is the digit corresponding to the smallest such j (s_i will thus be one of 1, 2, ..., 9);
• if no such j exists, then s_i is -.

Constraints

• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

12

Sample Output 1

1-643-2-346-1

We will explain how to determine s_i for some i.

• For i = 0, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 1, 2, 3, 4, 6. The smallest of these is 1, so s_0 = 1.

• For i = 4, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 3, 6. The smallest of these is 3, so s_4 = 3.

• For i = 11, there are no divisors j of N between 1 and 9 such that i is a multiple of N/j, so s_{11} = -.

Sample Input 2

7

Sample Output 2

17777771

Sample Input 3

1

Sample Output 3

11

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

• First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
• Next, choose four integers A, B, C, and D satisfying all of the following.
  • 1 \le A \le B \le 10.
  • 1 \le C \le D \le 10.
• Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
  • A \le i \le B.
  • C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

• S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Sample Input 1

..........
..........
..........
..........
...######.
...######.
...######.
...######.
..........
..........

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

..........
..#.......
..........
..........
..........
..........
..........
..........
..........
..........

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

• if A _ i=-1, person i is at the front of the line;
• if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

• 1\leq N\leq3\times10 ^ 5
• A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
• There is exactly one way to arrange the N people consistent with the information given.
• All input values are integers.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

• person 1 is standing right behind person 4,
• person 2 is standing right behind person 1,
• person 3 is at the front of the line,
• person 4 is standing right behind person 5,
• person 5 is standing right behind person 3, and
• person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

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

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

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

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

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

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:

• i \times j is a square number.

Constraints

• 1 \le N \le 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

6

The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.

On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.

Sample Input 2

254

Sample Output 2

896

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.
Respond to the following Q queries in the order they are given.

The k-th query is given in the following format:

i_k x_k

• First, change A_{i_k} to x_k. This change will carry over to subsequent queries.
• Then, print the \rm{mex} of A.
  • The \rm{mex} of A is the smallest non-negative integer not contained in A.

Constraints

• All input values are integers.
• 1 \le N,Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 1 \le i_k \le N
• 0 \le x_k \le 10^9

Sample Input 1

8 5
2 0 2 2 1 1 2 5
4 3
4 4
6 3
8 1000000000
2 1

Sample Output 1

4
3
6
5
0

Initially, the sequence A is (2,0,2,2,1,1,2,5).
This input gives you five queries.

• The first query changes A_4 to 3, making A=(2,0,2,3,1,1,2,5).
  • At this point, the \rm{mex} of A is 4.
• The second query changes A_4 to 4, making A=(2,0,2,4,1,1,2,5).
  • At this point, the \rm{mex} of A is 3.
• The third query changes A_6 to 3, making A=(2,0,2,4,1,3,2,5).
  • At this point, the \rm{mex} of A is 6.
• The fourth query changes A_8 to 1000000000, making A=(2,0,2,4,1,3,2,1000000000).
  • At this point, the \rm{mex} of A is 5.
• The fifth query changes A_2 to 1, making A=(2,1,2,4,1,3,2,1000000000).
  • At this point, the \rm{mex} of A is 0.

Problem Statement

You are given a tree with N vertices. For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i and has a weight w_i.

Consider choosing some of the N-1 edges (possibly none or all). Here, for each i = 1, 2, \ldots, N, one may choose at most d_i edges incident to Vertex i. Find the maximum possible total weight of the chosen edges.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq u_i, v_i \leq N
• -10^9 \leq w_i \leq 10^9
• d_i is a non-negative integer not exceeding the degree of Vertex i.
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

28

If you choose the 1-st, 2-nd, 5-th, and 6-th edges, the total weight of those edges is 8 + 9 + 8 + 3 = 28. This is the maximum possible.

Sample Input 2

20
0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2
4 9 583
4 6 -431
5 9 325
17 6 131
17 2 -520
2 16 696
5 7 662
17 15 845
7 8 307
13 7 849
9 19 242
20 6 909
7 11 -775
17 18 557
14 20 95
18 10 646
4 3 -168
1 3 -917
11 12 30

Sample Output 2

2184