vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We are interested in obtaining two scores from a given integer:

**First score**: The sum of all the integers obtained from the power set of the digits of the given integer that have the same order 

E.g:
```
integer = 1234 ---> (1 + 2 + 3 + 4) + (12 + 13 + 14 + 23 + 24 + 34) + 
(123 + 124 + 134 + 234) + 1234 = 10 + 120 + 615 + 1234 = 1979
```
**Second score**: The sum of all the integers obtained from the all the contiguous substrings of the given integer as a string.

E.g.
```
integer = 1234 ---> (1 + 2 + 3 + 4) + (12 + 23 + 34) + (123 + 234) + 1234 = 10 + 69 + 357 + 1234 = 1670
```
The first integer, higher than ```100```, that has both scores with ```3``` common divisors is ```204```. Its first score is ```258``` and the second one ```234```. The common divisors for both scores are ```2, 3, 6```.

In fact the integers ```294``` and ```468``` are the ones in the range ```[100, 500]```, that have both scores with ```7``` common divisors, the maximum amount of common factors in that range.

Your task in this kata is to create a function that may find the integer or integers that have the maximum amount of common divisors for the scores described above.

The example given above will be:
```python
find_int_inrange(100, 500) == [7, 294, 468]
```
As you can see, the function should receive the limits of a range [a, b], and outputs an array with the maximum amount of factors, ```max_am_div``` and the found numbers sorted
```
find_int_inrange(a, b) ----> [max_am_div, k1, k2, ...., kn] # k1 < k2 < ...< kn
```
The function may output only one number.
```python
find_int_inrange(100, 300) == [7, 294]
```
Enjoy it!

Features of the random tests:
```
100 < a < b < 55000 
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everyone who has played Cut the Rope knows full well how the gameplay is organized. All levels in the game are divided into boxes. Initially only one box with some levels is available. Player should complete levels to earn stars, collecting stars opens new box with levels.

<image>

Imagine that you are playing Cut the Rope for the first time. Currently you have only the levels of the first box (by the way, it is called "Cardboard Box"). Each level is characterized by two integers: ai — how long it takes to complete the level for one star, bi — how long it takes to complete the level for two stars (ai < bi).

You want to open the next box as quickly as possible. So, you need to earn at least w stars. How do make it happen? Note that the level can be passed only once: either for one star or for two. You do not necessarily need to pass all the levels.

Input

The first line contains two integers n and w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — the number of levels in the first box and the number of stars you need to open another box. Each of the following n lines contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the attributes of the i-th level.

Output

In the first line print integer t — the minimum time you need to open the next box. 

In the next line, print n digits without spaces — the description of the optimal scenario: 

  * if you need to pass the i-th level for one star, the i-th digit should equal 1; 
  * if you need to pass the i-th level for two stars, the i-th digit should equal 2; 
  * if you do not need to pass the i-th level at all, the i-th digit should equal 0. 

Examples

Input

2 3
1 2
1 2


Output

3
12


Input

5 3
10 20
5 10
10 20
6 9
25 30


Output

14
01020

Note

In the first test sample, answer 21 is also assumed correct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is playing Air Hockey with Bob. The first person to earn seven points wins the match. Currently, Alice's score is A and Bob's score is B.

Charlie is eagerly waiting for his turn. Help Charlie by calculating the minimum number of points that will be further scored in the match before it ends. 

------ Input Format ------ 

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two space-separated integers A and B, as described in the problem statement. 

------ Output Format ------ 

For each test case, output on a new line the minimum number of points that will be further scored in the match before it ends.

------ Constraints ------ 

$1 ≤ T ≤ 50$
$0 ≤ A, B ≤ 6$

----- Sample Input 1 ------ 
4
0 0
2 5
5 2
4 3
----- Sample Output 1 ------ 
7
2
2
3

----- explanation 1 ------ 
Test case $1$: The current score is $0-0$. If either Alice or Bob scores $7$ consecutive points, then the score will become $7-0$ or $0-7$ respectively, and the game will end. It can be proven that at least $7$ points will be further scored in the match before it ends.

Test case $2$: The current score is $2-5$. If Bob scores $2$ consecutive points, then the score will become $2-7$ and the game will end. It can be proven that at least $2$ points will be further scored in the match before it ends.

Test case $3$: The current score is $5-2$. If Alice scores $2$ consecutive points, then the score will become $7-2$ and the game will end. It can be proven that at least $2$ points will be further scored in the match before it ends.

Test case $4$: The current score is $4-3$. If Alice scores $3$ consecutive points, then the score will become $7-3$ and the game will end. It can be proven that at least $3$ points will be further scored in the match before it ends.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Peter and Snow Blower

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.

Formally, we assume that Peter's machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.

Peter decided to tie his car to point *P* and now he is wondering what is the area of ​​the region that will be cleared from snow. Help him.

Input Specification:
The first line of the input contains three integers — the number of vertices of the polygon *n* (), and coordinates of point *P*.

Each of the next *n* lines contains two integers — coordinates of the vertices of the polygon in the clockwise or counterclockwise order. It is guaranteed that no three consecutive vertices lie on a common straight line.

All the numbers in the input are integers that do not exceed 1<=000<=000 in their absolute value.

Output Specification:
Print a single real value number — the area of the region that will be cleared. Your answer will be considered correct if its absolute or relative error does not exceed 10<=-<=6. 

Namely: let's assume that your answer is *a*, and the answer of the jury is *b*. The checker program will consider your answer correct, if .

Demo Input:
['3 0 0\n0 1\n-1 2\n1 2\n', '4 1 -1\n0 0\n1 2\n2 0\n1 1\n']

Demo Output:
['12.566370614359172464\n', '21.991148575128551812\n']

Note:
In the first sample snow will be removed from that area:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Classroom Watch

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Eighth-grader Vova is on duty today in the class. After classes, he went into the office to wash the board, and found on it the number *n*. He asked what is this number and the teacher of mathematics Inna Petrovna answered Vova that *n* is the answer to the arithmetic task for first-graders. In the textbook, a certain positive integer *x* was given. The task was to add *x* to the sum of the digits of the number *x* written in decimal numeral system.

Since the number *n* on the board was small, Vova quickly guessed which *x* could be in the textbook. Now he wants to get a program which will search for arbitrary values of the number *n* for all suitable values of *x* or determine that such *x* does not exist. Write such a program for Vova.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=109).

Output Specification:
In the first line print one integer *k* — number of different values of *x* satisfying the condition. 

In next *k* lines print these values in ascending order.

Demo Input:
['21\n', '20\n']

Demo Output:
['1\n15\n', '0\n']

Note:
In the first test case *x* = 15 there is only one variant: 15 + 1 + 5 = 21.

In the second test case there are no such *x*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The hobbits Frodo and Sam are carrying the One Ring to Mordor. In order not to be spotted by orcs, they decided to go through the mountains.

The mountain relief can be represented as a polyline with n points (x_i, y_i), numbered from 1 to n (x_i < x_{i + 1} for 1 ≤ i ≤ n - 1). Hobbits start their journey at the point (x_1, y_1) and should reach the point (x_n, y_n) to complete their mission.

The problem is that there is a tower with the Eye of Sauron, which watches them. The tower is located at the point (x_n, y_n) and has the height H, so the Eye is located at the point (x_n, y_n + H). In order to complete the mission successfully, the hobbits have to wear cloaks all the time when the Sauron Eye can see them, i. e. when there is a direct line from the Eye to the hobbits which is not intersected by the relief.

The hobbits are low, so their height can be considered negligibly small, but still positive, so when a direct line from the Sauron Eye to the hobbits only touches the relief, the Eye can see them.

<image> The Sauron Eye can't see hobbits when they are in the left position, but can see them when they are in the right position.

The hobbits do not like to wear cloaks, so they wear them only when they can be spotted by the Eye. Your task is to calculate the total distance the hobbits have to walk while wearing cloaks.

Input

The first line of the input contains two integers n and H (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ H ≤ 10^4) — the number of vertices in polyline and the tower height.

The next n lines contain two integers x_i, y_i each (0 ≤ x_i ≤ 4 ⋅ 10^5; 0 ≤ y_i ≤ 10^4) — the coordinates of the polyline vertices. It is guaranteed that x_i < x_{i + 1} for 1 ≤ i ≤ n - 1.

Output

Print one real number — the total distance the hobbits have to walk while wearing cloaks. Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6} — formally, if your answer is a, and the jury's answer is b, your answer will be accepted if (|a - b|)/(max(1, b)) ≤ 10^{-6}.

Examples

Input


6 10
10 40
20 10
25 30
30 15
50 15
65 30


Output


70.4034587602


Input


9 5
0 0
5 10
15 10
20 0
25 11
30 0
35 10
50 10
60 5


Output


27.2787986124


Input


2 10000
0 10000
400000 0


Output


400124.9804748512

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Old Berland Language

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Berland scientists know that the Old Berland language had exactly *n* words. Those words had lengths of *l*1,<=*l*2,<=...,<=*l**n* letters. Every word consisted of two letters, 0 and 1. Ancient Berland people spoke quickly and didn’t make pauses between the words, but at the same time they could always understand each other perfectly. It was possible because no word was a prefix of another one. The prefix of a string is considered to be one of its substrings that starts from the initial symbol.

Help the scientists determine whether all the words of the Old Berland language can be reconstructed and if they can, output the words themselves.

Input Specification:
The first line contains one integer *N* (1<=≤<=*N*<=≤<=1000) — the number of words in Old Berland language. The second line contains *N* space-separated integers — the lengths of these words. All the lengths are natural numbers not exceeding 1000.

Output Specification:
If there’s no such set of words, in the single line output NO. Otherwise, in the first line output YES, and in the next *N* lines output the words themselves in the order their lengths were given in the input file. If the answer is not unique, output any.

Demo Input:
['3\n1 2 3\n', '3\n1 1 1\n']

Demo Output:
['YES\n0\n10\n110\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oostende Beach is a very long beach located in the north of Belgium. On this beach, there are $n$ huts located along a straight line. People can rent a room in one of those huts to spend their beach vacations together with the other tenants.

Every day at lunch time, a food truck drives by to serve fries to the guests. The truck parks in front of one of the huts and people form two queues. The people staying in huts to the left of the food truck queue on the left, and the people to the right of the food truck queue on the right. The people staying in the hut in front of the food truck split their group in half, one half going to the left queue and the other half going to the right queue. If this is an odd number of people, the remaining person will go to the queue with fewer people, or choose one randomly if the queues have the same length. The food truck always positions itself so that the difference between the number of people in the left queue and the number of people in the right queue is as small as possible.

Each night the number of guests in exactly one of the huts changes. Can you help the food truck find the best position for each day?

-----Input-----
 - The first line of the input consists of two integers $1\leq n \leq 10^5$, the number of huts, and $1\leq q\leq 10^5$, the number of days.
 - The second line has $n$ integers $a_0$, $\dots $, $a_{n-1}$ satisfying $1\leq a_ i \leq 10^6$ for $0\leq i < n$, where $a_ i$ is the current number of people in hut $i$.
 - Then follow $q$ lines with two integers $0\leq i<n$ and $1\leq x \leq 10^6$. The $j^\textrm {th}$ of these lines indicates that at day $j$ the number of people in hut $i$ changes to $x$.

-----Output-----
 - Print $q$ lines: the optimal position of the food truck after each of the $q$ nights. If there are multiple optimal positions, print the smallest one.

-----Examples-----
Sample Input:
5 4
3 1 3 4 2
0 5
0 9
4 5
2 1
Sample Output:
2
1
2
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr K has a rectangular plot of land which may have marshes where fenceposts cannot be set. He wants you to find the perimeter of the largest rectangular fence that can be built on this land.

For example, in the following $m\times n=4\times4$ grid, $\boldsymbol{x}$ marks a marsh and $\boldsymbol{.}$ marks good land.

....
..x.
..x.
x...

If we number the rows and columns starting with $\mbox{1}$, we see that there are two main areas that can be fenced: $(1,1)-(3,2)$ and $(1,2)-(4,4)$.  The longest perimeter is $10$.  

Function Description

Complete the kMarsh function in the editor below.  It should print either an integer or impossible.

kMarsh has the following parameter(s):  

grid: an array of strings that represent the grid  

Input Format

The first line contains two space-separated integers $m$ and $n$, the grid rows and columns. 

Each of the next $m$ lines contains $n$ characters each describing the state of the land. 'x' (ascii value: 120) if it is a marsh and '.' ( ascii value:46) otherwise.  

Constraints

$2\leq m,n\leq500$ 

Output Format

Output contains a single integer - the largest perimeter. If the rectangular fence cannot be built, print impossible.

Sample Input 0

4 5
.....
.x.x.
.....
.....

Sample Output 0

14

Explanation 0  

The fence can be put up around the entire field. The perimeter is 
$2*(4-1)+2*(5-1)=14$.

Sample Input 1

2 2
.x
x.

Sample Output 1

impossible

Explanation 1

We need a minimum of 4 points to place the 4 corners of the fence. Hence, impossible. 

Sample Input 2

2 5
.....
xxxx.

Sample Output 2

impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja is a coder and he likes to take part in Codesorfes rounds. However, Uzhland doesn't have good internet connection, so Sereja sometimes skips rounds.

Codesorfes has rounds of two types: Div1 (for advanced coders) and Div2 (for beginner coders). Two rounds, Div1 and Div2, can go simultaneously, (Div1 round cannot be held without Div2) in all other cases the rounds don't overlap in time. Each round has a unique identifier — a positive integer. The rounds are sequentially (without gaps) numbered with identifiers by the starting time of the round. The identifiers of rounds that are run simultaneously are different by one, also the identifier of the Div1 round is always greater.

Sereja is a beginner coder, so he can take part only in rounds of Div2 type. At the moment he is taking part in a Div2 round, its identifier equals to x. Sereja remembers very well that he has taken part in exactly k rounds before this round. Also, he remembers all identifiers of the rounds he has taken part in and all identifiers of the rounds that went simultaneously with them. Sereja doesn't remember anything about the rounds he missed.

Sereja is wondering: what minimum and what maximum number of Div2 rounds could he have missed? Help him find these two numbers.


-----Input-----

The first line contains two integers: x (1 ≤ x ≤ 4000) — the round Sereja is taking part in today, and k (0 ≤ k < 4000) — the number of rounds he took part in.

Next k lines contain the descriptions of the rounds that Sereja took part in before. If Sereja took part in one of two simultaneous rounds, the corresponding line looks like: "1 num_2 num_1" (where num_2 is the identifier of this Div2 round, num_1 is the identifier of the Div1 round). It is guaranteed that num_1 - num_2 = 1. If Sereja took part in a usual Div2 round, then the corresponding line looks like: "2 num" (where num is the identifier of this Div2 round). It is guaranteed that the identifiers of all given rounds are less than x.


-----Output-----

Print in a single line two integers — the minimum and the maximum number of rounds that Sereja could have missed.


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

Output
0 0
Input
9 3
1 2 3
2 8
1 4 5

Output
2 3
Input
10 0

Output
5 9


-----Note-----

In the second sample we have unused identifiers of rounds 1, 6, 7. The minimum number of rounds Sereja could have missed equals to 2. In this case, the round with the identifier 1 will be a usual Div2 round and the round with identifier 6 will be synchronous with the Div1 round. 

The maximum number of rounds equals 3. In this case all unused identifiers belong to usual Div2 rounds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string with repeated characters, the task is to complete the function rearrangeString which rearrange characters in a string so that no two adjacent characters are same.
Note : It may be assumed that the string has only lowercase English alphabets and such transformation is always always possible.
Example 1:
Input:
S = aaabc
Output: 1
Explanation: We can transform the string
to abaca.
Example 2:
Input:
S = aaabb
Output: 1
Explanation: We can transform the string
to ababa.
 
Your Task:
Complete the function rearrangeString() which takes a string as an input parameter and returns the rearranged string. (The output will be 1 if the returned string has no adjacent character same, otherwise 0. Printing is done by the driver's code.)
Expected Time Complexity: O(N * log N), N = length of the string.
Expected Auxiliary Space: O(constant)
Constraints:
1< N < 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.

The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.


-----Input-----

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.

Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland. 

The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.

It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.

Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.


-----Output-----

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.

In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once. 


-----Example-----
Input
2
5 5
2 1
4 5
2 3
1 3
3 5
7 2
3 7
4 2

Output
3
1 3
3 5
5 4
3 2
2 1
3
2 4
3 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.