vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Extra-terrestrial Intelligence

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Recently Vasya got interested in finding extra-terrestrial intelligence. He made a simple extra-terrestrial signals’ receiver and was keeping a record of the signals for *n* days in a row. Each of those *n* days Vasya wrote a 1 in his notebook if he had received a signal that day and a 0 if he hadn’t. Vasya thinks that he has found extra-terrestrial intelligence if there is a system in the way the signals has been received, i.e. if all the intervals between successive signals are equal. Otherwise, Vasya thinks that the signals were sent by some stupid aliens no one cares about. Help Vasya to deduce from the information given by the receiver if he has found extra-terrestrial intelligence or not.

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=≤<=100) — amount of days during which Vasya checked if there were any signals. The second line contains *n* characters 1 or 0 — the record Vasya kept each of those *n* days. It’s guaranteed that the given record sequence contains at least three 1s.

Output Specification:
If Vasya has found extra-terrestrial intelligence, output YES, otherwise output NO.

Demo Input:
['8\n00111000\n', '7\n1001011\n', '7\n1010100\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two binary strings $x$ and $y$, which are binary representations of some two integers (let's denote these integers as $f(x)$ and $f(y)$). You can choose any integer $k \ge 0$, calculate the expression $s_k = f(x) + f(y) \cdot 2^k$ and write the binary representation of $s_k$ in reverse order (let's denote it as $rev_k$). For example, let $x = 1010$ and $y = 11$; you've chosen $k = 1$ and, since $2^1 = 10_2$, so $s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2$ and $rev_k = 00001$.

For given $x$ and $y$, you need to choose such $k$ that $rev_k$ is lexicographically minimal (read notes if you don't know what does "lexicographically" means).

It's guaranteed that, with given constraints, $k$ exists and is finite.


-----Input-----

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

Next $2T$ lines contain a description of queries: two lines per query. The first line contains one binary string $x$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

The second line contains one binary string $y$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

It's guaranteed, that $1 \le f(y) \le f(x)$ (where $f(x)$ is the integer represented by $x$, and $f(y)$ is the integer represented by $y$), both representations don't have any leading zeroes, the total length of $x$ over all queries doesn't exceed $10^5$, and the total length of $y$ over all queries doesn't exceed $10^5$.


-----Output-----

Print $T$ integers (one per query). For each query print such $k$ that $rev_k$ is lexicographically minimal.


-----Example-----
Input
4
1010
11
10001
110
1
1
1010101010101
11110000

Output
1
3
0
0



-----Note-----

The first query was described in the legend.

In the second query, it's optimal to choose $k = 3$. The $2^3 = 1000_2$ so $s_3 = 10001_2 + 110_2 \cdot 1000_2 = 10001 + 110000 = 1000001$ and $rev_3 = 1000001$. For example, if $k = 0$, then $s_0 = 10111$ and $rev_0 = 11101$, but $rev_3 = 1000001$ is lexicographically smaller than $rev_0 = 11101$.

In the third query $s_0 = 10$ and $rev_0 = 01$. For example, $s_2 = 101$ and $rev_2 = 101$. And $01$ is lexicographically smaller than $101$.

The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a very long time, the Chef has a vacation. Chef has planned for two trips during this vacation - one with his family and the other with his friends. The family trip will take X days and the trip with friends will take Y days. Currently, the dates are not decided but the vacation will last only for Z days. 

Chef can be in at most one trip at any time and once a trip is started, Chef must complete it before the vacation ends. Will Chef be able to go on both these trips if he chooses the dates optimally? 

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

- The first line will contain a single integer T denoting the number of test cases. The description of the test cases follows.
- Each test case consists of a single line of input, which contains three space-separated integers X, Y and Z.

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

For each test case, output in a single line the answer: "YES" if Chef can go on both the trips and "NO" if not.

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

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

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

----- Sample Input 1 ------ 
2
1 2 4
2 2 3
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
Test case $1$: Chef can go to the family trip on day $1$ and the friends trip on days $2$ and $3$.

Alternatively, Chef can also plan the trip with friends on days $1$ and $2$ and the family trip on day $4$.

Test case $2$: Chef cannot plan both trips within $3$ days.

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

You have to write a function `pattern` which returns the following Pattern(See Examples) upto (2n-1) rows, where n is parameter.

* Note:`Returning` the pattern is not the same as `Printing` the pattern.

#### Parameters:
    
    pattern(        n        );
                    ^                     
                    |                     
             Term upto which   
           Basic Pattern(this)     
                should be         
                 created            
                                  
                                
#### Rules/Note:
* If `n < 1` then it should return "" i.e. empty string.
* `The length of each line is same`, and is equal to the length of longest line in the pattern i.e (2n-1).
* Range of Parameters (for the sake of CW Compiler) :
  + `n ∈ (-∞,100]`

### Examples:

* pattern(5):

        1       1
         2     2 
          3   3  
           4 4   
            5    
           4 4   
          3   3  
         2     2 
        1       1
       
        
* pattern(10):

        1                 1
         2               2 
          3             3  
           4           4   
            5         5    
             6       6     
              7     7      
               8   8       
                9 9        
                 0         
                9 9        
               8   8       
              7     7      
             6       6     
            5         5    
           4           4   
          3             3  
         2               2 
        1                 1
    
* pattern(15):

        1                           1
         2                         2 
          3                       3  
           4                     4   
            5                   5    
             6                 6     
              7               7      
               8             8       
                9           9        
                 0         0         
                  1       1          
                   2     2           
                    3   3            
                     4 4             
                      5              
                     4 4             
                    3   3            
                   2     2           
                  1       1          
                 0         0         
                9           9        
               8             8       
              7               7      
             6                 6     
            5                   5    
           4                     4   
          3                       3  
         2                         2 
        1                           1
    
[List of all my katas]("http://www.codewars.com/users/curious_db97/authored")

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Adrian, Bruno and Goran wanted to join the bird lovers’ club. However, they did not know that all applicants must pass an entrance exam. The exam consists of $N$ questions, each with three possible answers: A, B and C.

Unfortunately, they couldn’t tell a bird from a whale so they are trying to guess the correct answers. Each of the three boys has a theory of what set of answers will work best:

Adrian claims that the best sequence is: A, B, C, A, B, C, A, B, C, A, B, C ...

Bruno is convinced that this is better: B, A, B, C, B, A, B, C, B, A, B, C ...

Goran laughs at them and will use this sequence: C, C, A, A, B, B, C, C, A, A, B, B ...

Write a program that, given the correct answers to the exam, determines who of the three was right – whose sequence contains the most correct answers.

-----Input-----
The first line contains an integer $N$ ($1 \le N \le 100$), the number of questions on the exam.

The second line contains a string of $N$ letters ‘A’, ‘B’ and ‘C’. These are, in order, the correct answers to the questions in the exam.

-----Output-----
On the first line, output $M$, the largest number of correct answers one of the three boys gets.

After that, output the names of the boys (in alphabetical order) whose sequences result in $M$ correct answers.

-----Examples-----
Sample Input:
5
BAACC
Sample Output:
3
Bruno

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers a, b, k.

Find two binary integers x and y (x ≥ y) such that 

  1. both x and y consist of a zeroes and b ones; 
  2. x - y (also written in binary form) has exactly k ones. 

You are not allowed to use leading zeros for x and y. 

Input

The only line contains three integers a, b, and k (0 ≤ a; 1 ≤ b; 0 ≤ k ≤ a + b ≤ 2 ⋅ 10^5) — the number of zeroes, ones, and the number of ones in the result.

Output

If it's possible to find two suitable integers, print "Yes" followed by x and y in base-2.

Otherwise print "No".

If there are multiple possible answers, print any of them.

Examples

Input


4 2 3


Output


Yes
101000
100001


Input


3 2 1


Output


Yes
10100
10010


Input


3 2 5


Output


No

Note

In the first example, x = 101000_2 = 2^5 + 2^3 = 40_{10}, y = 100001_2 = 2^5 + 2^0 = 33_{10}, 40_{10} - 33_{10} = 7_{10} = 2^2 + 2^1 + 2^0 = 111_{2}. Hence x-y has 3 ones in base-2.

In the second example, x = 10100_2 = 2^4 + 2^2 = 20_{10}, y = 10010_2 = 2^4 + 2^1 = 18, x - y = 20 - 18 = 2_{10} = 10_{2}. This is precisely one 1.

In the third example, one may show, that it's impossible to find an answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You need to swap the head and the tail of the specified array:

the head (the first half) of array moves to the end, the tail (the second half) moves to the start. 
The middle element (if it exists) leaves on the same position.

Return new array.


 For example:
 ```
    [ 1, 2, 3, 4, 5 ]   =>  [ 4, 5, 3, 1, 2 ]
     \----/   \----/         
      head     tail 
 
    [ -1, 2 ]  => [ 2, -1 ] 
    [ 1, 2, -3, 4, 5, 6, -7, 8 ]   =>  [ 5, 6, -7, 8, 1, 2, -3, 4 ]  
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The recent All-Berland Olympiad in Informatics featured n participants with each scoring a certain amount of points.

As the head of the programming committee, you are to determine the set of participants to be awarded with diplomas with respect to the following criteria:   At least one participant should get a diploma.  None of those with score equal to zero should get awarded.  When someone is awarded, all participants with score not less than his score should also be awarded. 

Determine the number of ways to choose a subset of participants that will receive the diplomas.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of participants.

The next line contains a sequence of n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 600) — participants' scores.

It's guaranteed that at least one participant has non-zero score.


-----Output-----

Print a single integer — the desired number of ways.


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

Output
3

Input
3
1 1 1

Output
1

Input
4
42 0 0 42

Output
1



-----Note-----

There are three ways to choose a subset in sample case one.  Only participants with 3 points will get diplomas.  Participants with 2 or 3 points will get diplomas.  Everyone will get a diploma! 

The only option in sample case two is to award everyone.

Note that in sample case three participants with zero scores cannot get anything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"I'm a fan of anything that tries to replace actual human contact." - Sheldon.
After years of hard work, Sheldon was finally able to develop a formula which would diminish the real human contact.  
He found k$k$ integers n1,n2...nk$n_1,n_2...n_k$ . Also he found that if he could minimize the value of m$m$ such that  ∑ki=1$\sum_{i=1}^k$n$n$i$i$C$C$m$m$i$i$ is even, where m$m$ = ∑ki=1$\sum_{i=1}^k$mi$m_i$, he would finish the real human contact.  
Since Sheldon is busy choosing between PS-4 and XBOX-ONE, he want you to help him to calculate the minimum value of m$m$. 

-----Input:-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The 
description of T$T$ test cases follows.
- The first line of each test case contains a single integer k$k$.
- Next line contains k space separated integers n1,n2...nk$n_1,n_2...n_k$ .

-----Output:-----
For each test case output the minimum value of m for which ∑ki=1$\sum_{i=1}^k$n$n$i$i$C$C$m$m$i$i$ is even, where  m$m$=m1$m_1$+m2$m_2$+. . . mk$m_k$   and  0$0$ <= mi$m_i$<= ni$n_i$ .  If no such answer exists print -1.

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 1≤k≤1000$1 \leq k \leq 1000$
- 1≤ni≤10$1 \leq n_i \leq 10$18$18$

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

-----Sample Output:-----
2

-----EXPLANATION:-----
5$5$C$C$2$2$ = 10 which is even and m is minimum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amr loves Chemistry, and specially doing experiments. He is preparing for a new interesting experiment.

Amr has n different types of chemicals. Each chemical i has an initial volume of a_{i} liters. For this experiment, Amr has to mix all the chemicals together, but all the chemicals volumes must be equal first. So his task is to make all the chemicals volumes equal.

To do this, Amr can do two different kind of operations.   Choose some chemical i and double its current volume so the new volume will be 2a_{i}  Choose some chemical i and divide its volume by two (integer division) so the new volume will be $\lfloor \frac{a_{i}}{2} \rfloor$ 

Suppose that each chemical is contained in a vessel of infinite volume. Now Amr wonders what is the minimum number of operations required to make all the chemicals volumes equal?


-----Input-----

The first line contains one number n (1 ≤ n ≤ 10^5), the number of chemicals.

The second line contains n space separated integers a_{i} (1 ≤ a_{i} ≤ 10^5), representing the initial volume of the i-th chemical in liters.


-----Output-----

Output one integer the minimum number of operations required to make all the chemicals volumes equal.


-----Examples-----
Input
3
4 8 2

Output
2
Input
3
3 5 6

Output
5


-----Note-----

In the first sample test, the optimal solution is to divide the second chemical volume by two, and multiply the third chemical volume by two to make all the volumes equal 4.

In the second sample test, the optimal solution is to divide the first chemical volume by two, and divide the second and the third chemical volumes by two twice to make all the volumes equal 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pythagorean triplet (a,b,c) satisfies: 
You will be given an integer N. You have to count how many triplets a,b,c exist such that  
1 ≤ a ≤ b ≤ c ≤ N.

Input: 
First line contains T, the number of testcases. Each testcase consists of only one integer in one line.    

Output: 
For each testcase, print the required answer.   

Constraints: 
1 ≤ T ≤ 100 
1 ≤ N ≤ 10^6

SAMPLE INPUT
2
5
10

SAMPLE OUTPUT
1
2

Explanation

In first testcase, only one triplet ie. (3,4,5)
In second testcase, two triplets ie. (3,4,5),(6,8,10).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program that, given a word, computes the scrabble score for that word.

## Letter Values

You'll need these:

```
Letter                           Value
A, E, I, O, U, L, N, R, S, T       1
D, G                               2
B, C, M, P                         3
F, H, V, W, Y                      4
K                                  5
J, X                               8
Q, Z                               10
```

```if:ruby,javascript,cfml
There will be a preloaded hashtable `$dict` with all these values: `$dict["E"] == 1`. 
```
```if:haskell
There will be a preloaded list of `(Char, Int)` tuples called `dict` with all these values.
```
```if:python
There will be a preloaded dictionary `dict_scores` with all these values: `dict_scores["E"] == 1`
```

## Examples
```
"cabbage" --> 14
```

"cabbage" should be scored as worth 14 points:

- 3 points for C
- 1 point for A, twice
- 3 points for B, twice
- 2 points for G
- 1 point for E

And to total:

`3 + 2*1 + 2*3 + 2 + 1` = `3 + 2 + 6 + 3` = `14`


Empty string should return `0`. The string can contain spaces and letters (upper and lower case), you should calculate the scrabble score only of the letters in that string.

```
""           --> 0
"STREET"    --> 6
"st re et"    --> 6
"ca bba g  e" --> 14
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:
 - For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.
 - There is an edge between Vertex X and Vertex Y.
For each k=1,2,...,N-1, solve the problem below:
 - Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

-----Constraints-----
 - 3 \leq N \leq 2 \times 10^3
 - 1 \leq X,Y \leq N
 - X+1 < Y
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X Y

-----Output-----
For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

-----Sample Input-----
5 2 4

-----Sample Output-----
5
4
1
0

The graph in this input is as follows:





There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).


There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).


There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).


There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Summer holidays! Someone is going on trips, someone is visiting grandparents, but someone is trying to get a part-time job. This summer Noora decided that she wants to earn some money, and took a job in a shop as an assistant.

Shop, where Noora is working, has a plan on the following n days. For each day sales manager knows exactly, that in i-th day k_{i} products will be put up for sale and exactly l_{i} clients will come to the shop that day. Also, the manager is sure, that everyone, who comes to the shop, buys exactly one product or, if there aren't any left, leaves the shop without buying anything. Moreover, due to the short shelf-life of the products, manager established the following rule: if some part of the products left on the shelves at the end of the day, that products aren't kept on the next day and are sent to the dump.

For advertising purposes manager offered to start a sell-out in the shop. He asked Noora to choose any f days from n next for sell-outs. On each of f chosen days the number of products were put up for sale would be doubled. Thus, if on i-th day shop planned to put up for sale k_{i} products and Noora has chosen this day for sell-out, shelves of the shop would keep 2·k_{i} products. Consequently, there is an opportunity to sell two times more products on days of sell-out.

Noora's task is to choose f days to maximize total number of sold products. She asks you to help her with such a difficult problem.


-----Input-----

The first line contains two integers n and f (1 ≤ n ≤ 10^5, 0 ≤ f ≤ n) denoting the number of days in shop's plan and the number of days that Noora has to choose for sell-out.

Each line of the following n subsequent lines contains two integers k_{i}, l_{i} (0 ≤ k_{i}, l_{i} ≤ 10^9) denoting the number of products on the shelves of the shop on the i-th day and the number of clients that will come to the shop on i-th day.


-----Output-----

Print a single integer denoting the maximal number of products that shop can sell.


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

Output
10
Input
4 1
0 2
0 3
3 5
0 6

Output
5


-----Note-----

In the first example we can choose days with numbers 2 and 4 for sell-out. In this case new numbers of products for sale would be equal to [2, 6, 2, 2] respectively. So on the first day shop will sell 1 product, on the second — 5, on the third — 2, on the fourth — 2. In total 1 + 5 + 2 + 2 = 10 product units.

In the second example it is possible to sell 5 products, if you choose third day for sell-out.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing a game with $n$ piles of stones. It is guaranteed that $n$ is an even number. The $i$-th pile has $a_i$ stones.

Alice and Bob will play a game alternating turns with Alice going first.

On a player's turn, they must choose exactly $\frac{n}{2}$ nonempty piles and independently remove a positive number of stones from each of the chosen piles. They can remove a different number of stones from the piles in a single turn. The first player unable to make a move loses (when there are less than $\frac{n}{2}$ nonempty piles).

Given the starting configuration, determine who will win the game.


-----Input-----

The first line contains one integer $n$ ($2 \leq n \leq 50$) — the number of piles. It is guaranteed that $n$ is an even number.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 50$) — the number of stones in the piles.


-----Output-----

Print a single string "Alice" if Alice wins; otherwise, print "Bob" (without double quotes).


-----Examples-----
Input
2
8 8

Output
Bob

Input
4
3 1 4 1

Output
Alice



-----Note-----

In the first example, each player can only remove stones from one pile ($\frac{2}{2}=1$). Alice loses, since Bob can copy whatever Alice does on the other pile, so Alice will run out of moves first.

In the second example, Alice can remove $2$ stones from the first pile and $3$ stones from the third pile on her first move to guarantee a win.

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