1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Beautiful Triple Pairs
Contest: Codeforces Round 946 (Div. 3)
Difficulty rating: 1400
Tags: combinatorics, data structures

Polycarp was given an array $$$a$$$ of $$$n$$$ integers. He really likes triples of numbers, so for each $$$j$$$ ($$$1 \le j \le n - 2$$$) he wrote down a triple of elements $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

Polycarp considers a pair of triples $$$b$$$ and $$$c$$$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:

- $$$b_1 \ne c_1$$$ and $$$b_2 = c_2$$$ and $$$b_3 = c_3$$$;
- $$$b_1 = c_1$$$ and $$$b_2 \ne c_2$$$ and $$$b_3 = c_3$$$;
- $$$b_1 = c_1$$$ and $$$b_2 = c_2$$$ and $$$b_3 \ne c_3$$$.

Find the number of beautiful pairs of triples among the written triples $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases in the test does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

Note that the answer may not fit into 32-bit data types.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$a = [3, 2, 2, 2, 3]$$$, Polycarp will write the following triples:

1. $$$[3, 2, 2]$$$;
2. $$$[2, 2, 2]$$$;
3. $$$[2, 2, 3]$$$.

In the third example, $$$a = [1, 2, 3, 2, 2, 3, 4, 2]$$$, Polycarp will write the following triples:

1. $$$[1, 2, 3]$$$;
2. $$$[2, 3, 2]$$$;
3. $$$[3, 2, 2]$$$;
4. $$$[2, 2, 3]$$$;
5. $$$[2, 3, 4]$$$;
6. $$$[3, 4, 2]$$$;

Example input:
8
5
3 2 2 2 3
5
1 2 1 2 1
8
1 2 3 2 2 3 4 2
4
2 1 1 1
8
2 1 1 2 1 1 1 1
7
2 1 1 1 1 1 1
6
2 1 1 1 1 1
5
2 1 1 1 1

Example output:
2
0
3
1
8
4
3
2

Editorial:
To consider each pair only once, we will go from left to right and while adding a new triplet, we will add to the answer the number of already added triplets that form a beautiful pair with the current one.
We will maintain a map with triplets, to denote a triplet with an error, we will place $$$0$$$ (or any other value that cannot occur in the array $$$a$$$) in place of the error.
Thus, for each triplet $$$b$$$, the already found triplets $$$(0, b_2, b_3)$$$, $$$(b_1, 0, b_3)$$$, $$$(b_1, b_2, 0)$$$ will be good. In each case, triplets equal to $$$b$$$ will also be included, so they need to be subtracted from each of the three cases.
Money Buys Happiness
Contest: Codeforces Round 946 (Div. 3)
Difficulty rating: 1800
Tags: dp

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $$$m$$$ months, starting with no money, Charlie will work hard and earn $$$x$$$ pounds per month. For the $$$i$$$-th month $$$(1 \le i \le m)$$$, there'll be a single opportunity of paying cost $$$c_i$$$ pounds to obtain happiness $$$h_i$$$.

Borrowing is not allowed. Money earned in the $$$i$$$-th month can only be spent in a later $$$j$$$-th month ($$$j>i$$$).

Since physicists don't code, help Charlie find the maximum obtainable sum of happiness.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers, $$$m$$$ and $$$x$$$ ($$$1 \le m \le 50$$$, $$$1 \le x \le 10^8$$$) — the total number of months and the monthly salary.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers, $$$c_i$$$ and $$$h_i$$$ ($$$0 \le c_i \le 10^8$$$, $$$1 \le h_i \le 10^3$$$) — the cost and happiness on offer for the $$$i$$$-th month. Note that some happiness may be free ($$$c_i=0$$$ for some $$$i$$$'s).

It is guaranteed that the sum of $$$\sum_i h_i$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print a single integer, the maximum sum of happiness Charlie could obtain.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Charlie only gets paid at the end of the month, so is unable to afford anything.

In the second test case, Charlie obtains the free happiness in the first month.

In the third test case, it's optimal for Charlie to buy happiness in the second month. Even with money left at the end, Charlie could not go back in time to obtain the happiness on offer in the first month.

Example input:
7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2

Example output:
0
10
200
15
1
9
9

Editorial:
Let's consider the classic knapsack problem. Let $$$dp[j]$$$ be the minimum cost required to achieve happiness $$$j$$$. In the $$$i$$$-th month, we iterate through $$$dp[k]$$$ and check if $$$dp[k]+c_i \le (i-1) \cdot x$$$, and if so, we can afford to transition to $$$dp[k+h_i]$$$ and accordingly update $$$dp[k+h_i]$$$.
The complexity is $$$O(m \cdot \sum_i h_i)$$$ for each set of input data.
Money Buys Less Happiness Now
Contest: Codeforces Round 946 (Div. 3)
Difficulty rating: 2000
Tags: data structures, greedy, sortings

You can never buy enough happiness, so here we go again! In this version, you can only buy $$$h_i = 1$$$ unit of happiness each month, but the number of months is hugely increased. We are in the realm of quantum happiness and time dilation.

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $$$m$$$ months, starting with no money, Charlie will work hard and earn $$$x$$$ pounds per month. For the $$$i$$$-th month $$$(1 \le i \le m)$$$, there'll be a single opportunity of paying cost $$$c_i$$$ pounds to obtain one unit of happiness. You cannot buy more than one unit each month.

Borrowing is not allowed. Money earned in the $$$i$$$-th month can only be spent in a later $$$j$$$-th month ($$$j>i$$$).

Since physicists don't code, help Charlie find the maximum reachable units of happiness.

Input format:
The first line of the input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers, $$$m$$$ and $$$x$$$ ($$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le x \le 10^3$$$) — the total number of months and the monthly salary.

The second line of each test case contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \leq c_i \leq 10^3$$$) — the cost of one unit of happiness for each month.

It is guaranteed that sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one integer — the maximal amount of happiness Charlie can get.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
3 3
2 2 2
6 5
2 2 8 2 6 8
6 4
4 10 3 8 6 10
2 1
1 1
4 1
4 1 3 1
4 2
1 3 4 3

Example output:
2
4
3
1
2
1

Editorial:
Let us consider the smallest element $$$c_m$$$ (and the rightmost if equal). Suppose we do not take it. Now, we emulate the decisions from the first month up to month $$$m$$$. Note that if we chose some element on the left of $$$m$$$ we could have chosen the smallest one $$$c_m$$$ instead. Thus, we can go greedy: go over the costs in the sorted order and check whether we can take it. To check whether there are enough pounds from the previous months we can use the segment tree. When we take the happiness during month $$$m$$$ we need to reduce the amount of pounds on the left by $$$c_m$$$.
This greedy approach can be implemented simpler. We just need to go over the costs from the first month and maintain the heap (or set/priority queue) of chosen costs. When we go over a new cost we check whether we can pay for it and, if positive, we add it to our answer. Otherwise, we remove the largest chosen cost from the heap, compare it with the current cost, and put back the smaller one.
Beautiful Sequence
Contest: CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: brute force, greedy

A sequence of $$$m$$$ integers $$$a_{1}, a_{2}, \ldots, a_{m}$$$ is good, if and only if there exists at least one $$$i$$$ ($$$1 \le i \le m$$$) such that $$$a_{i} = i$$$. For example, $$$[3,2,3]$$$ is a good sequence, since $$$a_{2} = 2$$$, $$$a_{3} = 3$$$, while $$$[3,1,1]$$$ is not a good sequence, since there is no $$$i$$$ such that $$$a_{i} = i$$$.

A sequence $$$a$$$ is beautiful, if and only if there exists at least one subsequence of $$$a$$$ satisfying that this subsequence is good. For example, $$$[4,3,2]$$$ is a beautiful sequence, since its subsequence $$$[4,2]$$$ is good, while $$$[5,3,4]$$$ is not a beautiful sequence.

A sequence $$$b$$$ is a subsequence of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements.

Now you are given a sequence, check whether it is beautiful or not.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. Their description follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the given sequence.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$), representing the sequence.

Output format:
For each test case, output "YES" or "NO"(without quotes) in one line, representing whether the given sequence is beautiful.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the good subsequence is $$$b=[3,2]$$$, where $$$b_{2} = 2$$$.

In the second test case, the good subsequence is $$$b=[2,4,3]$$$, where $$$b_{3} = 3$$$.

In the fourth test case, the good subsequence is $$$b=[1]$$$, where $$$b_{1} = 1$$$.

In the fifth test case, the good subsequence is $$$b=[2,2]$$$, where $$$b_{2} = 2$$$.

Example input:
7
3
3 2 1
4
2 4 3 5
5
2 3 5 5 6
2
3 1
5
2 4 5 2 3
4
5 6 7 8
6
6 5 4 3 2 1

Example output:
YES
YES
NO
YES
YES
NO
YES

Editorial:
The necessary and sufficient condition for a beautiful sequence is that there exists one $$$i$$$, such that $$$a_{i} \le i$$$. Just check the sequence for the condition.
Candies
Contest: CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: constructive algorithms, math, number theory

This problem is about candy. Initially, you only have $$$1$$$ candy, and you want to have exactly $$$n$$$ candies.

You can use the two following spells in any order at most $$$40$$$ times in total.

- Assume you have $$$x$$$ candies now. If you use the first spell, then $$$x$$$ candies become $$$2x-1$$$ candies.
- Assume you have $$$x$$$ candies now. If you use the second spell, then $$$x$$$ candies become $$$2x+1$$$ candies.

Construct a sequence of spells, such that after using them in order, you will have exactly $$$n$$$ candies, or determine it's impossible.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Their description follows.

Each test case contains one line with a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the required final number of candies.

Output format:
For each test case, output the following.

If it's possible to eventually have $$$n$$$ candies within $$$40$$$ spells, in the first line print an integer $$$m$$$ ($$$1 \le m \le 40$$$), representing the total number of spells you use.

In the second print $$$m$$$ integers $$$a_{1}, a_{2}, \ldots, a_{m}$$$ ($$$a_{i}$$$ is $$$1$$$ or $$$2$$$) separated by spaces, where $$$a_{i} = 1$$$ means that you use the first spell in the $$$i$$$-th step, while $$$a_{i} = 2$$$ means that you use the second spell in the $$$i$$$-th step.

Note that you do not have to minimize $$$m$$$, and if there are multiple solutions, you may output any one of them.

If it's impossible, output $$$-1$$$ in one line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For $$$n=3$$$, you can just use the second spell once, and then have $$$2 \cdot 1 + 1 = 3$$$ candies.

For $$$n=7$$$, you can use the second spell twice. After the first step, you will have $$$3$$$ candies. And after the second step, you will have $$$2 \cdot 3 + 1 = 7$$$ candies.

Example input:
4
2
3
7
17

Example output:
-1
1
2 
2
2 2 
4
2 1 1 1

Editorial:
First, we notice that after each operation, the number of candies is always a odd number. So even numbers can not be achieved.
Then consider how the binary representation changes for a odd number $$$x$$$, after turn it into $$$2x+1$$$ or $$$2x-1$$$.
• For the $$$2x + 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 11}$$$.
• For the $$$2x - 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 01}$$$.
So, the operation is just insert a $$$0/1$$$ before the last digit. And the answer for an odd $$$n$$$ is just the binary representation of $$$n$$$, after removing the last digit.
Monsters
Contest: CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2100
Tags: brute force, data structures, dfs and similar, dsu, graphs, greedy

There is an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Initially, for each vertex $$$i$$$, there is a monster with danger $$$a_{i}$$$ on that vertex. For a monster with danger $$$a_{i}$$$, you can defeat it if and only if you have defeated at least $$$a_{i}$$$ other monsters before.

Now you want to defeat all the monsters. First, you choose some vertex $$$s$$$ and defeat the monster on that vertex (since you haven't defeated any monsters before, $$$a_{s}$$$ has to be $$$0$$$). Then, you can move through the edges. If you want to move from vertex $$$u$$$ to vertex $$$v$$$, then the following must hold: either the monster on vertex $$$v$$$ has been defeated before, or you can defeat it now. For the second case, you defeat the monster on vertex $$$v$$$ and reach vertex $$$v$$$.

You can pass the vertices and the edges any number of times. Determine whether you can defeat all the monsters or not.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Their description follows.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph respectively.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$0 \le a_{i} \le n$$$) — the dangers of monsters on corresponding vertices.

For the following $$$m$$$ lines, each line contains two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$), describing an edge connecting vertex $$$u$$$ and vertex $$$v$$$. It is guaranteed that there are no multi-edges or self-loops in the graph.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output "YES" if you can defeat all the monsters, or "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can start at vertex $$$3$$$ and defeat the monster on it, before you go to vertices $$$2$$$, $$$1$$$ in this order, defeating the monsters on them as well. Then you return to vertex $$$3$$$, and go to vertex $$$4$$$, defeating the monster on it.

In the third test case, there is no path to vertex $$$4$$$ if you start at vertex $$$1$$$. Also, there is no path to vertices $$$1$$$, $$$2$$$, and $$$3$$$ if you start at vertex $$$4$$$.

Example input:
5
4 3
2 1 0 3
1 2
2 3
3 4
6 6
0 1 2 3 0 1
1 2
2 3
3 4
4 5
4 6
5 6
4 3
0 1 2 0
1 2
2 3
1 3
4 6
1 1 1 0
1 2
3 2
4 3
2 4
4 1
1 3
5 5
0 1 3 2 0
1 2
2 3
3 4
4 5
3 5

Example output:
YES
YES
NO
YES
NO

Editorial:
Last Number
Contest: CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2900
Tags: combinatorics, math

You are given a multiset $$$S$$$. Initially, $$$S = \{1,2,3, \ldots, n\}$$$.

You will perform the following operation $$$n-1$$$ times.

- Choose the largest number $$$S_{\text{max}}$$$ in $$$S$$$ and the smallest number $$$S_{\text{min}}$$$ in $$$S$$$. Remove the two numbers from $$$S$$$, and add $$$S_{\text{max}} - S_{\text{min}}$$$ into $$$S$$$.

It's easy to show that there will be exactly one number left after $$$n-1$$$ operations. Output that number.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Their description follows.

For each test case, one single line contains a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the initial size of the multiset $$$S$$$.

Output format:
For each test case, output an integer denoting the only number left after $$$n-1$$$ operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
We show how the multiset $$$S$$$ changes for $$$n=4$$$.

- Operation $$$1$$$: $$$S=\{1,2,3,4\}$$$, remove $$$4$$$, $$$1$$$, add $$$3$$$.
- Operation $$$2$$$: $$$S=\{2,3,3\}$$$, remove $$$3$$$, $$$2$$$, add $$$1$$$.
- Operation $$$3$$$: $$$S=\{1,3\}$$$, remove $$$3$$$, $$$1$$$, add $$$2$$$.
- Final: $$$S = \{2\}$$$.

Thus, the answer for $$$n = 4$$$ is $$$2$$$.

Example input:
5
2
4
7
15
177567

Example output:
1
2
2
4
33914

Editorial:
Maxim and Discounts
Contest: Codeforces Round 160 (Div. 1)
Difficulty rating: 1400
Tags: greedy, sortings

Maxim always goes to the supermarket on Sundays. Today the supermarket has a special offer of discount systems.

There are m types of discounts. We assume that the discounts are indexed from 1 to m. To use the discount number i, the customer takes a special basket, where he puts exactly qi items he buys. Under the terms of the discount system, in addition to the items in the cart the customer can receive at most two items from the supermarket for free. The number of the "free items" (0, 1 or 2) to give is selected by the customer. The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the qi items in the cart.

Maxim now needs to buy n items in the shop. Count the minimum sum of money that Maxim needs to buy them, if he use the discount system optimally well.

Please assume that the supermarket has enough carts for any actions. Maxim can use the same discount multiple times. Of course, Maxim can buy items without any discounts.

Input format:
The first line contains integer m (1 ≤ m ≤ 105) — the number of discount types. The second line contains m integers: q1, q2, ..., qm (1 ≤ qi ≤ 105).

The third line contains integer n (1 ≤ n ≤ 105) — the number of items Maxim needs. The fourth line contains n integers: a1, a2, ..., an (1 ≤ ai ≤ 104) — the items' prices.

The numbers in the lines are separated by single spaces.

Output format:
In a single line print a single integer — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample Maxim needs to buy two items that cost 100 and get a discount for two free items that cost 50. In that case, Maxim is going to pay 200.

In the second sample the best strategy for Maxim is to buy 3 items and get 2 items for free using the discount. In that case, Maxim is going to pay 150.

Example input:
1
2
4
50 50 100 100

Example output:
200

Example input:
2
2 3
5
50 50 50 50 50

Example output:
150

Editorial:
Maxim and Restaurant
Contest: Codeforces Round 160 (Div. 1)
Difficulty rating: 1900
Tags: dp, math, probabilities

Maxim has opened his own restaurant! The restaurant has got a huge table, the table's length is p meters.

Maxim has got a dinner party tonight, n guests will come to him. Let's index the guests of Maxim's restaurant from 1 to n. Maxim knows the sizes of all guests that are going to come to him. The i-th guest's size (ai) represents the number of meters the guest is going to take up if he sits at the restaurant table.

Long before the dinner, the guests line up in a queue in front of the restaurant in some order. Then Maxim lets the guests in, one by one. Maxim stops letting the guests in when there is no place at the restaurant table for another guest in the queue. There is no place at the restaurant table for another guest in the queue, if the sum of sizes of all guests in the restaurant plus the size of this guest from the queue is larger than p. In this case, not to offend the guest who has no place at the table, Maxim doesn't let any other guest in the restaurant, even if one of the following guests in the queue would have fit in at the table.

Maxim is now wondering, what is the average number of visitors who have come to the restaurant for all possible n! orders of guests in the queue. Help Maxim, calculate this number.

Input format:
The first line contains integer n (1 ≤ n ≤ 50) — the number of guests in the restaurant. The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 50) — the guests' sizes in meters. The third line contains integer p (1 ≤ p ≤ 50) — the table's length in meters.

The numbers in the lines are separated by single spaces.

Output format:
In a single line print a real number — the answer to the problem. The answer will be considered correct, if the absolute or relative error doesn't exceed 10 - 4.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample the people will come in the following orders:

- (1, 2, 3) — there will be two people in the restaurant;
- (1, 3, 2) — there will be one person in the restaurant;
- (2, 1, 3) — there will be two people in the restaurant;
- (2, 3, 1) — there will be one person in the restaurant;
- (3, 1, 2) — there will be one person in the restaurant;
- (3, 2, 1) — there will be one person in the restaurant.

In total we get (2 + 1 + 2 + 1 + 1 + 1) / 6 = 8 / 6 = 1.(3).

Example input:
3
1 2 3
3

Example output:
1.3333333333

Editorial:
Maxim and Matrix
Contest: Codeforces Round 160 (Div. 1)
Difficulty rating: 2000
Tags: constructive algorithms, dp, math

Maxim loves to fill in a matrix in a special manner. Here is a pseudocode of filling in a matrix of size (m + 1) × (m + 1):

Maxim asks you to count, how many numbers m (1 ≤ m ≤ n) are there, such that the sum of values in the cells in the row number m + 1 of the resulting matrix equals t.

Expression (x xor y) means applying the operation of bitwise excluding "OR" to numbers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by character "^", in Pascal — by "xor".

Input format:
A single line contains two integers n and t (1 ≤ n, t ≤ 1012, t ≤ n + 1).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
In a single line print a single integer — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1 1

Example output:
1

Example input:
3 2

Example output:
1

Editorial: