vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: The Child and Set

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.

Fortunately, Picks remembers something about his set *S*:
 -  its elements were distinct integers from 1 to *limit*; -  the value of  was equal to *sum*; here *lowbit*(*x*) equals 2*k* where *k* is the position of the first one in the binary representation of *x*. For example, *lowbit*(100102)<==<=102,<=*lowbit*(100012)<==<=12,<=*lowbit*(100002)<==<=100002 (binary representation). 
Can you help Picks and find any set *S*, that satisfies all the above conditions?

Input Specification:
The first line contains two integers: *sum*,<=*limit* (1<=≤<=*sum*,<=*limit*<=≤<=105).

Output Specification:
In the first line print an integer *n* (1<=≤<=*n*<=≤<=105), denoting the size of *S*. Then print the elements of set *S* in any order. If there are multiple answers, print any of them.

If it's impossible to find a suitable set, print -1.

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

Demo Output:
['2\n4 5\n', '3\n2 3 1\n', '-1\n']

Note:
In sample test 1: *lowbit*(4) = 4, *lowbit*(5) = 1, 4 + 1 = 5.

In sample test 2: *lowbit*(1) = 1, *lowbit*(2) = 2, *lowbit*(3) = 1, 1 + 2 + 1 = 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jim enters a candy shop which has N different types of candies, each candy is of the same price. Jim has enough money to buy K candies. In how many different ways can he purchase K candies if there are infinite candies of each kind? 

Input Format 

The first line contains an integer T, the number of tests. 

This is followed by 2T lines which contain T tests: 

The first line (of each testcase) is an integer N and the second line (of each testcase) is an integer K.   

Output Format 

For each testcase, print the number of ways Jim can buy candies from the shop in a newline. If the answer has more than 9 digits, print the last 9 digits.  

Note 

This problem may expect you to have solved nCr Table

Constraints 

1 <= T <= 200 

1 <= N < 1000 

1 <= K < 1000  

Sample Input  

2
4
1
2
3

Sample Output  

4
4

Explanation 

There are 2 testcases, for the first testcase we have N = 4 and K = 1, as Jim can buy only 1 candy, he can choose to buy any of the 4 types of candies available. Hence, his answer is 4.
For the 2nd testcase, we have N = 2 and K = 3, If we name two chocolates as a and b, he can buy 

aaa bbb aab abb 

chocolates, hence 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward. Examples of numerical palindromes are: 

2332
110011
54322345

For a given number ```num```, return its closest numerical palindrome which can either be smaller or larger than ```num```. If there are 2 possible values, the larger value should be returned. If ```num``` is a numerical palindrome itself, return it. 

For this kata, single digit numbers will NOT be considered numerical palindromes. 

Also, you know the drill - be sure to return "Not valid" if the input is not an integer or is less than 0.

```
palindrome(8) => 11
palindrome(281) => 282 
palindrome(1029) => 1001
palindrome(1221) => 1221
palindrome("1221") => "Not valid"

```

```Haskell
In Haskell the function should return a Maybe Int with Nothing for cases where the argument is less than zero.
```
Other Kata in this Series:
Numerical Palindrome #1
Numerical Palindrome #1.5
Numerical Palindrome #2
Numerical Palindrome #3
Numerical Palindrome #3.5
Numerical Palindrome #4
Numerical Palindrome #5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number d, representing the number of digits of a number. Find the total count of positive integers which have at-least one zero in them and consist d or less digits.
Example 1:
Input: d = 2
Output: 9 
Explanation: There are total 9 
positive integers which have 
at-least one zero in them 
and consist 2 or less digits.
Example 2:
Input: d = 3
Output: 180
Explanation: There are total 180
positive integers which have
at-least one zero in them
and consist 3 or less digits.
Your Task:  
You dont need to read input or print anything. Complete the function findCountUpto() which takes d as input parameter and returns the total count of positive integers which have at-least one zero in them and consist d or less digits.
Expected Time Complexity: O(logn)
Expected Auxiliary Space: O(1)
Constraints:
1<= d <=15

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Rick and Morty are playing their own version of Berzerk (which has nothing in common with the famous Berzerk game). This game needs a huge space, so they play it with a computer.

In this game there are *n* objects numbered from 1 to *n* arranged in a circle (in clockwise order). Object number 1 is a black hole and the others are planets. There's a monster in one of the planet. Rick and Morty don't know on which one yet, only that he's not initially in the black hole, but Unity will inform them before the game starts. But for now, they want to be prepared for every possible scenario.

Each one of them has a set of numbers between 1 and *n*<=-<=1 (inclusive). Rick's set is *s*1 with *k*1 elements and Morty's is *s*2 with *k*2 elements. One of them goes first and the player changes alternatively. In each player's turn, he should choose an arbitrary number like *x* from his set and the monster will move to his *x*-th next object from its current position (clockwise). If after his move the monster gets to the black hole he wins.

Your task is that for each of monster's initial positions and who plays first determine if the starter wins, loses, or the game will stuck in an infinite loop. In case when player can lose or make game infinity, it more profitable to choose infinity game.

Input Specification:
The first line of input contains a single integer *n* (2<=≤<=*n*<=≤<=7000) — number of objects in game.

The second line contains integer *k*1 followed by *k*1 distinct integers *s*1,<=1,<=*s*1,<=2,<=...,<=*s*1,<=*k*1 — Rick's set.

The third line contains integer *k*2 followed by *k*2 distinct integers *s*2,<=1,<=*s*2,<=2,<=...,<=*s*2,<=*k*2 — Morty's set

1<=≤<=*k**i*<=≤<=*n*<=-<=1 and 1<=≤<=*s**i*,<=1,<=*s**i*,<=2,<=...,<=*s**i*,<=*k**i*<=≤<=*n*<=-<=1 for 1<=≤<=*i*<=≤<=2.

Output Specification:
In the first line print *n*<=-<=1 words separated by spaces where *i*-th word is "Win" (without quotations) if in the scenario that Rick plays first and monster is initially in object number *i*<=+<=1 he wins, "Lose" if he loses and "Loop" if the game will never end.

Similarly, in the second line print *n*<=-<=1 words separated by spaces where *i*-th word is "Win" (without quotations) if in the scenario that Morty plays first and monster is initially in object number *i*<=+<=1 he wins, "Lose" if he loses and "Loop" if the game will never end.

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

Demo Output:
['Lose Win Win Loop\nLoop Win Win Win\n', 'Win Win Win Win Win Win Win\nLose Win Lose Lose Win Lose Lose\n']

Note:
none

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

Problem Statement

~ How to draw a magic circle ~

1. Prepare a sufficiently large and white floor.
2. Draw a circle with radii 1, 2, ..., R centered on the point at the floor coordinates (0,0).
3. Paint blue between the circle with radius 1 and the circle with radius 2, between the circle with radius 3 and the circle with radius 4, ... Do not paint outside the circle with radius R.
4. Draw a polygon with N vertices on the floor.
5. Repaint the white area inside the polygon with blue and the blue area with white.



It is said that the power of the magic circle becomes stronger as the magic circle contains more blue.
Therefore, I would like you to find the area of ​​the blue area included in the magic circle.

The following figure is an example of a magic circle that can be drawn by this procedure.

<image>

Constraints

* 3 ≤ N ≤ 100
* 1 ≤ R ≤ 100
* Polygons are included inside or on the circumference of a circle with radius R.
* Polygons do not have self-intersections.
* The vertices of the polygon are given in a counterclockwise order.

Input

Input follows the following format. All given numbers are integers.


N R
x_1 y_1
...
x_N y_N

(x_i, y_i) is the i-th vertex of the polygon.

Output

Output the area of ​​the blue area on one line.
The output value must have an absolute or relative error of less than 10 ^ {-8} with the true value.

Examples

Input

3 1
0 0
1 0
0 1


Output

0.500000000


Input

3 2
0 0
2 0
0 2


Output

8.995574288


Input

3 2
1 -1
1 1
-2 0


Output

11.123246567


Input

4 3
1 1
-1 1
-1 -1
1 -1


Output

11.707963268

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We all love the future president (or Führer or duce or sōtō as he could find them more fitting) donald trump, but we might fear that some of his many fans like John Miller or John Barron are not making him justice, sounding too much like their (and our as well, of course!) hero and thus risking to compromise him.

For this reason we need to create a function to detect the original and unique rythm of our beloved leader, typically having a lot of extra vowels, all ready to fight the estabilishment.

The index is calculated based on how many vowels are repeated more than once in a row and dividing them by the total number of vowels a petty enemy of America would use.

For example:
```python
trump_detector("I will build a huge wall")==0 #definitely not our trump: 0 on the trump score
trump_detector("HUUUUUGEEEE WAAAAAALL")==4 #4 extra "U", 3 extra "E" and 5 extra "A" on 3 different vowel groups: 12/3 make for a trumpy trumping score of 4: not bad at all!
trump_detector("listen migrants: IIII KIIIDD YOOOUUU NOOOOOOTTT")==1.56 #14 extra vowels on 9 base ones
```
**Notes:** vowels are only the ones in the patriotic group of "aeiou": "y" should go back to Greece if she thinks she can have the same rights of true American vowels; there is always going to be at least a vowel, as silence is the option of coward Kenyan/terrorist presidents and their friends.

Round each result by two decimal digits: there is no place for small fry in Trump's America.

*Special thanks for [Izabela](https://www.codewars.com/users/ijelonek) for support and proof-reading.*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A has a string consisting of some number of lowercase English letters 'a'. He gives it to his friend B who appends some number of letters 'b' to the end of this string. Since both A and B like the characters 'a' and 'b', they have made sure that at this point, at least one 'a' and one 'b' exist in the string.

B now gives this string to C and he appends some number of letters 'c' to the end of the string. However, since C is a good friend of A and B, the number of letters 'c' he appends is equal to the number of 'a' or to the number of 'b' in the string. It is also possible that the number of letters 'c' equals both to the number of letters 'a' and to the number of letters 'b' at the same time.

You have a string in your hands, and you want to check if it is possible to obtain the string in this way or not. If it is possible to obtain the string, print "YES", otherwise print "NO" (without the quotes).


-----Input-----

The first and only line consists of a string $S$ ($ 1 \le |S| \le 5\,000 $). It is guaranteed that the string will only consist of the lowercase English letters 'a', 'b', 'c'.


-----Output-----

Print "YES" or "NO", according to the condition.


-----Examples-----
Input
aaabccc

Output
YES

Input
bbacc

Output
NO

Input
aabc

Output
YES



-----Note-----

Consider first example: the number of 'c' is equal to the number of 'a'. 

Consider second example: although the number of 'c' is equal to the number of the 'b', the order is not correct.

Consider third example: the number of 'c' is equal to the number of 'b'.

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

Aizu decided to play a game using a prime number $ P $, a set of natural numbers $ G $, and a natural number $ A $.

First, Aizu writes $ 1 $ on the paper at hand. After that, perform the following series of operations any number of times.

* Select one element from $ G $. Let this be $ g $.
* Write a new product of the number written on the paper at hand and $ g $ on the paper.
* Erase the number originally written on the paper.



If $ A $ is equal to the number written on the paper at hand divided by $ P $, Aizu wins, otherwise he loses. Determine if Aizu can win when $ P $, $ G $, and $ A $ are given.

Constraints

The input satisfies the following conditions.

* All inputs are integers.
* $ 2 \ le P \ le 2 ^ {31} -1 $
* $ 1 \ le T, | G | \ le 10 ^ 5 $
* $ 1 \ le G_i, A \ le P-1 $
* $ G_i \ ne G_j, $ if $ i \ ne j $
* The sum of $ | G | $ in all test cases does not exceed $ 10 ^ 5 $.

Input

The input is given in the following format.


$ P $ $ T $
$ Test_1 $
$ \ vdots $
$ Test_ {T} $


The input consists of multiple test cases. First, the $ 1 $ line is given the prime number $ P $ and the number of test cases $ T $. $ P $ is common to all test cases. Each test case is given in the following $ T $ line.

Each test case is given as follows.


$ | G | $ $ G_1 $ $ \ dots $ $ G_ {| G |} $ $ A $


In each test case, the number of elements of $ G $, each element of $ G $, and $ A $ are given in order, separated by a space.

Output

For each test case, if Aizu can win, $ 1 $ will be output on one line, otherwise $ 0 $ will be output on one line.

Examples

Input

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


Output

0
1
0


Input

1000000007 8
3 2 9 7 5
3 2 9 5 1000001
3 39 1002 65537 12
2 1000000006 518012930 793649232
10 459268180 313723762 835892239 612038995 90424474 366392946 38051435 854115735 5132833 320534710 421820264
1 1 1
1 1 1000000006
1 1000000006 1


Output

0
1
1
1
0
1
0
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, Your task is to  complete the function encode that returns the run length encoded string for the given string.
eg if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6″.
You are required to complete the function encode that takes only one argument the string which is to be encoded and returns the encoded string.
Example 1:
Input:
str = aaaabbbccc
Output: a4b3c3
Explanation: a repeated 4 times
consecutively b 3 times, c also 3
times.
Example 2:
Input:
str = abbbcdddd
Output: a1b3c1d4
Your Task:
Complete the function encode() which takes a character array as a input parameter and returns the encoded string.
Expected Time Complexity: O(N), N = length of given string.
Expected Auxiliary Space: O(1)
Constraints:
1<=length of str<=100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While doing some spring cleaning, Daniel found an old calculator that he loves so much. However, it seems like it is broken. When he tries to compute $1 + 3$ using the calculator, he gets $2$ instead of $4$. But when he tries computing $1 + 4$, he gets the correct answer, $5$. Puzzled by this mystery, he opened up his calculator and found the answer to the riddle: the full adders became half adders! 

So, when he tries to compute the sum $a + b$ using the calculator, he instead gets the xorsum $a \oplus b$ (read the definition by the link: https://en.wikipedia.org/wiki/Exclusive_or).

As he saw earlier, the calculator sometimes gives the correct answer. And so, he wonders, given integers $l$ and $r$, how many pairs of integers $(a, b)$ satisfy the following conditions: $$a + b = a \oplus b$$ $$l \leq a \leq r$$ $$l \leq b \leq r$$

However, Daniel the Barman is going to the bar and will return in two hours. He tells you to solve the problem before he returns, or else you will have to enjoy being blocked.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of testcases.

Then, $t$ lines follow, each containing two space-separated integers $l$ and $r$ ($0 \le l \le r \le 10^9$).


-----Output-----

Print $t$ integers, the $i$-th integer should be the answer to the $i$-th testcase.


-----Example-----
Input
3
1 4
323 323
1 1000000

Output
8
0
3439863766



-----Note-----

$a \oplus b$ denotes the bitwise XOR of $a$ and $b$.

For the first testcase, the pairs are: $(1, 2)$, $(1, 4)$, $(2, 1)$, $(2, 4)$, $(3, 4)$, $(4, 1)$, $(4, 2)$, and $(4, 3)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This time, there will be no unnecessary information in the problem statement.

Given an array(A) of N integers, find the probability that sum of any selected triplet is a cube of an integer number.

A triplet is a set of any three indices. Two triplets with same indices but in different order are considered same (Ex: triplets with indices {2,4,5} and {2,5,4} are same).

Cube of a number x is x * x * x.

Input:

First line has an integer T=number of test cases.
Each test case has two lines.
First line of test case has an integer N=numbers in the array.
Second line of test case has an array of N integers.

Output:

Print answer for each test case in a separate lines with exactly 9 decimal digits.  

Constraints:

1 ≤ T ≤ 40
3 ≤ N ≤ 500
1 ≤ Ai ≤ 2000  

SAMPLE INPUT
2
4
2 3 4 6
4
1 1 6 25

SAMPLE OUTPUT
0.000000000
0.500000000

Explanation

Case #1 : No triplet sum could be cube of an integer.

Case #2 : We can form 4 triplets.

Indices        Values       Sum  
{1,2,3}        {1,1, 6}    1+1+6 = 8  
{1,2,4}        {1,1,25}    1+1+25 = 27  
{1,3,4}        {1,6,25}    1+6+25 = 32
{2,3,4}        {1,6,25}    1+6+25 = 32

Out of 4 resulting sums, 2 are cube of a number and therefore probability is 2/4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a simple parser that will parse and run Deadfish.  

Deadfish has 4 commands, each 1 character long:
* `i` increments the value (initially `0`)
* `d` decrements the value
* `s` squares the value
* `o` outputs the value into the return array

Invalid characters should be ignored.

```python
parse("iiisdoso")  ==>  [8, 64]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima and his friends have been playing hide and seek at Dima's place all night. As a result, Dima's place got messy. In the morning they decided that they need to clean the place.

To decide who exactly would clean the apartment, the friends want to play a counting-out game. First, all the guys stand in a circle, and then each of them shows some number of fingers on one hand (one to five), and then the boys count in a circle, starting from Dima, the number of people, respective to the total number of fingers shown. The person on who the countdown stops will clean the apartment.

For example, if Dima and one of his friends played hide and seek, and 7 fingers were shown during the counting-out, then Dima would clean the place. If there were 2 or say, 8 fingers shown, then his friend would clean the place.

Dima knows how many fingers each of his friends will show during the counting-out. Now he is interested in the number of ways to show some number of fingers on one hand (one to five), so that he did not have to clean the place. Help Dima.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of Dima's friends. Dima himself isn't considered to be his own friend. The second line contains n positive integers, not exceeding 5, representing, how many fingers the Dima's friends will show. 

The numbers in the lines are separated by a single space.


-----Output-----

In a single line print the answer to the problem.


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

Output
3

Input
1
2

Output
2

Input
2
3 5

Output
3



-----Note-----

In the first sample Dima can show 1, 3 or 5 fingers. If Dima shows 3 fingers, then the counting-out will go like that: Dima, his friend, Dima, his friend.

In the second sample Dima can show 2 or 4 fingers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lee bought some food for dinner time, but Lee's friends eat dinner in a deadly way. Lee is so scared, he doesn't want to die, at least not before seeing Online IOI 2020...

There are $n$ different types of food and $m$ Lee's best friends. Lee has $w_i$ plates of the $i$-th type of food and each friend has two different favorite types of food: the $i$-th friend's favorite types of food are $x_i$ and $y_i$ ($x_i \ne y_i$).

Lee will start calling his friends one by one. Whoever is called will go to the kitchen and will try to eat one plate of each of his favorite food types. Each of the friends will go to the kitchen exactly once.

The only problem is the following: if a friend will eat at least one plate of food (in total) then he will be harmless. But if there is nothing left for him to eat (neither $x_i$ nor $y_i$), he will eat Lee instead $\times\_\times$.

Lee can choose the order of friends to call, so he'd like to determine if he can survive dinner or not. Also, he'd like to know the order itself.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$; $1 \le m \le 2 \cdot 10^5$) — the number of different food types and the number of Lee's friends. 

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \le w_i \le 10^6$) — the number of plates of each food type.

The $i$-th line of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$) — the favorite types of food of the $i$-th friend. 


-----Output-----

If Lee can survive the dinner then print ALIVE (case insensitive), otherwise print DEAD (case insensitive).

Also, if he can survive the dinner, print the order Lee should call friends. If there are multiple valid orders, print any of them.


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

Output
ALIVE
3 2 1 

Input
3 2
1 1 0
1 2
1 3

Output
ALIVE
2 1 

Input
4 4
1 2 0 1
1 3
1 2
2 3
2 4

Output
ALIVE
1 3 2 4 

Input
5 5
1 1 1 2 1
3 4
1 2
2 3
4 5
4 5

Output
ALIVE
5 4 1 3 2 

Input
4 10
2 4 1 4
3 2
4 2
4 1
3 1
4 1
1 3
3 2
2 1
3 1
2 4

Output
DEAD



-----Note-----

In the first example, any of the following orders of friends are correct : $[1, 3, 2]$, $[3, 1, 2]$, $[2, 3, 1]$, $[3, 2, 1]$.

In the second example, Lee should call the second friend first (the friend will eat a plate of food $1$) and then call the first friend (the friend will eat a plate of food $2$). If he calls the first friend sooner than the second one, then the first friend will eat one plate of food $1$ and food $2$ and there will be no food left for the second friend to eat.

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