vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n points on a straight line, and the i-th point among them is located at x_{i}. All these coordinates are distinct.

Determine the number m — the smallest number of points you should add on the line to make the distances between all neighboring points equal. 


-----Input-----

The first line contains a single integer n (3 ≤ n ≤ 100 000) — the number of points.

The second line contains a sequence of integers x_1, x_2, ..., x_{n} ( - 10^9 ≤ x_{i} ≤ 10^9) — the coordinates of the points. All these coordinates are distinct. The points can be given in an arbitrary order.


-----Output-----

Print a single integer m — the smallest number of points you should add on the line to make the distances between all neighboring points equal. 


-----Examples-----
Input
3
-5 10 5

Output
1

Input
6
100 200 400 300 600 500

Output
0

Input
4
10 9 0 -1

Output
8



-----Note-----

In the first example you can add one point with coordinate 0.

In the second example the distances between all neighboring points are already equal, so you shouldn't add anything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S consisting of only lowercase characters. Find the lexicographically smallest string after removing exactly k characters from the string. But you have to correct the value of k, i.e., if the length of the string is a power of 2, reduce k by half, else multiply k by 2. You can remove any k character.
NOTE: If it is not possible to remove k (the value of k after correction) characters or if the resulting string is empty return -1. 
Example 1:
Input: S = "fooland", k = 2
Output: "and" 
Explanation: As the size of the string = 7
which is not a power of 2, hence k = 4.
After removing 4 characters from the given 
string, the lexicographically smallest
string is "and".
Example 2:
Input: S = "code", k = 4
Output: "cd"
Explanation: As the length of the string = 4, 
which is 2 to the power 2, hence k = 2.
Hence, lexicographically smallest string after 
removal of 2 characters is "cd".
Your Task:  
You dont need to read input or print anything. Complete the function lexicographicallySmallest() which takes S and k as input parameters and returns the lexicographically smallest string after removing k characters.
Expected Time Complexity: O(n+k), n is size of the string
Expected Auxiliary Space: O(n)
Constraints:
1<= |S| <=10^{5}
1<= k <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
###Story
Sometimes we are faced with problems when we have a big nested dictionary with which it's hard to work. Now, we need to solve this problem by writing a function that will flatten a given dictionary.

###Info
Python dictionaries are a convenient data type to store and process configurations. They allow you to store data by keys to create nested structures. You are given a dictionary where the keys are strings and the values are strings or dictionaries. The goal is flatten the dictionary, but save the structures in the keys. The result should be a dictionary without the nested dictionaries. The keys should contain paths that contain the parent keys from the original dictionary. The keys in the path are separated by a `/`. If a value is an empty dictionary, then it should be replaced by an empty string `""`.

###Examples
```python
{
    "name": {
        "first": "One",
        "last": "Drone"
    },
    "job": "scout",
    "recent": {},
    "additional": {
        "place": {
            "zone": "1",
            "cell": "2"
        }
    }
}
```
The result will be:
```python
{"name/first": "One",           #one parent
 "name/last": "Drone",
 "job": "scout",                #root key
 "recent": "",                  #empty dict
 "additional/place/zone": "1",  #third level
 "additional/place/cell": "2"}
```

***`Input: An original dictionary as a dict.`***
***`Output: The flattened dictionary as a dict.`***
***`Precondition:
Keys in a dictionary are non-empty strings.
Values in a dictionary are strings or dicts.
root_dictionary != {}`***

```python
flatten({"key": "value"}) == {"key": "value"}
flatten({"key": {"deeper": {"more": {"enough": "value"}}}}) == {"key/deeper/more/enough": "value"}
flatten({"empty": {}}) == {"empty": ""}
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A famous Berland's painter Kalevitch likes to shock the public. One of his last obsessions is chess. For more than a thousand years people have been playing this old game on uninteresting, monotonous boards. Kalevitch decided to put an end to this tradition and to introduce a new attitude to chessboards.

As before, the chessboard is a square-checkered board with the squares arranged in a 8 × 8 grid, each square is painted black or white. Kalevitch suggests that chessboards should be painted in the following manner: there should be chosen a horizontal or a vertical line of 8 squares (i.e. a row or a column), and painted black. Initially the whole chessboard is white, and it can be painted in the above described way one or more times. It is allowed to paint a square many times, but after the first time it does not change its colour any more and remains black. Kalevitch paints chessboards neatly, and it is impossible to judge by an individual square if it was painted with a vertical or a horizontal stroke.

Kalevitch hopes that such chessboards will gain popularity, and he will be commissioned to paint chessboards, which will help him ensure a comfortable old age. The clients will inform him what chessboard they want to have, and the painter will paint a white chessboard meeting the client's requirements.

It goes without saying that in such business one should economize on everything — for each commission he wants to know the minimum amount of strokes that he has to paint to fulfill the client's needs. You are asked to help Kalevitch with this task.

Input

The input file contains 8 lines, each of the lines contains 8 characters. The given matrix describes the client's requirements, W character stands for a white square, and B character — for a square painted black.

It is guaranteed that client's requirments can be fulfilled with a sequence of allowed strokes (vertical/column or horizontal/row).

Output

Output the only number — the minimum amount of rows and columns that Kalevitch has to paint on the white chessboard to meet the client's requirements.

Examples

Input

WWWBWWBW
BBBBBBBB
WWWBWWBW
WWWBWWBW
WWWBWWBW
WWWBWWBW
WWWBWWBW
WWWBWWBW


Output

3


Input

WWWWWWWW
BBBBBBBB
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An English text needs to be encrypted using the following encryption scheme. 

First, the spaces are removed from the text. Let $L$ be the length of this text. 

Then, characters are written into a grid, whose rows and columns have the following constraints:

$\lfloor\sqrt{L}\rfloor\leq row\leq column\leq\lceil\sqrt{L}\rceil,\text{where}\lfloor x\rfloor\text{is floor function and}\lceil x\rceil\text{is cell function}$ 

Example  

$s=\textbf{if man was meant to stay on the ground good would have given us roots}$  

After removing spaces, the string is $54$ characters long.  $\sqrt{54}$ is between $7$ and $8$, so it is written in the form of a grid with 7 rows and 8 columns. 

ifmanwas  
meanttos          
tayonthe  
groundgo  
dwouldha  
vegivenu  
sroots

Ensure that $rows\times columns\geq L$   
If multiple grids satisfy the above conditions, choose the one with the minimum area, i.e. $rows\times columns$.  

The encoded message is obtained by displaying the characters of each column, with a space between column texts. The encoded message for the grid above is:  

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau  

Create a function to encode a message.

Function Description  

Complete the encryption function in the editor below.  

encryption has the following parameter(s):  

string s: a string to encrypt  

Returns  

string: the encrypted string  

Input Format

One line of text, the string $\boldsymbol{\mathrm{~S~}}$

Constraints

$1\leq\ \text{length of}\ s\leq81$ 

$\boldsymbol{\mathrm{~S~}}$ contains characters in the range ascii[a-z] and space, ascii(32).

Sample Input
haveaniceday

Sample Output 0

hae and via ecy

Explanation 0  

$L=12$, $\sqrt{12}$ is between $3$ and $4$. 

Rewritten with $3$ rows and $4$ columns:

have
anic
eday

Sample Input 1

feedthedog    

Sample Output 1

fto ehg ee dd

Explanation 1  

$L=\textbf{10}$, $\sqrt{10}$ is between $3$ and $4$. 

Rewritten with $3$ rows and $4$ columns:  

feed
thed
og

Sample Input 2

chillout

Sample Output 2

clu hlt io

Explanation 2  

$L=8$, $\sqrt{8}$ is between $2$ and $3$. 

Rewritten with $3$ columns and $3$ rows ($2*3=6<8$ so we have to use $3X3$.)

chi
llo
ut

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The city of Kyoto is well-known for its Chinese plan: streets are either North-South or East-West. Some streets are numbered, but most of them have real names.
Crossings are named after the two streets crossing there, e.g. Kawaramachi-Sanjo is the crossing of Kawaramachi street and Sanjo street. But there is a problem: which name should come first? At first the order seems quite arbitrary: one says Kawaramachi-Sanjo (North-South first) but Shijo-Kawaramachi (East-West first). With some experience, one realizes that actually there seems to be an "order" on the streets, for instance in the above Shijo is "stronger" than Kawaramachi, which in turn is "stronger" than Sanjo. One can use this order to deduce the names of other crossings.

You are given as input a list of known crossing names X-Y. Streets are either North-South or East-West, and only orthogonal streets may cross.

As your list is very incomplete, you start by completing it using the following rule:

* two streets A and B have equal strength if (1) to (3) are all true:
1. they both cross the same third street C in the input
2. there is no street D such that D-A and B-D appear in the input
3. there is no street E such that A-E and E-B appear in the input



We use this definition to extend our strength relation:

* A is stronger than B, when there is a sequence A = A1, A2, ..., An = B, with n at least 2,
where, for any i in 1 .. n-1, either Ai-Ai+1 is an input crossing or Ai and Ai+1 have equal strength.



Then you are asked whether some other possible crossing names X-Y are valid. You should answer affirmatively if you can infer the validity of a name, negatively if you cannot. Concretely:

* YES if you can infer that the two streets are orthogonal, and X is stronger than Y
* NO otherwise



Input

The input is a sequence of data sets, each of the form

>
>     N
>     Crossing1
>     ...
>     CrossingN
>     M
>     Question1
>     ...
>     QuestionM
>

Both Crossings and Questions are of the form

> X-Y

where X and Y are strings of alphanumerical characters, of lengths no more than 16. There is no white space, and case matters for alphabetical characters.
N and M are between 1 and 1000 inclusive, and there are no more than 200 streets in a data set.

The last data set is followed by a line containing a zero.

Output

The output for each data set should be composed of M+1 lines, the first one containing the number of streets in the Crossing part of the input, followed by the answers to each question, either YES or NO without any spaces.

Example

Input

7
Shijo-Kawaramachi
Karasuma-Imadegawa
Kawaramachi-Imadegawa
Nishioji-Shijo
Karasuma-Gojo
Torimaru-Rokujo
Rokujo-Karasuma
6
Shijo-Karasuma
Imadegawa-Nishioji
Nishioji-Gojo
Shijo-Torimaru
Torimaru-Gojo
Shijo-Kawabata
4
1jo-Midosuji
Midosuji-2jo
2jo-Omotesando
Omotesando-1jo
4
Midosuji-1jo
1jo-Midosuji
Midosuji-Omotesando
1jo-1jo
0


Output

8
YES
NO
YES
NO
YES
NO
4
YES
YES
NO
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Klein is trying to get her dog Jack into the Frisbee Dog Tournament. But she's not sure if Jack will get a good grade. For her, she simulates the tournament to get Jack's grade. I want you to create a program to estimate.

The tournament is held by N dogs on a two-dimensional plane. At the start of the tournament, the i-th dog is in the (Dix, Diy) position. The i-th dog is Vi [m / s] All dogs are small enough to be considered points. At any given time, two or more dogs may be in the same position.

The tournament begins with the launch of the first Frisbee, from which the dogs are allowed to move. Frisbee can also be considered a point, the i Frisbee from the (FPix, FPiy) position ( FVix, FViy) Fired at a velocity vector of [m / s] and continues a constant velocity linear motion. When a dog's position and a Frisbee's position are equal, the dog can get a Frisbee.

The moment the first Frisbee is acquired by one of the dogs, the second Frisbee is fired. The moment the second Frisbee is acquired, the third is fired, and so on. Immediately after, the next Frisbee will be fired. The tournament will end when the Mth Frisbee is acquired.

Needless to say, the dogs' goal is to get more Frisbee. Dogs take the following strategies.

When the Frisbee is fired, the dog moves to get it at the earliest possible time and gets the Frisbee. However, if it cannot get the Frisbee, it waits where it is.

The determination of whether a dog can get a frisbee is made regardless of the behavior of the other dog. That is, one dog moves to get a frisbee, but the other dog gets it first. The moment one of the dogs gets the Frisbee and a new Frisbee is launched, the dogs take the above strategy against the new Frisbee.

The program you create must output the number of Frisbees obtained by each dog.



Input

The input file consists of multiple datasets.

The first row of the dataset gives the number of dogs N (1 ≤ N ≤ 10) and the number of Frisbees M (1 ≤ M ≤ 1000).

The following N lines are given the dog's initial position and velocity Dix, Diy, Vi, separated by a single blank.

The following M lines are given the Frisbee launch position and velocity FPix, FPiy, FVix, FViy, separated by a single space character.

The coordinate values ​​given are real numbers and their absolute values ​​do not exceed 1000. The speeds given are real numbers 1 ≤ DVi ≤ 100, -25 ≤ FVix, FViy ≤ 25. Frisbees that cannot be obtained by any dog You can assume that there is no.

When a dog with any Frisbee was obtained at time t, no dog could get it before time t + 1e-6.

During the simulation, the absolute values ​​of the dog's x and y coordinates do not exceed 1e + 8.

When both N and M are 0, the end of input is indicated.

Output

Output the number of Frisbees obtained by each dog on one line separated by a space character. The order of output must be the same as the order given in the input.

Example

Input

2 1
12 5 3
0 17 3
0 0 2 2
2 3
2 0 2
100 100 2
0 0 -1 0
-2 -5 0 3
100 100 1 1
0 0


Output

1 0
2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have initially a string of N characters, denoted by A1,A2...AN. You have to print the size of the largest subsequence of string A such that all the characters in that subsequence are distinct ie. no two characters in that subsequence should be same.

A subsequence of string A is a sequence that can be derived from A by deleting some elements  and without changing the order of the remaining elements.

-----Input-----
First line contains T, number of testcases. Each testcase consists of a single string in one line. Each character of the string will be a small alphabet(ie. 'a' to 'z').

-----Output-----
For each testcase, print the required answer in one line.

-----Constraints-----
- 1 ≤ T ≤ 10
- Subtask 1 (20 points):1 ≤ N ≤ 10
- Subtask 2 (80 points):1 ≤ N ≤ 105

-----Example-----
Input:
2
abc
aba

Output:
3
2

-----Explanation-----
For first testcase, the whole string is a subsequence which has all distinct characters.

In second testcase, the we can delete last or first 'a' to get the required subsequence.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array *a*. Some element of this array *a**i* is a local minimum iff it is strictly less than both of its neighbours (that is, *a**i*<=&lt;<=*a**i*<=-<=1 and *a**i*<=&lt;<=*a**i*<=+<=1). Also the element can be called local maximum iff it is strictly greater than its neighbours (that is, *a**i*<=&gt;<=*a**i*<=-<=1 and *a**i*<=&gt;<=*a**i*<=+<=1). Since *a*1 and *a**n* have only one neighbour each, they are neither local minima nor local maxima.

An element is called a local extremum iff it is either local maximum or local minimum. Your task is to calculate the number of local extrema in the given array.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=1000) — the number of elements in array *a*.

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=1000) — the elements of array *a*.

Output Specification:
Print the number of local extrema in the given array.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let a and b be binary numbers of length n (MSB to the left). The following commands may be performed:

set_a idx x: Set $a[i dx]$ to $\boldsymbol{x}$, where $0\leq idx<n$ and  $a[i dx]$ is $\text{id}x^{\text{th}}$ least significant bit of $a$.  
set_b idx x: Set $b[idx]$ to $\boldsymbol{x}$, where $0\leq idx<n$ and  $b[idx]$ is $\text{id}x^{\text{th}}$ least significant bit of $\boldsymbol{b}$.  
get_c idx: Print $c[idx]$, where $c[idx]=a[idx]+b[idx]$ and $0\leq idx\leq n+1$.  

Given $a,b$, and a list of commands, create a string made of the results of each $\text{get_c}$ call, the only command that produces output.  For example, $\boldsymbol{a}=\boldsymbol{000}$ and $b=111$ so the length of the numbers is $n=3$.  Print an answer string that contains the results of all commands on one line.  A series of commands and their results follow:

Starting 

ans = '' (empty string) 

a   b 

000 111 

set_a 1 1 

010 111 

set_b 0 1 

010 111 

get_c 3 

a + b = 1001 

ans = '1' 

010 111 

get_c 4 

a + b = 01001 

ans = '10' 

Note: When the command is get_c 4, $\textbf{C}$  had to be padded to the left with a $0$ to be long enough to return a value.  

Function Description  

Complete the changeBits function in the editor below.  For each get_c command, it should print either a 0 or a 1 without a newline until all commands have been processed. At that point, add a newline.   

changeBits has the following parameters: 

- a, b: two integers represented as binary strings 

- queries[queries[0]-queries[n-1]]: an array of query strings in the format described  

Input Format

The first line of input contains two space-separated integers, $n$ and $\textit{q}$, the length of the binary representations of $a$ and $\boldsymbol{b}$, and the number of commands, respectively. 

The second and third lines each contain a string representation of $a$ and $\boldsymbol{b}$. 

The following $\textit{q}$ lines each contain a command string $\textit{queries}[i]$ as described above.  

Constraints

$1\leq n\leq1000000$ 

$1\leq q\leq5000000$  

Output Format

For each query of the type $\text{get_c}$, output a single digit 0 or 1. Output must be placed on a single line.

Sample Input 0
5 5
00000
11111
set_a 0 1
get_c 5
get_c 1
set_b 2 0
get_c 5

Sample Output 0
100

Explanation 0

set_a 0 1 sets 00000 to 00001
C = A + B = 00001 + 11111 = 100000, so get_c[5] = 1
from the above computation get_c[1] = 0
set_b 2 0 sets 11111 to 11011
C = A + B = 00001 + 11011 = 011100, so get_c[5]  = 0

The output is hence concatenation of 1, 0 and 0  = 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer n. Output its binary notation.

Input

The only line of input data contains an integer n (1 ≤ n ≤ 106).

Output

Output the binary notation of n (without any leading zeros).

Examples

Input

5


Output

101


Input

13


Output

1101

Note

In the first example 5 = 1 * 22 + 0 * 21 + 1 * 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N islands in the sea, enumerated from 1 to N. Each of them is so small that we can consider them as points on a plane. You are given the Cartesian coordinates of all islands. X-axis is directed towards East and Y-axis is directed towards North.
You need to illuminate all the islands. To do this, you can place lighthouses on some of the islands. You can't place more than one lighthouse on any single island. Each lighthouse can light only one of the 4 quadrants: North-Western, North-Eastern, South-Western or South-Eastern. If some island is located on the border of an illuminated quadrant, it is considered to be illuminated as well. Note that this means that a lighthouse always illuminates it's own island as well.
Find the smallest possible number of lighthouses required to illuminate all the islands (say L). Describe their configurations — positions and quadrants illuminated — as well.

-----Input-----
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of islands.
The ith of the following N lines contains two integers Xi and Yi denoting the coordinates of the ith island.

-----Output-----
For each test case, first line of output must contain minimum number of lighthouses required to illuminate all islands, L.
Following L lines must describe configuration of the lighthouses, one configuration per line. Description of a lighthouse configuration consists of the number of the island where the lighthouse is placed, and the direction of the quadrant (NW for North-Western, NE for North-Eastern, SW for South-Western, SE for South-Eastern) illuminated by it, separated by a single space.
If there are many possible placements, output any one of them.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 105
- The sum of N over all test cases doesn't exceed 5*105
- Absolute value of each coordinate doesn't exceed 109
- No two given islands coincide.

-----Subtasks-----
Subtask 1: (15 points)
- 1 ≤ N ≤ 8
- Absolute value of each coordinate doesn't exceed 50

Subtask 2: (85 points)
- Original constraints

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

Output:
1
3 SW
2
4 NE
2 NE

-----Explanation-----
Example case 1. Also we can place lighthouse on 1st or 5th island.
Example case 2. Notice that some islands can be illuminated by more than 1 lighthouse.

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