Problem Statement

ButCoder Inc. runs a programming competition site called ButCoder. In this site, a user is given an integer value called rating that represents his/her skill, which changes each time he/she participates in a contest. The initial value of a new user's rating is 0, and a user whose rating reaches K or higher is called Kaiden ("total transmission"). Note that a user's rating may become negative.

Hikuhashi is a new user in ButCoder. It is estimated that, his rating increases by A in each of his odd-numbered contests (first, third, fifth, ...), and decreases by B in each of his even-numbered contests (second, fourth, sixth, ...).

According to this estimate, after how many contests will he become Kaiden for the first time, or will he never become Kaiden?

Constraints

• 1 ≤ K, A, B ≤ 10^{18}
• All input values are integers.

Sample Input 1

4000 2000 500

Sample Output 1

5

Each time Hikuhashi participates in a contest, his rating is estimated to change as 0 → 2000 → 1500 → 3500 → 3000 → 5000 → … After his fifth contest, his rating will reach 4000 or higher for the first time.

Sample Input 2

4000 500 2000

Sample Output 2

-1

Each time Hikuhashi participates in a contest, his rating is estimated to change as 0 → 500 → -1500 → -1000 → -3000 → -2500 → … He will never become Kaiden.

Sample Input 3

1000000000000000000 2 1

Sample Output 3

1999999999999999997

The input and output values may not fit into 32-bit integers.

Problem Statement

You are given an integer N. Consider an infinite N-ary tree as shown below:

Figure: an infinite N-ary tree for the case N = 3

As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1. For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.

Regarding this tree, process Q queries. The i-th query is as follows:

• Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i.

Notes

• In a rooted tree, the lowest common ancestor (LCA) of Vertex v and w is the farthest vertex from the root that is an ancestor of both Vertex v and w. Here, a vertex is considered to be an ancestor of itself. For example, in the tree shown in Problem Statement, the LCA of Vertex 5 and 7 is Vertex 2, the LCA of Vertex 8 and 11 is Vertex 1, and the LCA of Vertex 3 and 9 is Vertex 3.

Constraints

• 1 ≤ N ≤ 10^9
• 1 ≤ Q ≤ 10^5
• 1 ≤ v_i < w_i ≤ 10^9

Sample Input 1

3 3
5 7
8 11
3 9

Sample Output 1

2
1
3

The queries in this case correspond to the examples shown in Notes.

Sample Input 2

100000 2
1 2
3 4

Sample Output 2

1
1

Problem Statement

In your garden, there is a long and narrow flowerbed that stretches infinitely to the east. You have decided to plant N kinds of flowers in this empty flowerbed. For convenience, we will call these N kinds of flowers Flower 1, 2, …, N. Also, we will call the position that is p centimeters from the west end of the flowerbed Position p.

You will plant Flower i (1 ≤ i ≤ N) as follows: first, plant one at Position w_i, then plant one every d_i centimeters endlessly toward the east. That is, Flower i will be planted at the positions w_i, w_i + d_i, w_i + 2 d_i, … Note that more than one flower may be planted at the same position.

Find the position at which the K-th flower from the west is planted. If more than one flower is planted at the same position, they are counted individually.

Constraints

• 1 ≤ N ≤ 10^5
• 1 ≤ K ≤ 10^9
• 1 ≤ w_i ≤ 10^{18}
• 1 ≤ d_i ≤ 10^9
• All input values are integers.

Sample Input 1

2 6
20 10
25 15

Sample Output 1

50

Two kinds of flowers are planted at the following positions:

• Flower 1: Position 20, 30, 40, 50, 60, …
• Flower 2: Position 25, 40, 55, 70, 85, …

The sixth flower from the west is the Flower 1 planted at Position 50. Note that the two flowers planted at Position 40 are counted individually.

Sample Input 2

3 9
10 10
10 10
10 10

Sample Output 2

30

Three flowers are planted at each of the positions 10, 20, 30, … Thus, the ninth flower from the west is planted at Position 30.

Sample Input 3

1 1000000000
1000000000000000000 1000000000

Sample Output 3

1999999999000000000

Problem Statement

You are given an undirected graph G. G has N vertices and M edges. The vertices are numbered from 1 through N, and the i-th edge (1 ≤ i ≤ M) connects Vertex a_i and b_i. G does not have self-loops and multiple edges.

You can repeatedly perform the operation of adding an edge between two vertices. However, G must not have self-loops or multiple edges as the result. Also, if Vertex 1 and 2 are connected directly or indirectly by edges, your body will be exposed to a voltage of 1000000007 volts. This must also be avoided.

Under these conditions, at most how many edges can you add? Note that Vertex 1 and 2 are never connected directly or indirectly in the beginning.

Constraints

• 2 ≤ N ≤ 10^5
• 0 ≤ M ≤ 10^5
• 1 ≤ a_i < b_i ≤ N
• All pairs (a_i, b_i) are distinct.
• Vertex 1 and 2 in G are not connected directly or indirectly by edges.

Sample Input 1

4 1
1 3

Sample Output 1

2

As shown above, two edges can be added. It is not possible to add three or more edges.

Sample Input 2

2 0

Sample Output 2

0

No edge can be added.

Sample Input 3

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

Sample Output 3

12

Problem Statement

Ringo Kingdom Congress is voting on a bill.

N members are present, and the i-th member (1 ≤ i ≤ N) has w_i white ballots and b_i blue ballots. Each member i will put all the w_i white ballots into the box if he/she is in favor of the bill, and put all the b_i blue ballots into the box if he/she is not in favor of the bill. No other action is allowed. For example, a member must not forfeit voting, or put only a part of his/her white ballots or a part of his/her blue ballots into the box.

After all the members vote, if at least P percent of the ballots in the box is white, the bill is passed; if less than P percent of the ballots is white, the bill is rejected.

In order for the bill to pass, at least how many members must be in favor of it?

Constraints

• 1 ≤ N ≤ 10^5
• 1 ≤ P ≤ 100
• 1 ≤ w_i ≤ 10^9
• 1 ≤ b_i ≤ 10^9
• All input values are integers.

Sample Input 1

4 75
1 1
1 1
1 1
1 1

Sample Output 1

3

This is a "normal" vote, where each of the four members has one white ballot and one blue ballot. For the bill to pass, at least 75 percent of the four, that is, at least three must be in favor of it.

Sample Input 2

4 75
1 1
1 1
1 1
100 1

Sample Output 2

1

The "yes" vote of the member with 100 white ballots alone is enough to pass the bill.

Sample Input 3

5 60
6 3
5 9
3 4
7 8
4 7

Sample Output 3

3

Problem Statement

In a long narrow forest stretching east-west, there are N beasts. Below, we will call the point that is p meters from the west end Point p. The i-th beast from the west (1 ≤ i ≤ N) is at Point x_i, and can be sold for s_i yen (the currency of Japan) if captured.

You will choose two integers L and R (L ≤ R), and throw a net to cover the range from Point L to Point R including both ends, [L, R]. Then, all the beasts in the range will be captured. However, the net costs R - L yen and your profit will be (the sum of s_i over all captured beasts i) - (R - L) yen.

What is the maximum profit that can be earned by throwing a net only once?

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^{15}
• 1 ≤ s_i ≤ 10^9
• All input values are integers.

Sample Input 1

5
10 20
40 50
60 30
70 40
90 10

Sample Output 1

90

If you throw a net covering the range [L = 40, R = 70], the second, third and fourth beasts from the west will be captured, generating the profit of s_2 + s_3 + s_4 - (R - L) = 90 yen. It is not possible to earn 91 yen or more.

Sample Input 2

5
10 2
40 5
60 3
70 4
90 1

Sample Output 2

5

The positions of the beasts are the same as Sample 1, but the selling prices dropped significantly, so you should not aim for two or more beasts. By throwing a net covering the range [L = 40, R = 40], you can earn s_2 - (R - L) = 5 yen, and this is the maximum possible profit.

Sample Input 3

4
1 100
3 200
999999999999999 150
1000000000000000 150

Sample Output 3

299

Problem Statement

You are given two strings s and t consisting of lowercase English letters and an integer L.

We will consider generating a string of length L by concatenating one or more copies of s and t. Here, it is allowed to use the same string more than once.

For example, when s = at, t = code and L = 6, the strings atatat, atcode and codeat can be generated.

Among the strings that can be generated in this way, find the lexicographically smallest one. In the cases given as input, it is always possible to generate a string of length L.

Constraints

• 1 ≤ L ≤ 2 × 10^5
• 1 ≤ |s|, |t| ≤ L
• s and t consist of lowercase English letters.
• It is possible to generate a string of length L in the way described in Problem Statement.

Sample Input 1

6
at
code

Sample Output 1

atatat

This input corresponds to the example shown in Problem Statement.

Sample Input 2

8
coding
festival

Sample Output 2

festival

It is possible that either s or t cannot be used at all in generating a string of length L.

Sample Input 3

8
same
same

Sample Output 3

samesame

It is also possible that s = t.

Sample Input 4

10
coin
age

Sample Output 4

ageagecoin

Problem Statement

Consider an infinite sequence a_1, a_2, … Initially, the values of all the terms are 0, and from this state we will sequentially perform Q operations. The i-th operation (1 ≤ i ≤ Q) is as follows:

• For every positive integer j, add x_i to the value of a_{j × m_i}.

Find the value of the largest term after these Q operations.

Constraints

• 1 ≤ Q ≤ 299
• 2 ≤ m_i ≤ 300
• -10^6 ≤ x_i ≤ 10^6
• All m_i are distinct.
• All input values are integers.

Sample Input 1

3
2 10
3 -20
6 15

Sample Output 1

10

The values of each terms in the sequence a_1, a_2, … change as follows:

• Before the operations: 0, 0, 0, 0, 0, 0, …
• After the 1-st operation: 0, 10, 0, 10, 0, 10, …
• After the 2-nd operation: 0, 10, -20, 10, 0, -10, …
• After the 3-rd operation: 0, 10, -20, 10, 0, 5, …

The value of the largest term after all the operations is 10.

Sample Input 2

3
10 -3
50 4
100 -5

Sample Output 2

1

Sample Input 3

5
56 114834
72 -149861
100 190757
192 -132693
240 133108

Sample Output 3

438699

Problem Statement

There are N islands floating in Ringo Sea, and M travel agents operate ships between these islands. For convenience, we will call these islands Island 1, 2, …, N, and call these agents Agent 1, 2, …, M.

The sea currents in Ringo Sea change significantly each day. Depending on the state of the sea on the day, Agent i (1 ≤ i ≤ M) operates ships from Island a_i to b_i, or Island b_i to a_i, but not both at the same time. Assume that the direction of the ships of each agent is independently selected with equal probability.

Now, Takahashi is on Island 1, and Hikuhashi is on Island 2. Let P be the probability that Takahashi and Hikuhashi can travel to the same island in the day by ships operated by the M agents, ignoring the factors such as the travel time for ships. Then, P × 2^M is an integer. Find P × 2^M modulo 10^9 + 7.

Constraints

• 2 ≤ N ≤ 15
• 1 ≤ M ≤ N(N-1)/2
• 1 ≤ a_i < b_i ≤ N
• All pairs (a_i, b_i) are distinct.

Sample Input 1

4 3
1 3
2 3
3 4

Sample Output 1

6

The 2^M = 8 scenarios shown above occur with equal probability, and Takahashi and Hikuhashi can meet on the same island in 6 of them. Thus, P = 6/2^M and P × 2^M = 6.

Sample Input 2

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

Sample Output 2

18

Sample Input 3

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

Sample Output 3

64

Problem Statement

We have 2N pots. The market price of the i-th pot (1 ≤ i ≤ 2N) is p_i yen (the currency of Japan).

Now, you and Lunlun the dachshund will alternately take one pot. You will go first, and we will continue until all the pots are taken by you or Lunlun. Since Lunlun does not know the market prices of the pots, she will always choose a pot randomly from the remaining pots with equal probability. You know this behavior of Lunlun, and the market prices of the pots.

Let the sum of the market prices of the pots you take be S yen. Your objective is to maximize the expected value of S. Find the expected value of S when the optimal strategy is adopted.

Constraints

• 1 ≤ N ≤ 10^5
• 1 ≤ p_i ≤ 2 × 10^5
• All input values are integers.

Sample Input 1

1
150000
108

Sample Output 1

150000.0

Naturally, you should choose the 150000 yen pot.

Sample Input 2

2
50000
50000
100000
100000

Sample Output 2

183333.3333333333

First, you will take one of the 100000 yen pots. The other 100000 yen pot will become yours if it is not taken in Lunlun's next turn, with probability 2/3. If it is taken, you will have to settle for a 50000 yen pot. Thus, the expected value of S when the optimal strategy is adopted is 2/3 × (100000 + 100000) + 1/3 × (100000 + 50000) = 183333.3333…