vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a number N. The task is to generate and print all binary numbers with decimal values from 1 to N.
Example 1:
Input:
N = 2
Output: 
1 10
Explanation: 
Binary numbers from
1 to 2 are 1 and 10.
Example 2:
Input:
N = 5
Output: 
1 10 11 100 101
Explanation: 
Binary numbers from
1 to 5 are 1 , 10 , 11 , 100 and 101.
 
Your Task:
You only need to complete the function generate() that takes N as parameter and returns vector of strings denoting binary numbers.
Expected Time Complexity : O(N log_{2}N)
Expected Auxilliary Space : O(N log_{2}N)
Constraints:
1 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Queries about less or equal elements

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given two arrays of integers *a* and *b*. For each element of the second array *b**j* you should find the number of elements in array *a* that are less than or equal to the value *b**j*.

Input Specification:
The first line contains two integers *n*,<=*m* (1<=≤<=*n*,<=*m*<=≤<=2·105) — the sizes of arrays *a* and *b*.

The second line contains *n* integers — the elements of array *a* (<=-<=109<=≤<=*a**i*<=≤<=109).

The third line contains *m* integers — the elements of array *b* (<=-<=109<=≤<=*b**j*<=≤<=109).

Output Specification:
Print *m* integers, separated by spaces: the *j*-th of which is equal to the number of such elements in array *a* that are less than or equal to the value *b**j*.

Demo Input:
['5 4\n1 3 5 7 9\n6 4 2 8\n', '5 5\n1 2 1 2 5\n3 1 4 1 5\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has $n$ hotels, where the $i$-th hotel is located in the city with coordinate $x_i$. Sonya is a smart girl, so she does not open two or more hotels in the same city.

Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to $d$. The girl understands that there are many possible locations to construct such a hotel. Thus she wants to know the number of possible coordinates of the cities where she can build a new hotel. 

Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original $n$ hotels to the new one is equal to $d$.


-----Input-----

The first line contains two integers $n$ and $d$ ($1\leq n\leq 100$, $1\leq d\leq 10^9$) — the number of Sonya's hotels and the needed minimum distance from a new hotel to all others.

The second line contains $n$ different integers in strictly increasing order $x_1, x_2, \ldots, x_n$ ($-10^9\leq x_i\leq 10^9$) — coordinates of Sonya's hotels.


-----Output-----

Print the number of cities where Sonya can build a new hotel so that the minimum distance from this hotel to all others is equal to $d$.


-----Examples-----
Input
4 3
-3 2 9 16

Output
6

Input
5 2
4 8 11 18 19

Output
5



-----Note-----

In the first example, there are $6$ possible cities where Sonya can build a hotel. These cities have coordinates $-6$, $5$, $6$, $12$, $13$, and $19$.

In the second example, there are $5$ possible cities where Sonya can build a hotel. These cities have coordinates $2$, $6$, $13$, $16$, and $21$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil got interested in  palindrome research. For that he needs some research data for a particular string S. To obtain this data he has some queries of following type:
1 L x - update L^th character of string to x 
2 L R - find if all the character of string from index L to R can be rearranged such that they can form a palindrome. If they can print "yes", else print "no". 
Since you decided to help Shil with his research, its your responsibililty to make this data available as soon as possible.  

INPUT: 
First line of input consists of two integers N and Q denoting length of string  S and total number of queries. Next line consists of N lowercase english characters ('a' - 'z') .Next Q lines consists of queries. If the query is 1st type, then it will consists of two integers and a character x and if its of the 2nd type, it will consist of three integers.   

OUTPUT:
For each query of 2nd type, output "yes" or "no" without the quotes.  

CONSTRAINTS: 
1 ≤ N  ≤ 10^5
1 ≤ Q  ≤ 10^5
1 ≤ L,R ≤ N
All the characters in string S will be lowercase english letters ('a'-'z').

SAMPLE INPUT
5 4
ababb
2 2 3
1 3 b
2 1 4
2 1 5

SAMPLE OUTPUT
no
no
yes

Explanation

For 1st query , 'b' and  'a' can't be rearranged to form the palindrome.
For 3rd query , 'a' , 'b' ,  'b' ,  'b' can't be rearranged to form the palindrome.
For 4th query , all the characters can be rearranged like this "bbabb" to form a palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bobby has decided to hunt some Parrots. There are n horizontal branch of trees aligned parallel to each other. Branches are numbered 1 to n from top to bottom. On each branch there are some parrots sitting next to each other. Supposed there are a[i]$a[i]$ parrots sitting on the i−th$ i-th$ branch.  
Sometimes Bobby shots one of the parrot and the parrot dies (suppose that this parrots sat at the i−th$i-th$ branch). Consequently all the parrots on the i−th$i-th$ branch to the left of the dead parrot get scared and jump up on the branch number i − 1$i - 1$, if there exists no upper branch they fly away. Also all the parrots to the right of the dead parrot jump down on branch number i + 1$i + 1$, if there exists no such branch they fly away.  
Bobby has shot m parrots. You're given the initial number of parrots on each branch, tell him how many parrots are sitting on each branch after the shots.  

-----Input:-----
The first line of the input contains an integer N$N$. The next line contains a list of space-separated integers a1, a2, …, an.
The third line contains an integer M$M$. Each of the next M$M$ lines contains two integers x[i]$x[i]$ and y[i]$y[i]$. The integers mean that for the i-th time Bobby shoot the y[i]-th (from left) parrot on the x[i]-th branch. It's guaranteed there will be at least y[i] parrot on the x[i]-th branch at that moment.   

-----Output:-----
On the i−th$i-th$ line of the output print the number of parrots on the i−th$i-th$ branch.

-----Constraints-----
- 1≤N≤100$1 \leq N \leq 100$
- 0≤a[i]≤100$0 \leq a[i] \leq 100$
- 0≤M≤100$0 \leq M \leq 100$
- 1≤x[i]≤n$1 \leq x[i] \leq n$, 1≤y[i]$1 \leq y[i] $

-----Sample Input:-----
5

10 10 10 10 10

5

2 5

3 13

2 12

1 13

4 6   
3

2 4 1

1

2 2   

-----Sample Output:-----
0

12

5

0

16   
3

0

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find common tangent lines of two circles $c1$ and $c2$.

Constraints

* $-1,000 \leq c1x, c1y, c2x, c2y \leq 1,000$
* $1 \leq c1r, c2r \leq 1,000$
* $c1$ and $c2$ are different

Input

Center coordinates ($cix$, $ciy$) and radii $cir$ of two circles $c1$ are $c2$ are given in the following format.

$c1x \; c1y \; c1r$
$c2x \; c2y \; c2r$

All input values are given in integers.

Output

Print coordinates of the tangent points on circle $c1$ based on the following rules.

* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.00001.

Examples

Input

1 1 1
6 2 2


Output

0.6153846154 1.9230769231
1.0000000000 0.0000000000
1.4183420913 1.9082895434
1.7355040625 0.3224796874


Input

1 2 1
4 2 2


Output

0.6666666667 1.0571909584
0.6666666667 2.9428090416
2.0000000000 2.0000000000


Input

1 2 1
3 2 2


Output

0.5000000000 1.1339745962
0.5000000000 2.8660254038


Input

0 0 1
1 0 2


Output

-1.0000000000 0.0000000000


Input

0 0 1
0 0 2


Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya plays one very well-known and extremely popular MMORPG game. His game character has k skill; currently the i-th of them equals to ai. Also this game has a common rating table in which the participants are ranked according to the product of all the skills of a hero in the descending order.

Vasya decided to 'upgrade' his character via the game store. This store offers n possible ways to improve the hero's skills; Each of these ways belongs to one of three types:

  1. assign the i-th skill to b; 
  2. add b to the i-th skill; 
  3. multiply the i-th skill by b. 



Unfortunately, a) every improvement can only be used once; b) the money on Vasya's card is enough only to purchase not more than m of the n improvements. Help Vasya to reach the highest ranking in the game. To do this tell Vasya which of improvements he has to purchase and in what order he should use them to make his rating become as high as possible. If there are several ways to achieve it, print any of them.

Input

The first line contains three numbers — k, n, m (1 ≤ k ≤ 105, 0 ≤ m ≤ n ≤ 105) — the number of skills, the number of improvements on sale and the number of them Vasya can afford.

The second line contains k space-separated numbers ai (1 ≤ ai ≤ 106), the initial values of skills.

Next n lines contain 3 space-separated numbers tj, ij, bj (1 ≤ tj ≤ 3, 1 ≤ ij ≤ k, 1 ≤ bj ≤ 106) — the type of the j-th improvement (1 for assigning, 2 for adding, 3 for multiplying), the skill to which it can be applied and the value of b for this improvement.

Output

The first line should contain a number l (0 ≤ l ≤ m) — the number of improvements you should use.

The second line should contain l distinct space-separated numbers vi (1 ≤ vi ≤ n) — the indices of improvements in the order in which they should be applied. The improvements are numbered starting from 1, in the order in which they appear in the input. 

Examples

Input

2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2


Output

3
2 3 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Chefland, each chicken has X legs and each duck has Y legs. Chef's farm can have exactly one type of bird. 

Given that the birds on the farm have a total of Z legs:
Print CHICKEN, if the farm can have only chickens but not ducks.
Print DUCK, if the farm can have only ducks but not chickens.
Print ANY, if the farm can have either chickens or ducks.
Print NONE, if the farm can have neither chickens nor ducks.

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

- The first line will contain T, the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, containing three space-separated integers X, Y, Z.

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

For each test case, output in a single line the type of bird on the farm.
- Print CHICKEN, if the farm can have only chickens but not ducks.
- Print DUCK, if the farm can have only ducks but not chickens.
- Print ANY, if the farm can have either chickens or ducks.
- Print NONE, if the farm can have neither chickens nor ducks.

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{AnY}, \texttt{anY}, \texttt{any} and \texttt{ANY} will all be treated as identical).

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

$1 ≤ T ≤ 1000$
$1 ≤ X, Y, Z ≤ 1000$

----- Sample Input 1 ------ 
3
2 3 5
2 2 2
3 4 6
----- Sample Output 1 ------ 
NONE
ANY
CHICKEN
----- explanation 1 ------ 
Test case $1$: There are $5$ legs on the farm. Each chicken has $2$ legs and each duck has $3$ legs. Thus, the farm can have neither chickens nor ducks.

Test case $2$: There are $2$ legs on the farm. Each chicken has $2$ legs and each duck has $2$ legs. Thus, the farm can have any bird among chicken and duck.

Test case $3$: There are $6$ legs on the farm. Each chicken has $3$ legs and each duck has $4$ legs. Thus, the farm can have chicken only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrew was very excited to participate in Olympiad of Metropolises. Days flew by quickly, and Andrew is already at the airport, ready to go home. He has $n$ rubles left, and would like to exchange them to euro and dollar bills. Andrew can mix dollar bills and euro bills in whatever way he wants. The price of one dollar is $d$ rubles, and one euro costs $e$ rubles.

Recall that there exist the following dollar bills: $1$, $2$, $5$, $10$, $20$, $50$, $100$, and the following euro bills — $5$, $10$, $20$, $50$, $100$, $200$ (note that, in this problem we do not consider the $500$ euro bill, it is hard to find such bills in the currency exchange points). Andrew can buy any combination of bills, and his goal is to minimize the total number of rubles he will have after the exchange.

Help him — write a program that given integers $n$, $e$ and $d$, finds the minimum number of rubles Andrew can get after buying dollar and euro bills.


-----Input-----

The first line of the input contains one integer $n$ ($1 \leq n \leq 10^8$) — the initial sum in rubles Andrew has. 

The second line of the input contains one integer $d$ ($30 \leq d \leq 100$) — the price of one dollar in rubles. 

The third line of the input contains integer $e$ ($30 \leq e \leq 100$) — the price of one euro in rubles.


-----Output-----

Output one integer — the minimum number of rubles Andrew can have after buying dollar and euro bills optimally.


-----Examples-----
Input
100
60
70

Output
40

Input
410
55
70

Output
5

Input
600
60
70

Output
0



-----Note-----

In the first example, we can buy just $1$ dollar because there is no $1$ euro bill.

In the second example, optimal exchange is to buy $5$ euro and $1$ dollar.

In the third example, optimal exchange is to buy $10$ dollars in one bill.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem description.
Tic-tac-toe is the third most popular activity to kill a lazy afternoon in Ardenia.Arthum and Breece are not fans of this game, but their mother told them to play, so they sit at a 5 x 5 board. Both have a large pile of marbles: marbles of Arthum have an A written on them and that of Breece have a B. However, as they are both two years old, they have no concept of rounds. Instead, they just toss their marbles as quick as possible, so after a while each board field has either marble A or marble B. 
At that point, they would like to determine the winner, but counting is not their strong point, either. (They are two years old, remember?) Recall that the goal of tic-tac-toe is to have three own marbles in a row, i.e., lying at three consecutive fields horizontally, vertically or diagonally. If both Arthum and Breece have their three marbles in a row, or neither of them has it, we call it a draw. 

Input

The input contains several test cases. The first line of the input contains a positive integer  Z  , denoting the number of test cases.
 Then Z input instances follow, each conforming to the following format: 
The input instance describes marbles placed on the board in a single game. The instance consists of 5 rows and each of them consists of 5 letters:  A or B .

 

Output

You should output one line describing the outcome of the game, i.e., one of the three possible strings: A wins, B wins, or draw .

 

Constraints

Z ≤ 10^5

 

Example
Input:
2
AABBA
BAAAB
AAABA
ABAAB
BAAAB
AAAAA
AAAAA
BAAAA
ABAAA
AABAA

Output:
A wins
draw

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of $n$ integers, $a_0,a_1,\ldots,a_{n-1}$. Find and print any integer $\boldsymbol{x}$ such that $\boldsymbol{x}$ is divisor of every $a_i$ except for exactly one element.

Input Format

The first line contains an integer, $n$, denoting the length of the sequence. 

The second line contains $n$ positive space-separated integers describing $a_0,a_1,\ldots,a_{n-1}$.

Constraints

$1\leq n\leq10^5$
$1\leq a_i\leq10^{18}$
It is guaranteed that a solution exists.

Output Format

Print any positive integer denoting $\boldsymbol{x}$ such that $\boldsymbol{x}$ is a divisor of exactly $n-1$ of the sequence's elements. $\boldsymbol{x}$ must be between $\mbox{1}$ and $2\cdot10^{18}$

Sample Input 0
4
3 6 18 12

Sample Output 0
6

Explanation 0

We are given the array $[3,6,18,12]$. There are two possible answers:

$x=6$ is a divisor of $\boldsymbol{6}$, $12$, and $\mbox{18}$ but not a divisor of $3$.
$x=2$ is a divisor of $\boldsymbol{6}$, $12$, and $\mbox{18}$ but not a divisor of $3$.

Thus, we can print either $\boldsymbol{6}$ or $2$ as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jeff got 2n real numbers a_1, a_2, ..., a_2n as a birthday present. The boy hates non-integer numbers, so he decided to slightly "adjust" the numbers he's got. Namely, Jeff consecutively executes n operations, each of them goes as follows:  choose indexes i and j (i ≠ j) that haven't been chosen yet;  round element a_{i} to the nearest integer that isn't more than a_{i} (assign to a_{i}: ⌊ a_{i} ⌋);  round element a_{j} to the nearest integer that isn't less than a_{j} (assign to a_{j}: ⌈ a_{j} ⌉). 

Nevertheless, Jeff doesn't want to hurt the feelings of the person who gave him the sequence. That's why the boy wants to perform the operations so as to make the absolute value of the difference between the sum of elements before performing the operations and the sum of elements after performing the operations as small as possible. Help Jeff find the minimum absolute value of the difference.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2n real numbers a_1, a_2, ..., a_2n (0 ≤ a_{i} ≤ 10000), given with exactly three digits after the decimal point. The numbers are separated by spaces.


-----Output-----

In a single line print a single real number — the required difference with exactly three digits after the decimal point.


-----Examples-----
Input
3
0.000 0.500 0.750 1.000 2.000 3.000

Output
0.250

Input
3
4469.000 6526.000 4864.000 9356.383 7490.000 995.896

Output
0.279



-----Note-----

In the first test case you need to perform the operations as follows: (i = 1, j = 4), (i = 2, j = 3), (i = 5, j = 6). In this case, the difference will equal |(0 + 0.5 + 0.75 + 1 + 2 + 3) - (0 + 0 + 1 + 1 + 2 + 3)| = 0.25.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Soon a school Olympiad in Informatics will be held in Berland, n schoolchildren will participate there.

At a meeting of the jury of the Olympiad it was decided that each of the n participants, depending on the results, will get a diploma of the first, second or third degree. Thus, each student will receive exactly one diploma.

They also decided that there must be given at least min_1 and at most max_1 diplomas of the first degree, at least min_2 and at most max_2 diplomas of the second degree, and at least min_3 and at most max_3 diplomas of the third degree.

After some discussion it was decided to choose from all the options of distributing diplomas satisfying these limitations the one that maximizes the number of participants who receive diplomas of the first degree. Of all these options they select the one which maximizes the number of the participants who receive diplomas of the second degree. If there are multiple of these options, they select the option that maximizes the number of diplomas of the third degree.

Choosing the best option of distributing certificates was entrusted to Ilya, one of the best programmers of Berland. However, he found more important things to do, so it is your task now to choose the best option of distributing of diplomas, based on the described limitations.

It is guaranteed that the described limitations are such that there is a way to choose such an option of distributing diplomas that all n participants of the Olympiad will receive a diploma of some degree.


-----Input-----

The first line of the input contains a single integer n (3 ≤ n ≤ 3·10^6) — the number of schoolchildren who will participate in the Olympiad.

The next line of the input contains two integers min_1 and max_1 (1 ≤ min_1 ≤ max_1 ≤ 10^6) — the minimum and maximum limits on the number of diplomas of the first degree that can be distributed.

The third line of the input contains two integers min_2 and max_2 (1 ≤ min_2 ≤ max_2 ≤ 10^6) — the minimum and maximum limits on the number of diplomas of the second degree that can be distributed. 

The next line of the input contains two integers min_3 and max_3 (1 ≤ min_3 ≤ max_3 ≤ 10^6) — the minimum and maximum limits on the number of diplomas of the third degree that can be distributed. 

It is guaranteed that min_1 + min_2 + min_3 ≤ n ≤ max_1 + max_2 + max_3.


-----Output-----

In the first line of the output print three numbers, showing how many diplomas of the first, second and third degree will be given to students in the optimal variant of distributing diplomas.

The optimal variant of distributing diplomas is the one that maximizes the number of students who receive diplomas of the first degree. Of all the suitable options, the best one is the one which maximizes the number of participants who receive diplomas of the second degree. If there are several of these options, the best one is the one that maximizes the number of diplomas of the third degree.


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

Output
1 2 3 

Input
10
1 2
1 3
1 5

Output
2 3 5 

Input
6
1 3
2 2
2 2

Output
2 2 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imp is in a magic forest, where xorangles grow (wut?)

 [Image] 

A xorangle of order n is such a non-degenerate triangle, that lengths of its sides are integers not exceeding n, and the xor-sum of the lengths is equal to zero. Imp has to count the number of distinct xorangles of order n to get out of the forest. 

Formally, for a given integer n you have to find the number of such triples (a, b, c), that:

  1 ≤ a ≤ b ≤ c ≤ n;  $a \oplus b \oplus c = 0$, where $x \oplus y$ denotes the bitwise xor of integers x and y.  (a, b, c) form a non-degenerate (with strictly positive area) triangle. 


-----Input-----

The only line contains a single integer n (1 ≤ n ≤ 2500).


-----Output-----

Print the number of xorangles of order n.


-----Examples-----
Input
6

Output
1

Input
10

Output
2



-----Note-----

The only xorangle in the first sample is (3, 5, 6).

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