meetforever/GRPO_CL huggingface dataset:
user: Given 2 integers $u$ and $v$, find the shortest array such that bitwise-xor of its elements is $u$, and the sum of its elements is $v$.


-----Input-----

The only line contains 2 integers $u$ and $v$ $(0 \le u,v \le 10^{18})$.


-----Output-----

If there's no array that satisfies the condition, print "-1". Otherwise:

The first line should contain one integer, $n$, representing the length of the desired array. The next line should contain $n$ positive integers, the array itself. If there are multiple possible answers, print any.


-----Examples-----
Input
2 4

Output
2
3 1
Input
1 3

Output
3
1 1 1
Input
8 5

Output
-1
Input
0 0

Output
0


-----Note-----

In the first sample, $3\oplus 1 = 2$ and $3 + 1 = 4$. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.
user: Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.


-----Input-----

The first line of the input contains integer n (1 ≤ n < 10^15).


-----Output-----

Print expected minimal number of digits 1.


-----Examples-----
Input
121

Output
6
user: Captain Bill the Hummingbird and his crew recieved an interesting challenge offer. Some stranger gave them a map, potion of teleportation and said that only this potion might help them to reach the treasure. 

Bottle with potion has two values x and y written on it. These values define four moves which can be performed using the potion:

  $(a, b) \rightarrow(a + x, b + y)$  $(a, b) \rightarrow(a + x, b - y)$  $(a, b) \rightarrow(a - x, b + y)$  $(a, b) \rightarrow(a - x, b - y)$ 

Map shows that the position of Captain Bill the Hummingbird is (x_1, y_1) and the position of the treasure is (x_2, y_2).

You task is to tell Captain Bill the Hummingbird whether he should accept this challenge or decline. If it is possible for Captain to reach the treasure using the potion then output "YES", otherwise "NO" (without quotes).

The potion can be used infinite amount of times.


-----Input-----

The first line contains four integer numbers x_1, y_1, x_2, y_2 ( - 10^5 ≤ x_1, y_1, x_2, y_2 ≤ 10^5) — positions of Captain Bill the Hummingbird and treasure respectively.

The second line contains two integer numbers x, y (1 ≤ x, y ≤ 10^5) — values on the potion bottle.


-----Output-----

Print "YES" if it is possible for Captain to reach the treasure using the potion, otherwise print "NO" (without quotes).


-----Examples-----
Input
0 0 0 6
2 3

Output
YES

Input
1 1 3 6
1 5

Output
NO



-----Note-----

In the first example there exists such sequence of moves:

  $(0,0) \rightarrow(2,3)$ — the first type of move  $(2,3) \rightarrow(0,6)$ — the third type of move
user: This night wasn't easy on Vasya. His favorite team lost, and he didn't find himself victorious either — although he played perfectly, his teammates let him down every time. He had to win at least one more time, but the losestreak only grew longer and longer... It's no wonder he didn't get any sleep this night at all.

In the morning, Vasya was waiting the bus to the university on the bus stop. Vasya's thoughts were hazy and so he couldn't remember the right bus' number quite right and got onto the bus with the number $n$.

In the bus, Vasya thought that he could get the order of the digits in the number of the bus wrong. Futhermore, he could "see" some digits several times, but the digits he saw were definitely in the real number of the bus. For example, if Vasya saw the number 2028, it could mean that the real bus number could be 2028, 8022, 2820 or just 820. However, numbers 80, 22208, 52 definitely couldn't be the number of the bus. Also, real bus number couldn't start with the digit 0, this meaning that, for example, number 082 couldn't be the real bus number too.

Given $n$, determine the total number of possible bus number variants.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^{18}$) — the number of the bus that was seen by Vasya. It is guaranteed that this number does not start with $0$.


-----Output-----

Output a single integer — the amount of possible variants of the real bus number.


-----Examples-----
Input
97

Output
2

Input
2028

Output
13



-----Note-----

In the first sample, only variants $97$ and $79$ are possible.

In the second sample, the variants (in the increasing order) are the following: $208$, $280$, $802$, $820$, $2028$, $2082$, $2208$, $2280$, $2802$, $2820$, $8022$, $8202$, $8220$.
user: A new delivery of clothing has arrived today to the clothing store. This delivery consists of $a$ ties, $b$ scarves, $c$ vests and $d$ jackets.

The store does not sell single clothing items — instead, it sells suits of two types:  a suit of the first type consists of one tie and one jacket;  a suit of the second type consists of one scarf, one vest and one jacket. 

Each suit of the first type costs $e$ coins, and each suit of the second type costs $f$ coins.

Calculate the maximum possible cost of a set of suits that can be composed from the delivered clothing items. Note that one item cannot be used in more than one suit (though some items may be left unused).


-----Input-----

The first line contains one integer $a$ $(1 \le a \le 100\,000)$ — the number of ties.

The second line contains one integer $b$ $(1 \le b \le 100\,000)$ — the number of scarves.

The third line contains one integer $c$ $(1 \le c \le 100\,000)$ — the number of vests.

The fourth line contains one integer $d$ $(1 \le d \le 100\,000)$ — the number of jackets.

The fifth line contains one integer $e$ $(1 \le e \le 1\,000)$ — the cost of one suit of the first type.

The sixth line contains one integer $f$ $(1 \le f \le 1\,000)$ — the cost of one suit of the second type.


-----Output-----

Print one integer — the maximum total cost of some set of suits that can be composed from the delivered items. 


-----Examples-----
Input
4
5
6
3
1
2

Output
6

Input
12
11
13
20
4
6

Output
102

Input
17
14
5
21
15
17

Output
325



-----Note-----

It is possible to compose three suits of the second type in the first example, and their total cost will be $6$. Since all jackets will be used, it's impossible to add anything to this set.

The best course of action in the second example is to compose nine suits of the first type and eleven suits of the second type. The total cost is $9 \cdot 4 + 11 \cdot 6 = 102$.
user: Given an integer $x$. Your task is to find out how many positive integers $n$ ($1 \leq n \leq x$) satisfy $$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$ where $a, b, p$ are all known constants.


-----Input-----

The only line contains four integers $a,b,p,x$ ($2 \leq p \leq 10^6+3$, $1 \leq a,b < p$, $1 \leq x \leq 10^{12}$). It is guaranteed that $p$ is a prime.


-----Output-----

Print a single integer: the number of possible answers $n$.


-----Examples-----
Input
2 3 5 8

Output
2

Input
4 6 7 13

Output
1

Input
233 233 10007 1

Output
1



-----Note-----

In the first sample, we can see that $n=2$ and $n=8$ are possible answers.
user: Recently Anton found a box with digits in his room. There are k_2 digits 2, k_3 digits 3, k_5 digits 5 and k_6 digits 6.

Anton's favorite integers are 32 and 256. He decided to compose this integers from digits he has. He wants to make the sum of these integers as large as possible. Help him solve this task!

Each digit can be used no more than once, i.e. the composed integers should contain no more than k_2 digits 2, k_3 digits 3 and so on. Of course, unused digits are not counted in the sum.


-----Input-----

The only line of the input contains four integers k_2, k_3, k_5 and k_6 — the number of digits 2, 3, 5 and 6 respectively (0 ≤ k_2, k_3, k_5, k_6 ≤ 5·10^6).


-----Output-----

Print one integer — maximum possible sum of Anton's favorite integers that can be composed using digits from the box.


-----Examples-----
Input
5 1 3 4

Output
800

Input
1 1 1 1

Output
256



-----Note-----

In the first sample, there are five digits 2, one digit 3, three digits 5 and four digits 6. Anton can compose three integers 256 and one integer 32 to achieve the value 256 + 256 + 256 + 32 = 800. Note, that there is one unused integer 2 and one unused integer 6. They are not counted in the answer.

In the second sample, the optimal answer is to create on integer 256, thus the answer is 256.
user: Mr. Bender has a digital table of size n × n, each cell can be switched on or off. He wants the field to have at least c switched on squares. When this condition is fulfilled, Mr Bender will be happy.

We'll consider the table rows numbered from top to bottom from 1 to n, and the columns — numbered from left to right from 1 to n. Initially there is exactly one switched on cell with coordinates (x, y) (x is the row number, y is the column number), and all other cells are switched off. Then each second we switch on the cells that are off but have the side-adjacent cells that are on.

For a cell with coordinates (x, y) the side-adjacent cells are cells with coordinates (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1).

In how many seconds will Mr. Bender get happy?


-----Input-----

The first line contains four space-separated integers n, x, y, c (1 ≤ n, c ≤ 10^9; 1 ≤ x, y ≤ n; c ≤ n^2).


-----Output-----

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


-----Examples-----
Input
6 4 3 1

Output
0

Input
9 3 8 10

Output
2



-----Note-----

Initially the first test has one painted cell, so the answer is 0. In the second test all events will go as is shown on the figure. [Image].
user: A little girl loves problems on bitwise operations very much. Here's one of them.

You are given two integers l and r. Let's consider the values of $a \oplus b$ for all pairs of integers a and b (l ≤ a ≤ b ≤ r). Your task is to find the maximum value among all considered ones.

Expression $x \oplus y$ means applying bitwise excluding or operation to integers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as "^", in Pascal — as «xor».


-----Input-----

The single line contains space-separated integers l and r (1 ≤ l ≤ r ≤ 10^18).

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


-----Output-----

In a single line print a single integer — the maximum value of $a \oplus b$ for all pairs of integers a, b (l ≤ a ≤ b ≤ r).


-----Examples-----
Input
1 2

Output
3

Input
8 16

Output
31

Input
1 1

Output
0
user: You are given a set of $2n+1$ integer points on a Cartesian plane. Points are numbered from $0$ to $2n$ inclusive. Let $P_i$ be the $i$-th point. The $x$-coordinate of the point $P_i$ equals $i$. The $y$-coordinate of the point $P_i$ equals zero (initially). Thus, initially $P_i=(i,0)$.

The given points are vertices of a plot of a piecewise function. The $j$-th piece of the function is the segment $P_{j}P_{j + 1}$.

In one move you can increase the $y$-coordinate of any point with odd $x$-coordinate (i.e. such points are $P_1, P_3, \dots, P_{2n-1}$) by $1$. Note that the corresponding segments also change.

For example, the following plot shows a function for $n=3$ (i.e. number of points is $2\cdot3+1=7$) in which we increased the $y$-coordinate of the point $P_1$ three times and $y$-coordinate of the point $P_5$ one time: [Image] 

Let the area of the plot be the area below this plot and above the coordinate axis OX. For example, the area of the plot on the picture above is 4 (the light blue area on the picture above is the area of the plot drawn on it).

Let the height of the plot be the maximum $y$-coordinate among all initial points in the plot (i.e. points $P_0, P_1, \dots, P_{2n}$). The height of the plot on the picture above is 3.

Your problem is to say which minimum possible height can have the plot consisting of $2n+1$ vertices and having an area equal to $k$. Note that it is unnecessary to minimize the number of moves.

It is easy to see that any answer which can be obtained by performing moves described above always exists and is an integer number not exceeding $10^{18}$.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 10^{18}$) — the number of vertices in a plot of a piecewise function and the area we need to obtain.


-----Output-----

Print one integer — the minimum possible height of a plot consisting of $2n+1$ vertices and with an area equals $k$. It is easy to see that any answer which can be obtained by performing moves described above always exists and is an integer number not exceeding $10^{18}$.


-----Examples-----
Input
4 3

Output
1

Input
4 12

Output
3

Input
999999999999999999 999999999999999986

Output
1



-----Note-----

One of the possible answers to the first example: [Image] 

The area of this plot is 3, the height of this plot is 1.

There is only one possible answer to the second example: $M M$ 

The area of this plot is 12, the height of this plot is 3.
user: One day Misha and Andrew were playing a very simple game. First, each player chooses an integer in the range from 1 to n. Let's assume that Misha chose number m, and Andrew chose number a.

Then, by using a random generator they choose a random integer c in the range between 1 and n (any integer from 1 to n is chosen with the same probability), after which the winner is the player, whose number was closer to c. The boys agreed that if m and a are located on the same distance from c, Misha wins.

Andrew wants to win very much, so he asks you to help him. You know the number selected by Misha, and number n. You need to determine which value of a Andrew must choose, so that the probability of his victory is the highest possible.

More formally, you need to find such integer a (1 ≤ a ≤ n), that the probability that $|c - a|<|c - m|$ is maximal, where c is the equiprobably chosen integer from 1 to n (inclusive).


-----Input-----

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 10^9) — the range of numbers in the game, and the number selected by Misha respectively.


-----Output-----

Print a single number — such value a, that probability that Andrew wins is the highest. If there are multiple such values, print the minimum of them.


-----Examples-----
Input
3 1

Output
2
Input
4 3

Output
2


-----Note-----

In the first sample test: Andrew wins if c is equal to 2 or 3. The probability that Andrew wins is 2 / 3. If Andrew chooses a = 3, the probability of winning will be 1 / 3. If a = 1, the probability of winning is 0.

In the second sample test: Andrew wins if c is equal to 1 and 2. The probability that Andrew wins is 1 / 2. For other choices of a the probability of winning is less.
user: Alena has successfully passed the entrance exams to the university and is now looking forward to start studying.

One two-hour lesson at the Russian university is traditionally called a pair, it lasts for two academic hours (an academic hour is equal to 45 minutes).

The University works in such a way that every day it holds exactly n lessons. Depending on the schedule of a particular group of students, on a given day, some pairs may actually contain classes, but some may be empty (such pairs are called breaks).

The official website of the university has already published the schedule for tomorrow for Alena's group. Thus, for each of the n pairs she knows if there will be a class at that time or not.

Alena's House is far from the university, so if there are breaks, she doesn't always go home. Alena has time to go home only if the break consists of at least two free pairs in a row, otherwise she waits for the next pair at the university.

Of course, Alena does not want to be sleepy during pairs, so she will sleep as long as possible, and will only come to the first pair that is presented in her schedule. Similarly, if there are no more pairs, then Alena immediately goes home.

Alena appreciates the time spent at home, so she always goes home when it is possible, and returns to the university only at the beginning of the next pair. Help Alena determine for how many pairs she will stay at the university. Note that during some pairs Alena may be at the university waiting for the upcoming pair.


-----Input-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 100) — the number of lessons at the university. 

The second line contains n numbers a_{i} (0 ≤ a_{i} ≤ 1). Number a_{i} equals 0, if Alena doesn't have the i-th pairs, otherwise it is equal to 1. Numbers a_1, a_2, ..., a_{n} are separated by spaces.


-----Output-----

Print a single number — the number of pairs during which Alena stays at the university.


-----Examples-----
Input
5
0 1 0 1 1

Output
4

Input
7
1 0 1 0 0 1 0

Output
4

Input
1
0

Output
0



-----Note-----

In the first sample Alena stays at the university from the second to the fifth pair, inclusive, during the third pair she will be it the university waiting for the next pair. 

In the last sample Alena doesn't have a single pair, so she spends all the time at home.
user: Bran and his older sister Arya are from the same house. Bran like candies so much, so Arya is going to give him some Candies.

At first, Arya and Bran have 0 Candies. There are n days, at the i-th day, Arya finds a_{i} candies in a box, that is given by the Many-Faced God. Every day she can give Bran at most 8 of her candies. If she don't give him the candies at the same day, they are saved for her and she can give them to him later.

Your task is to find the minimum number of days Arya needs to give Bran k candies before the end of the n-th day. Formally, you need to output the minimum day index to the end of which k candies will be given out (the days are indexed from 1 to n).

Print -1 if she can't give him k candies during n given days.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10000).

The second line contains n integers a_1, a_2, a_3, ..., a_{n} (1 ≤ a_{i} ≤ 100).


-----Output-----

If it is impossible for Arya to give Bran k candies within n days, print -1.

Otherwise print a single integer — the minimum number of days Arya needs to give Bran k candies before the end of the n-th day.


-----Examples-----
Input
2 3
1 2

Output
2
Input
3 17
10 10 10

Output
3
Input
1 9
10

Output
-1


-----Note-----

In the first sample, Arya can give Bran 3 candies in 2 days.

In the second sample, Arya can give Bran 17 candies in 3 days, because she can give him at most 8 candies per day.

In the third sample, Arya can't give Bran 9 candies, because she can give him at most 8 candies per day and she must give him the candies within 1 day.
user: Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk. 

Empirically Polycarp learned that the dog needs at least k walks for any two consecutive days in order to feel good. For example, if k = 5 and yesterday Polycarp went for a walk with Cormen 2 times, today he has to go for a walk at least 3 times. 

Polycarp analysed all his affairs over the next n days and made a sequence of n integers a_1, a_2, ..., a_{n}, where a_{i} is the number of times Polycarp will walk with the dog on the i-th day while doing all his affairs (for example, he has to go to a shop, throw out the trash, etc.).

Help Polycarp determine the minimum number of walks he needs to do additionaly in the next n days so that Cormen will feel good during all the n days. You can assume that on the day before the first day and on the day after the n-th day Polycarp will go for a walk with Cormen exactly k times. 

Write a program that will find the minumum number of additional walks and the appropriate schedule — the sequence of integers b_1, b_2, ..., b_{n} (b_{i} ≥ a_{i}), where b_{i} means the total number of walks with the dog on the i-th day.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 500) — the number of days and the minimum number of walks with Cormen for any two consecutive days. 

The second line contains integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 500) — the number of walks with Cormen on the i-th day which Polycarp has already planned. 


-----Output-----

In the first line print the smallest number of additional walks that Polycarp should do during the next n days so that Cormen will feel good during all days. 

In the second line print n integers b_1, b_2, ..., b_{n}, where b_{i} — the total number of walks on the i-th day according to the found solutions (a_{i} ≤ b_{i} for all i from 1 to n). If there are multiple solutions, print any of them. 


-----Examples-----
Input
3 5
2 0 1

Output
4
2 3 2

Input
3 1
0 0 0

Output
1
0 1 0

Input
4 6
2 4 3 5

Output
0
2 4 3 5
user: While playing with geometric figures Alex has accidentally invented a concept of a $n$-th order rhombus in a cell grid.

A $1$-st order rhombus is just a square $1 \times 1$ (i.e just a cell).

A $n$-th order rhombus for all $n \geq 2$ one obtains from a $n-1$-th order rhombus adding all cells which have a common side with it to it (look at the picture to understand it better).

 [Image] 

Alex asks you to compute the number of cells in a $n$-th order rhombus.


-----Input-----

The first and only input line contains integer $n$ ($1 \leq n \leq 100$) — order of a rhombus whose numbers of cells should be computed.


-----Output-----

Print exactly one integer — the number of cells in a $n$-th order rhombus.


-----Examples-----
Input
1

Output
1
Input
2

Output
5
Input
3

Output
13


-----Note-----

Images of rhombus corresponding to the examples are given in the statement.
user: A word or a sentence in some language is called a pangram if all the characters of the alphabet of this language appear in it at least once. Pangrams are often used to demonstrate fonts in printing or test the output devices.

You are given a string consisting of lowercase and uppercase Latin letters. Check whether this string is a pangram. We say that the string contains a letter of the Latin alphabet if this letter occurs in the string in uppercase or lowercase.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of characters in the string.

The second line contains the string. The string consists only of uppercase and lowercase Latin letters.


-----Output-----

Output "YES", if the string is a pangram and "NO" otherwise.


-----Examples-----
Input
12
toosmallword

Output
NO

Input
35
TheQuickBrownFoxJumpsOverTheLazyDog

Output
YES
user: You are given the current time in 24-hour format hh:mm. Find and print the time after a minutes.

Note that you should find only the time after a minutes, see the examples to clarify the problem statement.

You can read more about 24-hour format here https://en.wikipedia.org/wiki/24-hour_clock.


-----Input-----

The first line contains the current time in the format hh:mm (0 ≤ hh < 24, 0 ≤ mm < 60). The hours and the minutes are given with two digits (the hours or the minutes less than 10 are given with the leading zeroes).

The second line contains integer a (0 ≤ a ≤ 10^4) — the number of the minutes passed.


-----Output-----

The only line should contain the time after a minutes in the format described in the input. Note that you should print exactly two digits for the hours and the minutes (add leading zeroes to the numbers if needed).

See the examples to check the input/output format.


-----Examples-----
Input
23:59
10

Output
00:09

Input
20:20
121

Output
22:21

Input
10:10
0

Output
10:10