Problem Statement

A basketball game is being played, and the score is now X-Y. Here, it is guaranteed that X \neq Y.
Can the team which is behind turn the tables with a successful three-point goal?
In other words, if the team which is behind earns three points, will its score become strictly greater than that of the other team?

Constraints

• 0 \le X \le 100
• 0 \le Y \le 100
• X \neq Y
• X and Y are integers.

Sample Input 1

3 5

Sample Output 1

Yes

The team with 3 points is behind.
After a successful 3-point goal, it will have 6 points, which is greater than that of the other team - 5.
Thus, we should print Yes.

Sample Input 2

16 2

Sample Output 2

No

The gap is too much. The team which is behind cannot overtake the other by getting 3 points.

Sample Input 3

12 15

Sample Output 3

No

A 3-point goal will tie the score but not turn the tables.

Problem Statement

Given are two N-dimensional vectors A = (A_1, A_2, A_3, \dots, A_N) and B = (B_1, B_2, B_3, \dots, B_N).
Determine whether the inner product of A and B is 0.
In other words, determine whether A_1B_1 + A_2B_2 + A_3B_3 + \dots + A_NB_N = 0.

Constraints

• 1 \le N \le 100000
• -100 \le A_i \le 100
• -100 \le B_i \le 100
• All values in input are integers.

Sample Input 1

2
-3 6
4 2

Sample Output 1

Yes

The inner product of A and B is (-3) \times 4 + 6 \times 2 = 0.

Sample Input 2

2
4 5
-1 -3

Sample Output 2

No

The inner product of A and B is 4 \times (-1) + 5 \times (-3) = -19.

Sample Input 3

3
1 3 5
3 -6 3

Sample Output 3

Yes

The inner product of A and B is 1 \times 3 + 3 \times (-6) + 5 \times 3 = 0.

Problem Statement

2^N players, labeled 1 through 2^N, will compete against each other in a single-elimination programming tournament.
The rating of Player i is A_i. Any two players have different ratings, and a match between two players always results in the victory of the player with the higher rating.

The tournament looks like a perfect binary tree.
Formally, the tournament will proceed as follows:

• For each integer i = 1, 2, 3, \dots, N in this order, the following happens.
  • For each integer j (1 \le j \le 2^{N - i}), among the players who have never lost, the player with the (2j - 1)-th smallest label and the player with the 2j-th smallest label play a match against each other.

Find the label of the player who will take second place, that is, lose in the final match.

Constraints

• 1 \le N \le 16
• 1 \le A_i \le 10^9
• A_i are pairwise different.
• All values in input are integers.

Sample Input 1

2
1 4 2 5

Sample Output 1

2

First, there will be two matches between Players 1 and 2 and between Players 3 and 4. According to the ratings, Players 2 and 4 will win.
Then, there will be a match between Players 2 and 4, and the tournament will end with Player 4 becoming champion.
The player who will lose in the final match is Player 2, so we should print 2.

Sample Input 2

2
3 1 5 4

Sample Output 2

1

First, there will be two matches between Players 1 and 2 and between Players 3 and 4. According to the ratings, Players 1 and 3 will win.
Then, there will be a match between Players 1 and 3, and the tournament will end with Player 3 becoming champion.
The player who will lose in the final match is Player 1, so we should print 1.

Sample Input 3

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

Sample Output 3

2

Problem Statement

Snuke Inc. offers various kinds of services.
A payment plan called Snuke Prime is available.
In this plan, by paying C yen (the currency of Japan) per day, you can use all services offered by the company without additional fees.
You can start your subscription to this plan at the beginning of any day and cancel your subscription at the end of any day.

Takahashi is going to use N of the services offered by the company.
He will use the i-th of those services from the beginning of the a_i-th day until the end of the b_i-th day, where today is the first day.
Without a subscription to Snuke Prime, he has to pay c_i yen per day to use the i-th service.

Find the minimum total amount of money Takahashi has to pay to use the services.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq C \leq 10^9
• 1 \leq a_i \leq b_i \leq 10^9
• 1 \leq c_i \leq 10^9
• All values in input are integers.

Sample Input 1

2 6
1 2 4
2 2 4

Sample Output 1

10

He will use the 1-st service on the 1-st and 2-nd days, and the 2-nd service on the 2-nd day.
If he subscribes to Snuke Prime only on the 2-nd day, he will pay 4 yen on the 1-st day and 6 yen on the 2-nd day, for a total of 10 yen.
It is impossible to make the total payment less than 10 yen, so we should print 10.

Sample Input 2

5 1000000000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409

Sample Output 2

163089627821228

It is optimal to do without Snuke Prime.

Sample Input 3

5 100000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409

Sample Output 3

88206004785464

Problem Statement

In Takahashi Kingdom, there are N towns, called Town 1 through Town N.
There are also M roads in the kingdom, called Road 1 through Road M. By traversing Road i, you can travel from Town X_i to Town Y_i, but not vice versa. Here, it is guaranteed that X_i < Y_i.
Gold is actively traded in this kingdom. At Town i, you can buy or sell 1 kilogram of gold for A_i yen (the currency of Japan).

Takahashi, a traveling salesman, plans to buy 1 kilogram of gold at some town, traverse one or more roads, and sell 1 kilogram of gold at another town.
Find the maximum possible profit (that is, the selling price minus the buying price) in this plan.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le X_i \lt Y_i \le N
• (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

We can achieve the profit of 3 yen, as follows:

• At Town 1, buy one kilogram of gold for 2 yen.
• Traverse Road 2 to get to Town 2.
• Traverse Road 1 to get to Town 4.
• At Town 4, sell one kilogram of gold for 5 yen.

Sample Input 2

5 5
13 8 3 15 18
2 4
1 2
4 5
2 3
1 3

Sample Output 2

10

We can achieve the profit of 10 yen, as follows:

• At Town 2, buy one kilogram of gold for 8 yen.
• Traverse Road 1 to get to Town 4.
• Traverse Road 3 to get to Town 5.
• At Town 5, sell one kilogram of gold for 18 yen.

Sample Input 3

3 1
1 100 1
2 3

Sample Output 3

-99

Note that we cannot sell gold at the town where we bought the gold, which means the answer may be negative.

Problem Statement

Takahashi has written an integer X on a blackboard. He can do the following three kinds of operations any number of times in any order:

• increase the value written on the blackboard by 1;
• decrease the value written on the blackboard by 1;
• multiply the value written on the blackboard by 2.

Find the minimum number of operations required to have Y written on the blackboard.

Constraints

• 1 \le X \le 10^{18}
• 1 \le Y \le 10^{18}
• X and Y are integers.

Sample Input 1

3 9

Sample Output 1

3

Initially, 3 is written on the blackboard. The following three operations can make it 9:

• increase the value by 1, which results in 4;
• multiply the value by 2, which results in 8;
• increase the value by 1, which results in 9.

Sample Input 2

7 11

Sample Output 2

3

The following procedure can make the value on the blackboard 11:

• decrease the value by 1, which results in 6;
• multiply the value by 2, which results in 12;
• decrease the value by 1, which results in 11.

Sample Input 3

1000000000000000000 1000000000000000000

Sample Output 3

0

If the value initially written on the blackboard equals Y, print 0.