vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given two arrays A and B of equal size N, the task is to find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though.
Note : If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
Example 1:
Input:
N = 5
A[] = {1,2,5,4,0}
B[] = {2,4,5,0,1}
Output: 1
Explanation: Both the array can be 
rearranged to {0,1,2,4,5}
Example 2:
Input:
N = 3
A[] = {1,2,5}
B[] = {2,4,15}
Output: 0
Explanation: A[] and B[] have only 
one common value.
Your Task:
Complete check() function which takes both the given array and their size as function arguments and returns true if the arrays are equal else returns false.The 0 and 1 printing is done by the driver code.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1<=N<=10^{7}
1<=A[],B[]<=10^{18}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given sequence of distinct non-negative integers $(b_1, b_2, \dots, b_k)$ we determine if it is good in the following way:

Consider a graph on $k$ nodes, with numbers from $b_1$ to $b_k$ written on them.

For every $i$ from $1$ to $k$: find such $j$ ($1 \le j \le k$, $j\neq i$), for which $(b_i \oplus b_j)$ is the smallest among all such $j$, where $\oplus$ denotes the operation of bitwise XOR ( https://en.wikipedia.org/wiki/Bitwise_operation#XOR ). Next, draw an undirected edge between vertices with numbers $b_i$ and $b_j$ in this graph.

We say that the sequence is good if and only if the resulting graph forms a tree (is connected and doesn't have any simple cycles).

It is possible that for some numbers $b_i$ and $b_j$, you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

You can find an example below (the picture corresponding to the first test case).

Sequence $(0, 1, 5, 2, 6)$ is not good as we cannot reach $1$ from $5$.

However, sequence $(0, 1, 5, 2)$ is good.

You are given a sequence $(a_1, a_2, \dots, a_n)$ of distinct non-negative integers. You would like to remove some of the elements (possibly none) to make the remaining sequence good. What is the minimum possible number of removals required to achieve this goal?

It can be shown that for any sequence, we can remove some number of elements, leaving at least $2$, so that the remaining sequence is good.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 200,000$) — length of the sequence.

The second line contains $n$ distinct non-negative integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the sequence.


-----Output-----

You should output exactly one integer — the minimum possible number of elements to remove in order to make the remaining sequence good.


-----Examples-----

Input
5
0 1 5 2 6
Output
1
Input
7
6 9 8 7 3 5 2
Output
2


-----Note-----

Note that numbers which you remove don't impact the procedure of telling whether the resulting sequence is good.

It is possible that for some numbers $b_i$ and $b_j$, you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's define a string <x> as an opening tag, where x is any small letter of the Latin alphabet. Each opening tag matches a closing tag of the type </x>, where x is the same letter.

Tegs can be nested into each other: in this case one opening and closing tag pair is located inside another pair.

Let's define the notion of a XML-text: 

  * an empty string is a XML-text
  * if s is a XML-text, then s'=<a>+s+</a> also is a XML-text, where a is any small Latin letter 
  * if s1, s2 are XML-texts, then s1+s2 also is a XML-text



You are given a XML-text (it is guaranteed that the text is valid), your task is to print in the following form: 

  * each tag (opening and closing) is located on a single line 
  * print before the tag 2 * h spaces, where h is the level of the tag's nestedness. 

Input

The input data consists on the only non-empty string — the XML-text, its length does not exceed 1000 characters. It is guaranteed that the text is valid. The text contains no spaces.

Output

Print the given XML-text according to the above-given rules.

Examples

Input

&lt;a&gt;&lt;b&gt;&lt;c&gt;&lt;/c&gt;&lt;/b&gt;&lt;/a&gt;


Output

&lt;a&gt;
  &lt;b&gt;
    &lt;c&gt;
    &lt;/c&gt;
  &lt;/b&gt;
&lt;/a&gt;


Input

&lt;a&gt;&lt;b&gt;&lt;/b&gt;&lt;d&gt;&lt;c&gt;&lt;/c&gt;&lt;/d&gt;&lt;/a&gt;


Output

&lt;a&gt;
  &lt;b&gt;
  &lt;/b&gt;
  &lt;d&gt;
    &lt;c&gt;
    &lt;/c&gt;
  &lt;/d&gt;
&lt;/a&gt;

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every day, Danny buys one sweet from the candy store and eats it. The store has $m$ types of sweets, numbered from $1$ to $m$. Danny knows that a balanced diet is important and is applying this concept to his sweet purchasing. To each sweet type $i$, he has assigned a target fraction, which is a real number $f_ i$ ($0 < f_ i \le 1$). He wants the fraction of sweets of type $i$ among all sweets he has eaten to be roughly equal to $f_ i$. To be more precise, let $s_ i$ denote the number of sweets of type $i$ that Danny has eaten, and let $n = \sum _{i=1}^m s_ i$. We say the set of sweets is balanced if for every $i$ we have\[ n f_ i - 1 < s_ i < n f_ i + 1. \]

Danny has been buying and eating sweets for a while and during this entire time the set of sweets has been balanced. He is now wondering how many more sweets he can buy while still fulfilling this condition. Given the target fractions $f_ i$ and the sequence of sweets he has eaten so far, determine how many more sweets he can buy and eat so that at any time the set of sweets is balanced.

-----Input-----
The input consists of three lines. The first line contains two integers $m$ ($1 \le m \le 10^5$), which is the number of types of sweets, and $k$ ($0 \le k \le 10^5$), which is the number of sweets Danny has already eaten.

The second line contains $m$ positive integers $a_1, \ldots , a_ m$. These numbers are proportional to $f_1, \ldots , f_ m$, that is, $\displaystyle f_ i = \frac{a_ i}{\sum _{j = 1}^m a_ j}$. It is guaranteed that the sum of all $a_ j$ is no larger than $10^5$.

The third line contains $k$ integers $b_1, \ldots , b_ k$ ($1 \le b_ i \le m$), where each $b_ i$ denotes the type of sweet Danny bought and ate on the $i^\text {th}$ day. It is guaranteed that every prefix of this sequence (including the whole sequence) is balanced.

-----Output-----
Display the maximum number of additional sweets that Danny can buy and eat while keeping his diet continuously balanced. If there is no upper limit on the number of sweets, display the word forever.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A mouse encountered a nice big cake and decided to take a walk across it, eating the berries on top of the cake on its way. The cake is rectangular, neatly divided into squares; some of the squares have a berry in them, and some don't.

The mouse is in a bit of a hurry, though, so once she enters the cake from its northwest corner (the top left cell in the input data), she will only go east (right) or south (down), until she reaches the southeast corner (the bottom right cell). She will eat every berry in the squares she passes through, but not in the other squares.

The mouse tries to choose her path so as to maximize the number of berries consumed. However, her haste and hunger might be clouding her judgement, leading her to suboptimal decisions...

Input

The first line of input contains two integers H and W (1 ≤ H, W ≤ 5), separated by a space, — the height and the width of the cake.

The next H lines contain a string of W characters each, representing the squares of the cake in that row: '.' represents an empty square, and '*' represents a square with a berry.

Output

Output the number of berries the mouse will eat following her strategy.

Examples

Input


4 3
*..
.*.
..*
...


Output


3


Input


4 4
.*..
*...
...*
..*.


Output


2


Input


3 4
..**
*...
....


Output


1


Input


5 5
..*..
.....
**...
**...
**...


Output


1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given string s consists of opening and closing brackets of four kinds <>, {}, [], (). There are two types of brackets: opening and closing. You can replace any bracket by another of the same type. For example, you can replace < by the bracket {, but you can't replace it by ) or >.

The following definition of a regular bracket sequence is well-known, so you can be familiar with it.

Let's define a regular bracket sequence (RBS). Empty string is RBS. Let s_1 and s_2 be a RBS then the strings <s_1>s_2, {s_1}s_2, [s_1]s_2, (s_1)s_2 are also RBS.

For example the string "[[(){}]<>]" is RBS, but the strings "[)()" and "][()()" are not.

Determine the least number of replaces to make the string s RBS.


-----Input-----

The only line contains a non empty string s, consisting of only opening and closing brackets of four kinds. The length of s does not exceed 10^6.


-----Output-----

If it's impossible to get RBS from s print Impossible.

Otherwise print the least number of replaces needed to get RBS from s.


-----Examples-----
Input
[<}){}

Output
2
Input
{()}[]

Output
0
Input
]]

Output
Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A TV show called "Guess a number!" is gathering popularity. The whole Berland, the old and the young, are watching the show.

The rules are simple. The host thinks of an integer y and the participants guess it by asking questions to the host. There are four types of acceptable questions:  Is it true that y is strictly larger than number x?  Is it true that y is strictly smaller than number x?  Is it true that y is larger than or equal to number x?  Is it true that y is smaller than or equal to number x? 

On each question the host answers truthfully, "yes" or "no".

Given the sequence of questions and answers, find any integer value of y that meets the criteria of all answers. If there isn't such value, print "Impossible".


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 10000) — the number of questions (and answers). Next n lines each contain one question and one answer to it. The format of each line is like that: "sign x answer", where the sign is:  ">" (for the first type queries),  "<" (for the second type queries),  ">=" (for the third type queries),  "<=" (for the fourth type queries). 

All values of x are integer and meet the inequation  - 10^9 ≤ x ≤ 10^9. The answer is an English letter "Y" (for "yes") or "N" (for "no").

Consequtive elements in lines are separated by a single space.


-----Output-----

Print any of such integers y, that the answers to all the queries are correct. The printed number y must meet the inequation  - 2·10^9 ≤ y ≤ 2·10^9. If there are many answers, print any of them. If such value doesn't exist, print word "Impossible" (without the quotes).


-----Examples-----
Input
4
>= 1 Y
< 3 N
<= -3 N
> 55 N

Output
17

Input
2
> 100 Y
< -100 Y

Output
Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has come to a 2 dimensional garden in which there are N points. Each point has coordinates (x, y), where x can either be 1 or 2 or 3. Chef will now choose every triplet of these N points and make a triangle from it. You need to tell the sum of areas of all the triangles the Chef makes.
Note that some of the triplets might not form proper triangles, and would end up as a line or a point (ie. degenerate), but that is fine because their area will be zero.

-----Input-----
- The first line contains a single integer T, the number of test cases. The description of each testcase follows.
- The first line of each test case contains an integer N denoting the number of points on the plane.
- The next N lines contain 2 space separated integers x and y denoting the coordinates of the points. 

-----Output-----
For each test case, output a single line containing the answer. Your answer will be considered correct if the absolute error is less than or equal to 10-2.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 2000
- 1 ≤ x ≤ 3
- 1 ≤ y ≤106
- All (x, y) pairs are distinct

-----Example-----
Input:
2
3
1 1
2 1
3 3
4
1 1
2 2
2 1
3 3

Output:
1.0
2.0

-----Explanation:-----
Test Case 1: There is only one triangle which has non-zero area, and it's area is 1, hence the output.
Test Case 2: Let the points be A(1,1), B(2,2), C(2,1), D(3,3). There are 3 non degenerate triangles possible. 

-  area ABC = 0.5
-  area BCD = 0.5
-  area ACD = 1
Total area = 2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly *k* time units for the lunch break.

The Rabbits have a list of *n* restaurants to lunch in: the *i*-th restaurant is characterized by two integers *f**i* and *t**i*. Value *t**i* shows the time the Rabbits need to lunch in the *i*-th restaurant. If time *t**i* exceeds the time *k* that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal *f**i*<=-<=(*t**i*<=-<=*k*). Otherwise, the Rabbits get exactly *f**i* units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value.

Input Specification:
The first line contains two space-separated integers — *n* (1<=≤<=*n*<=≤<=104) and *k* (1<=≤<=*k*<=≤<=109) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next *n* lines contains two space-separated integers — *f**i* (1<=≤<=*f**i*<=≤<=109) and *t**i* (1<=≤<=*t**i*<=≤<=109) — the characteristics of the *i*-th restaurant.

Output Specification:
In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch.

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

Demo Output:
['4\n', '3\n', '-1\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel has a board with *n* rows and *n* columns. So, the board consists of *n*<=×<=*n* cells. Each cell contains either a symbol '.', or a symbol '#'.

A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.

Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols '#', and any cell with symbol '#' must belong to some cross. No two crosses can share a cell.

Please, tell Ciel if she can draw the crosses in the described way.

Input Specification:
The first line contains an integer *n* (3<=≤<=*n*<=≤<=100) — the size of the board.

Each of the next *n* lines describes one row of the board. The *i*-th line describes the *i*-th row of the board and consists of *n* characters. Each character is either a symbol '.', or a symbol '#'.

Output Specification:
Output a single line with "YES" if Ciel can draw the crosses in the described way. Otherwise output a single line with "NO".

Demo Input:
['5\n.#...\n####.\n.####\n...#.\n.....\n', '4\n####\n####\n####\n####\n', '6\n.#....\n####..\n.####.\n.#.##.\n######\n.#..#.\n', '6\n.#..#.\n######\n.####.\n.####.\n######\n.#..#.\n', '3\n...\n...\n...\n']

Demo Output:
['YES\n', 'NO\n', 'YES\n', 'NO\n', 'YES\n']

Note:
In example 1, you can draw two crosses. The picture below shows what they look like.

In example 2, the board contains 16 cells with '#', but each cross contains 5. Since 16 is not a multiple of 5, so it's impossible to cover all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja is hosting his birthday dinner. He invited his N close friends. Let us number the people from 1 to N according to the order in which they arrive at the event. The dinner is being held in long straight corridor in which people sit in a way such that they won't leave any empty space in between two consecutive persons at any given time. 

When a person number i arrives at the corridor, he must go and stand to the immediate right of the person numbered A[i] (if A[i] = 0, then this person just stands at the leftmost end of the line). 

But there is a problem, as there is no space between two consecutive persons at any given time, so for this person to sit, space must be created by moving either all the persons to left of the place to the left one step each, or all the persons to right of the place to the right one step each.  

Now, Sereja is wondering about what could be the minimum number of steps people will take so as to sit in the dinner party. Please find it fast, so that Sereja can peacefully entertain his guests.

-----Input-----
First line of input contain an integer T — the number of test cases. T tests follow.
First line of each test case contain the integer N, and the next line contains N integers — A[1], A[2], ... , A[N].

-----Output-----
For each test case, output a single line with the answer — the minimal number of steps required.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100
- 0 ≤ A[i] < i

-----Example-----
Input:
3
1
0
3
0 0 0
5
0 1 2 1 4

Output:
0
0
3

-----Explanation-----
Example case 3.
- First three persons don't need any steps to sit. The line after the arrangement of these persons will look like [1, 2, 3].  

- When person #4 comes in, he wants to sit to the right of person 1, so we need to either move the first person to the left, or the second and third persons to the right. The first case is clearly better. Now the line will look like [1, 4, 2, 3].  

- When person #5 arrives, he will need to move 2 persons in either case. The final arrangement will be [1, 4, 5, 2, 3]. 

So total number of steps people moved during the entire process is 1 + 2 = 3. So the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's been long after the events of the previous problems, and Karen has now moved on from student life and is looking to relocate to a new neighborhood.

<image>

The neighborhood consists of n houses in a straight line, labelled 1 to n from left to right, all an equal distance apart.

Everyone in this neighborhood loves peace and quiet. Because of this, whenever a new person moves into the neighborhood, he or she always chooses the house whose minimum distance to any occupied house is maximized. If there are multiple houses with the maximum possible minimum distance, he or she chooses the leftmost one.

Note that the first person to arrive always moves into house 1.

Karen is the k-th person to enter this neighborhood. If everyone, including herself, follows this rule, which house will she move into?

Input

The first and only line of input contains two integers, n and k (1 ≤ k ≤ n ≤ 1018), describing the number of houses in the neighborhood, and that Karen was the k-th person to move in, respectively.

Output

Output a single integer on a line by itself, the label of the house Karen will move into.

Examples

Input

6 4


Output

2


Input

39 3


Output

20

Note

In the first test case, there are 6 houses in the neighborhood, and Karen is the fourth person to move in:

  1. The first person moves into house 1. 
  2. The second person moves into house 6. 
  3. The third person moves into house 3. 
  4. The fourth person moves into house 2. 



In the second test case, there are 39 houses in the neighborhood, and Karen is the third person to move in:

  1. The first person moves into house 1. 
  2. The second person moves into house 39. 
  3. The third person moves into house 20. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For the purposes of this problem, we will assume that every page in an book is numbered sequentially, and that the first page is numbered 1. 
How many digits would you need to use to number the pages of a 10 page book? Pages 1 to 9 would require 1 digit each (total 9), and page 10 would require 2 digits. This makes 11 digits. Similarly, a book of 34 pages would require 59 digits. 
Can we work backwards? If you are told that a book requires 13 digits to number its pages, can you work out how many pages the book has? I hope so, because that is all you have to do for this problem. Each line in the input file represents the number of digits used in numbering a book. Your answer will be the number of pages the book has. If the number supplied cannot possibly be valid, your answer should be "Impossible!" Beware that books can be quite large, and the number of digits required for a given book can reach 2,000,000,000.



Input
Each line in the input file contains a single integer, between 1 and 2,000,000,000, representing a number of digits used in numbering the pages of a book. A single # on a line indicates the end of input. 


Output
Output for each input number must be on a single line. If the input value is valid, output the number of pages in the book. Otherwise, output "Impossible!" 


Example

Input:
11 
13 
59 
60 
1999999998 
# 


Output:
10 
11 
34 
Impossible! 
234567900

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the sequence: 0123456789101112131415...
The 0th digit of this sequence is 0, the 1st digit of this sequence is 1, the 2nd digit of this sequence is 2 and so on. You are given n, find the nth digit of the sequence.
 
Example 1:
Input: n = 12
Output: 1
Explanation: 1 is the 12th digit of the
given sequence.
Example 2:
Input: n = 20
Output: 4
Explanation: 4 is the 20th digit of the
given sequence.
 
Your Task:
You don't need to read or write anything. Your task is to complete the function NthDigit() which takes n as input parameter and returns the nth digit of the sequence.
 
Expected Time Complexity: O(log_{10}(n))
Expected Space Compelxity: O(1)
 
Constraints:
1 <= n <= 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you probably know, Fibonacci sequence are the numbers in the following integer sequence:
1, 1, 2, 3, 5, 8, 13...
Write a method that takes the index as an argument and returns last digit from fibonacci number. Example:
  getLastDigit(15) - 610. Your method must return 0 because the last digit of 610 is 0.
Fibonacci sequence grows very fast and value can take very big numbers (bigger than integer type can contain), so, please, be careful with overflow.

[Hardcore version of this kata](http://www.codewars.com/kata/find-last-fibonacci-digit-hardcore-version), no bruteforce will work here ;)

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