Problem Statement

Takahashi is growing a plant. Its height at the time of germination is 0\,\mathrm{cm}. Considering the day of germination as day 0, its height increases by 2^i\,\mathrm{cm} day i's night (0 \le i).

Takahashi's height is H\,\mathrm{cm}.

Every morning, Takahashi measures his height against this plant. Find the first day such that the plant's height is strictly greater than Takahashi's height in the morning.

Constraints

• 1 \leq H \leq 10^{9}
• All input values are integers.

Sample Input 1

54

Sample Output 1

6

The plant's height in the mornings of days 1, 2, 3, 4, 5, 6 will be 1\,\mathrm{cm}, 3\,\mathrm{cm}, 7\,\mathrm{cm}, 15\,\mathrm{cm}, 31\,\mathrm{cm}, 63\,\mathrm{cm}, respectively. The plant becomes taller than Takahashi in the morning day 6, so print 6.

Sample Input 2

7

Sample Output 2

4

The plant's height will be 7\,\mathrm{cm} in the morning of day 3 and 15\,\mathrm{cm} in the morning day 4. The plant becomes taller than Takahashi in the morning of day 4, so print 4. Note that, in the morning of day 3, the plant is as tall as Takahashi, but not taller.

Sample Input 3

262144

Sample Output 3

19

Problem Statement

You are given integers a, b, c, and d. Print two lines as follows.

The first line should contain the result of calculating (a + b) \times (c - d) as an integer.
The second line should contain Takahashi, regardless of the input.

Constraints

• -100 \leq a, b, c, d \leq 100
• a, b, c, and d are integers.

Sample Input 1

1 2 5 3

Sample Output 1

6
Takahashi

We have (1 + 2) \times(5 - 3) = 3 \times 2 = 6, so the first line should contain 6.
The second line should contain Takahashi. Lowercasing the first character or incorrect spelling will not be accepted, so be careful.

Sample Input 2

10 -20 30 -40

Sample Output 2

-700
Takahashi

The input or output may contain negative numbers.

Sample Input 3

100 100 100 -100

Sample Output 3

40000
Takahashi

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

• 1 \leq A \leq B \leq 10^9
• 2 \leq K \leq 10^9
• All values in input are integers.

Sample Input 1

1 4 2

Sample Output 1

2

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

0

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

6

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

• There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
• s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• A_i \neq B_i
• All values in the input are integers.

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

• For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
• For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

• Choose an arbitrary row of A and remove it.
• Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

• 1 \leq H_2 \leq H_1 \leq 10
• 1 \leq W_2 \leq W_1 \leq 10
• 1 \leq A_{i, j} \leq 10^9
• 1 \leq B_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

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

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

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

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

Problem Statement

There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.

Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.

The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.

The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.

For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.

Constraints

• 1 \leq N, M \leq 200000
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3 7
1 2 2 3 1 3 3

Sample Output 1

1
1
2
2
1
1
3

Let C_i denote the number of votes for candidate i.

• After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
• After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
• After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
• After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
• After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
• After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
• After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.

Sample Input 2

100 5
100 90 80 70 60

Sample Output 2

100
90
80
70
60

Sample Input 3

9 8
8 8 2 2 8 8 2 2

Sample Output 3

8
8
8
2
8
8
8
2

Problem Statement

Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).

Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:

• A'_1 \leq A'_k.

Since the count can be enormous, print it modulo 998244353.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 2 1

Sample Output 1

3

A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).

Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.

Sample Input 2

3
1 2 2

Sample Output 2

4

Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.

Sample Input 3

3
3 2 1

Sample Output 3

0

There may be no subsequence that satisfies the condition.

Sample Input 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

Sample Output 4

830

Problem Statement

You are given a connected simple undirected graph G with N vertices numbered 1 to N and N edges. The i-th edge connects Vertex u_i and Vertex v_i bidirectionally.

Answer the following Q queries.

• Determine whether there is a unique simple path from Vertex x_i to Vertex y_i (a simple path is a path without repetition of vertices).

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i\leq N
• (u_i,v_i) \neq (u_j,v_j) if i \neq j.
• G is a connected simple undirected graph with N vertices and N edges.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i < y_i\leq N
• All values in input are integers.

Sample Input 1

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

Sample Output 1

No
Yes
No

The simple paths from Vertex 1 to 2 are (1,2) and (1,3,2), which are not unique, so the answer to the first query is No.

The simple path from Vertex 1 to 4 is (1,4), which is unique, so the answer to the second query is Yes.

The simple paths from Vertex 1 to 5 are (1,2,5) and (1,3,2,5), which are not unique, so the answer to the third query is No.

Sample Input 2

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

Sample Output 2

Yes
No
Yes
Yes
No
No
Yes
No
Yes
No