vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Draw Brackets!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A sequence of square brackets is regular if by inserting symbols "+" and "1" into it, you can get a regular mathematical expression from it. For example, sequences "[[]][]", "[]" and "[[][[]]]" — are regular, at the same time "][", "[[]" and "[[]]][" — are irregular. 

Draw the given sequence using a minimalistic pseudographics in the strip of the lowest possible height — use symbols '+', '-' and '|'. For example, the sequence "[[][]][]" should be represented as: 

Each bracket should be represented with the hepl of one or more symbols '|' (the vertical part) and symbols '+' and '-' as on the example which is given above.

Brackets should be drawn without spaces one by one, only dividing pairs of consecutive pairwise brackets with a single-space bar (so that the two brackets do not visually merge into one symbol). The image should have the minimum possible height. 

The enclosed bracket is always smaller than the surrounding bracket, but each bracket separately strives to maximize the height of the image. So the pair of final brackets in the example above occupies the entire height of the image.

Study carefully the examples below, they adequately explain the condition of the problem. Pay attention that in this problem the answer (the image) is unique.

Input Specification:
The first line contains an even integer *n* (2<=≤<=*n*<=≤<=100) — the length of the sequence of brackets.

The second line contains the sequence of brackets — these are *n* symbols "[" and "]". It is guaranteed that the given sequence of brackets is regular.

Output Specification:
Print the drawn bracket sequence in the format which is given in the condition. Don't print extra (unnecessary) spaces.

Demo Input:
['8\n[[][]][]\n', '6\n[[[]]]\n', '6\n[[][]]\n', '2\n[]\n', '4\n[][]\n']

Demo Output:
['+-        -++- -+\n|+- -++- -+||   |\n||   ||   |||   |\n|+- -++- -+||   |\n+-        -++- -+\n', '+-     -+\n|+-   -+|\n||+- -+||\n|||   |||\n||+- -+||\n|+-   -+|\n+-     -+\n', '+-        -+\n|+- -++- -+|\n||   ||   ||\n|+- -++- -+|\n+-        -+\n', '+- -+\n|   |\n+- -+\n', '+- -++- -+\n|   ||   |\n+- -++- -+\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Felicity is Coming!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
It's that time of the year, Felicity is around the corner and you can see people celebrating all around the Himalayan region. The Himalayan region has *n* gyms. The *i*-th gym has *g**i* Pokemon in it. There are *m* distinct Pokemon types in the Himalayan region numbered from 1 to *m*. There is a special evolution camp set up in the fest which claims to evolve any Pokemon. The type of a Pokemon could change after evolving, subject to the constraint that if two Pokemon have the same type before evolving, they will have the same type after evolving. Also, if two Pokemon have different types before evolving, they will have different types after evolving. It is also possible that a Pokemon has the same type before and after evolving. 

Formally, an evolution plan is a permutation *f* of {1,<=2,<=...,<=*m*}, such that *f*(*x*)<==<=*y* means that a Pokemon of type *x* evolves into a Pokemon of type *y*.

The gym leaders are intrigued by the special evolution camp and all of them plan to evolve their Pokemons. The protocol of the mountain states that in each gym, for every type of Pokemon, the number of Pokemon of that type before evolving any Pokemon should be equal the number of Pokemon of that type after evolving all the Pokemons according to the evolution plan. They now want to find out how many distinct evolution plans exist which satisfy the protocol.

Two evolution plans *f*1 and *f*2 are distinct, if they have at least one Pokemon type evolving into a different Pokemon type in the two plans, i. e. there exists an *i* such that *f*1(*i*)<=≠<=*f*2(*i*).

Your task is to find how many distinct evolution plans are possible such that if all Pokemon in all the gyms are evolved, the number of Pokemon of each type in each of the gyms remains the same. As the answer can be large, output it modulo 109<=+<=7.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=105, 1<=≤<=*m*<=≤<=106) — the number of gyms and the number of Pokemon types.

The next *n* lines contain the description of Pokemons in the gyms. The *i*-th of these lines begins with the integer *g**i* (1<=≤<=*g**i*<=≤<=105) — the number of Pokemon in the *i*-th gym. After that *g**i* integers follow, denoting types of the Pokemons in the *i*-th gym. Each of these integers is between 1 and *m*.

The total number of Pokemons (the sum of all *g**i*) does not exceed 5·105.

Output Specification:
Output the number of valid evolution plans modulo 109<=+<=7.

Demo Input:
['2 3\n2 1 2\n2 2 3\n', '1 3\n3 1 2 3\n', '2 4\n2 1 2\n3 2 3 4\n', '2 2\n3 2 2 1\n2 1 2\n', '3 7\n2 1 2\n2 3 4\n3 5 6 7\n']

Demo Output:
['1\n', '6\n', '2\n', '1\n', '24\n']

Note:
In the first case, the only possible evolution plan is: 

In the second case, any permutation of (1,  2,  3) is valid.

In the third case, there are two possible plans: 

In the fourth case, the only possible evolution plan is:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vanya and Cards

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vanya loves playing. He even has a special set of cards to play with. Each card has a single integer. The number on the card can be positive, negative and can even be equal to zero. The only limit is, the number on each card doesn't exceed *x* in the absolute value.

Natasha doesn't like when Vanya spends a long time playing, so she hid all of his cards. Vanya became sad and started looking for the cards but he only found *n* of them. Vanya loves the balance, so he wants the sum of all numbers on found cards equal to zero. On the other hand, he got very tired of looking for cards. Help the boy and say what is the minimum number of cards does he need to find to make the sum equal to zero?

You can assume that initially Vanya had infinitely many cards with each integer number from <=-<=*x* to *x*.

Input Specification:
The first line contains two integers: *n* (1<=≤<=*n*<=≤<=1000) — the number of found cards and *x* (1<=≤<=*x*<=≤<=1000) — the maximum absolute value of the number on a card. The second line contains *n* space-separated integers — the numbers on found cards. It is guaranteed that the numbers do not exceed *x* in their absolute value.

Output Specification:
Print a single number — the answer to the problem.

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

Demo Output:
['1\n', '2\n']

Note:
In the first sample, Vanya needs to find a single card with number -2.

In the second sample, Vanya needs to find two cards with number 2. He can't find a single card with the required number as the numbers on the lost cards do not exceed 3 in their absolute value.

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

In A.D. 2101, war was beginning. The enemy has taken over all of our bases. To recapture the bases, we decided to set up a headquarters. We need to define the location of the headquarters so that all bases are not so far away from the headquarters. Therefore, we decided to choose the location to minimize the sum of the distances from the headquarters to the furthest $K$ bases. The bases are on the 2-D plane, and we can set up the headquarters in any place on this plane even if it is not on a grid point.

Your task is to determine the optimal headquarters location from the given base positions.

* * *

Input

The input consists of a single test case in the format below.

> $N$ $K$ $x_{1}$ $y_{1}$ $\vdots$ $x_{N}$ $y_{N}$

The first line contains two integers $N$ and $K$. The integer $N$ is the number of the bases ($1 \le N \le 200$). The integer $K$ gives how many bases are considered for calculation ($1 \le K \le N$). Each of the following $N$ lines gives the x and y coordinates of each base. All of the absolute values of given coordinates are less than or equal to $1000$, i.e., $-1000 \le x_{i}, y_{i} \le 1000$ is satisfied.

Output

Output the minimum sum of the distances from the headquarters to the furthest $K$ bases. The output can contain an absolute or a relative error no more than $10^{-3}$.

Examples

Input| Output
---|---


3 1
0 1
1 0
1 1


|


0.70711



6 3
1 1
2 1
3 2
5 3
8 5
13 8


|


17.50426



9 3
573 -50
-256 158
-751 14
314 207
293 567
59 -340
-243 -22
-268 432
-91 -192


|


1841.20904






Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Misha walked through the snowy forest and he was so fascinated by the trees to decide to draw his own tree!

Misha would like to construct a rooted tree with n vertices, indexed from 1 to n, where the root has index 1. Every other vertex has a parent p_i, and i is called a child of vertex p_i. Vertex u belongs to the subtree of vertex v iff v is reachable from u while iterating over the parents (u, p_{u}, p_{p_{u}}, ...). Clearly, v belongs to its own subtree, and the number of vertices in the subtree is called the size of the subtree. Misha is only interested in trees where every vertex belongs to the subtree of vertex 1.

Below there is a tree with 6 vertices. The subtree of vertex 2 contains vertices 2, 3, 4, 5. Hence the size of its subtree is 4. 

<image>

The branching coefficient of the tree is defined as the maximum number of children in any vertex. For example, for the tree above the branching coefficient equals 2. Your task is to construct a tree with n vertices such that the sum of the subtree sizes for all vertices equals s, and the branching coefficient is minimum possible.

Input

The only input line contains two integers n and s — the number of vertices in the tree and the desired sum of the subtree sizes (2 ≤ n ≤ 10^5; 1 ≤ s ≤ 10^{10}).

Output

If the required tree does not exist, output «No». Otherwise output «Yes» on the first line, and in the next one output integers p_2, p_3, ..., p_n, where p_i denotes the parent of vertex i.

Examples

Input


3 5


Output


Yes
1 1 


Input


4 42


Output


No


Input


6 15


Output


Yes
1 2 3 1 5 

Note

Below one can find one of the possible solutions for the first sample case. The sum of subtree sizes equals 3 + 1 + 1 = 5, and the branching coefficient equals 2.

<image>

Below one can find one of the possible solutions for the third sample case. The sum of subtree sizes equals 6 + 3 + 2 + 1 + 2 + 1 = 15, and the branching coefficient equals 2.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got a robot, its task is destroying bombs on a square plane. Specifically, the square plane contains n bombs, the i-th bomb is at point with coordinates (x_{i}, y_{i}). We know that no two bombs are at the same point and that no bomb is at point with coordinates (0, 0). Initially, the robot is at point with coordinates (0, 0). Also, let's mark the robot's current position as (x, y). In order to destroy all the bombs, the robot can perform three types of operations:  Operation has format "1 k dir". To perform the operation robot have to move in direction dir k (k ≥ 1) times. There are only 4 directions the robot can move in: "R", "L", "U", "D". During one move the robot can move from the current point to one of following points: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) (corresponding to directions). It is forbidden to move from point (x, y), if at least one point on the path (besides the destination point) contains a bomb.  Operation has format "2". To perform the operation robot have to pick a bomb at point (x, y) and put it in a special container. Thus, the robot can carry the bomb from any point to any other point. The operation cannot be performed if point (x, y) has no bomb. It is forbidden to pick a bomb if the robot already has a bomb in its container.  Operation has format "3". To perform the operation robot have to take a bomb out of the container and destroy it. You are allowed to perform this operation only if the robot is at point (0, 0). It is forbidden to perform the operation if the container has no bomb. 

Help the robot and find the shortest possible sequence of operations he can perform to destroy all bombs on the coordinate plane.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of bombs on the coordinate plane. Next n lines contain two integers each. The i-th line contains numbers (x_{i}, y_{i}) ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th bomb. It is guaranteed that no two bombs are located at the same point and no bomb is at point (0, 0). 


-----Output-----

In a single line print a single integer k — the minimum number of operations needed to destroy all bombs. On the next lines print the descriptions of these k operations. If there are multiple sequences, you can print any of them. It is guaranteed that there is the solution where k ≤ 10^6.


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

Output
12
1 1 R
1 1 U
2
1 1 L
1 1 D
3
1 1 L
1 1 D
2
1 1 R
1 1 U
3

Input
3
5 0
0 5
1 0

Output
12
1 1 R
2
1 1 L
3
1 5 R
2
1 5 L
3
1 5 U
2
1 5 D
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A test for allergy is conducted over the course of several days, and consists of exposing you to different substances (so called allergens). The goal is to decide exactly which of the allergens you are allergic to. Each allergen has a live duration $D$ measured in whole days, indicating exactly how many days you will suffer from an allergic reaction if you are allergic to that particular substance. An allergic reaction starts to show almost immediately after you have been exposed to an allergen which you are allergic to. The test scheme has two action points per day:
 - At 8 o’clock each morning, at most one of the allergens is applied to your body.
 - At 8 o’clock each evening, you are examined for allergic reactions.

Thus an allergen with live duration $D$ will affect exactly $D$ allergic reaction examinations.

Of course, if you have two or more active allergens in your body at the time of an observed reaction, you cannot tell from that information only, which of the substances you are allergic to.

You want to find the shortest possible test scheme given the durations of the allergens you want to test. Furthermore, to allow simple large scale application the test scheme must be non-adaptive, i.e. the scheme should be fixed in advance. Thus you may not choose when to apply an allergen based on the outcome of previous allergic reaction examinations.

-----Input-----
The first line of the input contains a single integer $k$ ($1 \leq k \leq 20$) specifying the number of allergens being tested for. Then follow $k$ lines each containing an integer $D$ ($1 \leq D \leq 7$) specifying the live duration of each allergen.

-----Output-----
The number of days of the shortest conclusive non-adaptive test scheme.

A scheme ends the morning when you no longer have active allergens in your body, thus a test scheme for a single allergen with live duration $D$ takes $D$ days.

-----Examples-----
Sample Input:
3
2
2
2
Sample Output:
5

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
At the Byteland State University marks are strings of the same length. Mark *x* is considered better than *y* if string *y* is lexicographically smaller than *x*.

Recently at the BSU was an important test work on which Vasya recived the mark *a*. It is very hard for the teacher to remember the exact mark of every student, but he knows the mark *b*, such that every student recieved mark strictly smaller than *b*.

Vasya isn't satisfied with his mark so he decided to improve it. He can swap characters in the string corresponding to his mark as many times as he like. Now he want to know only the number of different ways to improve his mark so that his teacher didn't notice something suspicious.

More formally: you are given two strings *a*, *b* of the same length and you need to figure out the number of different strings *c* such that:

1) *c* can be obtained from *a* by swapping some characters, in other words *c* is a permutation of *a*.

2) String *a* is lexicographically smaller than *c*.

3) String *c* is lexicographically smaller than *b*.

For two strings *x* and *y* of the same length it is true that *x* is lexicographically smaller than *y* if there exists such *i*, that *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=...,<=*x**i*<=-<=1<==<=*y**i*<=-<=1,<=*x**i*<=&lt;<=*y**i*.

Since the answer can be very large, you need to find answer modulo 109<=+<=7.

Input Specification:
First line contains string *a*, second line contains string *b*. Strings *a*,<=*b* consist of lowercase English letters. Their lengths are equal and don't exceed 106.

It is guaranteed that *a* is lexicographically smaller than *b*.

Output Specification:
Print one integer  — the number of different strings satisfying the condition of the problem modulo 109<=+<=7.

Demo Input:
['abc\nddd\n', 'abcdef\nabcdeg\n', 'abacaba\nubuduba\n']

Demo Output:
['5\n', '0\n', '64\n']

Note:
In first sample from string *abc* can be obtained strings *acb*, *bac*, *bca*, *cab*, *cba*, all of them are larger than *abc*, but smaller than *ddd*. So the answer is 5.

In second sample any string obtained from *abcdef* is larger than *abcdeg*. So the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two arrays A and B each of length N.
   
Find the value \sum_{i=1}^N\sum_{j=1}^N \max(A_{i}\oplus B_{j},A_{i}\& B_{j}).  
Here \oplus and \& denote the [bitwise XOR operation] and [bitwise AND operation] respectively.

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

- The first line of input contains a single integer T - the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N - the length of arrays A and B.
- The second line of each test case contains N space-separated integers A_{1},A_{2},…,A_{N} representing the array A.
- The third line of each test case contains N space-separated integers B_{1},B_{2},…,B_{N} representing the array B.

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

For each test case, output the value \sum_{i=1}^N\sum_{j=1}^N \max(A_{i}\oplus B_{j},A_{i}\& B_{j}).

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}, B_{i} < 2^{20}$
- Sum of $N$ does not exceed $2\cdot 10^{5}$ over all test cases.

----- Sample Input 1 ------ 
3
2
3 4
1 2
1
0
0
3
2 4 3
1 2 1
----- Sample Output 1 ------ 
15
0
30
----- explanation 1 ------ 
- Test Case $1$: For the given arrays, the value is: $\max(3\oplus 1,3\& 1) + \max(3\oplus 2,3\& 2) + \max(4\oplus 1,4\& 1) + \max(4\oplus 2,4\& 2) = 2 + 2 + 5 + 6 = 15$.

- Test Case $2$: For the given arrays, the value is: $\max(0\oplus 0,0\& 0) = 0$.

- Test Case $3$: For the given arrays, the value is: $\max(2\oplus 1,2\& 1) + \max(2\oplus 2,2\& 2) + \max(2\oplus 1,2\& 1) + \max(4\oplus 1,4\& 1) + \max(4\oplus 2,4\& 2) + \max(4\oplus 1,4\& 1) + \max(3\oplus 1,3\& 1) + \max(3\oplus 2,3\& 2) + \max(3\oplus 1,3\& 1)$  
$= 3 + 2 + 3 + 5 + 6 + 5 + 2 + 2 + 2 = 30$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
~~~if:csharp,javascript,cfml,php
Given a 2D array of size `m * n`. Your task is to find the sum of minimum value in each row.
~~~
~~~if:cpp
Given a 2D vector of size `m * n`. Your task is to find the sum of minimum value in each row.
~~~
~~~if:python,ruby
Given a 2D list of size `m * n`. Your task is to find the sum of minimum value in each row.
~~~

For Example:
```python
[
  [1, 2, 3, 4, 5],       # minimum value of row is 1
  [5, 6, 7, 8, 9],       # minimum value of row is 5
  [20, 21, 34, 56, 100]  # minimum value of row is 20
]
```
So, the function should return `26` because sum of minimums is as `1 + 5 + 20 = 26`

~~~if:javascript,php
Note: You will be always given non-empty array containing Positive values.
~~~
~~~if:python
Note: You will be always given non-empty list containing Positive values.
~~~
~~~if:cpp
Note: You will be always given non-empty vector containing Positive values.
~~~
~~~if:c#
Note: You will be always given non-empty vector containing Positive values.
~~~
~~~if:cfml
Note: You will be always given non-empty array containing Positive values.
~~~

ENJOY CODING :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Frane is already in tenth grade, but is still struggling with Pascal in computer class. For homework, his teacher wrote the following program into his notebook, and he needs to determine the output, given the integer $N$.

readln(N);
counter := 0;
for i := N - 1 downto 1 do begin
  counter := counter + 1;
  if N mod i = 0 then break;
end;
writeln(counter);

Write a program which solves Frane’s problem.

-----Input-----
The first and only line of input contains the integer $1 \le N \le 10^9$.

-----Output-----
Output the result from Frane’s program on a single line.

-----Examples-----
Sample Input 1:
1
Sample Output 1:
0

Sample Input 2:
10
Sample Output 2:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera's finally decided to go on holiday! He packed up and headed for a ski resort.

Valera's fancied a ski trip but he soon realized that he could get lost in this new place. Somebody gave him a useful hint: the resort has n objects (we will consider the objects indexed in some way by integers from 1 to n), each object is either a hotel or a mountain.

Valera has also found out that the ski resort had multiple ski tracks. Specifically, for each object v, the resort has at most one object u, such that there is a ski track built from object u to object v. We also know that no hotel has got a ski track leading from the hotel to some object.

Valera is afraid of getting lost on the resort. So he wants you to come up with a path he would walk along. The path must consist of objects v_1, v_2, ..., v_{k} (k ≥ 1) and meet the following conditions:  Objects with numbers v_1, v_2, ..., v_{k} - 1 are mountains and the object with number v_{k} is the hotel.  For any integer i (1 ≤ i < k), there is exactly one ski track leading from object v_{i}. This track goes to object v_{i} + 1.  The path contains as many objects as possible (k is maximal). 

Help Valera. Find such path that meets all the criteria of our hero!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of objects.

The second line contains n space-separated integers type_1, type_2, ..., type_{n} — the types of the objects. If type_{i} equals zero, then the i-th object is the mountain. If type_{i} equals one, then the i-th object is the hotel. It is guaranteed that at least one object is a hotel.

The third line of the input contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n) — the description of the ski tracks. If number a_{i} equals zero, then there is no such object v, that has a ski track built from v to i. If number a_{i} doesn't equal zero, that means that there is a track built from object a_{i} to object i.


-----Output-----

In the first line print k — the maximum possible path length for Valera. In the second line print k integers v_1, v_2, ..., v_{k} — the path. If there are multiple solutions, you can print any of them.


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

Output
5
1 2 3 4 5

Input
5
0 0 1 0 1
0 1 2 2 4

Output
2
4 5

Input
4
1 0 0 0
2 3 4 2

Output
1
1

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