vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
With a friend we used to play the following game on a chessboard
(8, rows, 8 columns).
On the first row at the *bottom* we put numbers:

`1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9`

On row 2 (2nd row from the bottom) we have:

`1/3, 2/4, 3/5, 4/6, 5/7, 6/8, 7/9, 8/10`

On row 3:

`1/4, 2/5, 3/6, 4/7, 5/8, 6/9, 7/10, 8/11`

until last row:

`1/9, 2/10, 3/11, 4/12, 5/13, 6/14, 7/15, 8/16`


When all numbers are on the chessboard each in turn we toss a coin. The one who get "head" wins and
the other gives him, in dollars, the **sum of the numbers on the chessboard**.
We play for fun, the dollars come from a monopoly game! 

### Task
How much can I (or my friend) win or loses for each game if the chessboard has n rows and n columns? Add all of the fractional values on an n by n sized board and give the answer as a simplified fraction.
  
- Ruby, Python, JS, Coffee, Clojure, PHP, Elixir, Crystal, Typescript, Go:

The function called 'game' with parameter n (integer >= 0) returns as result an irreducible fraction written as an array of integers: [numerator, denominator].
If the denominator is 1 return [numerator].

- Haskell:

'game' returns either a "Left Integer" if denominator is 1 otherwise 
"Right (Integer, Integer)" 

- Prolog:
'game' returns an irreducible fraction written as an array of integers: [numerator, denominator].
If the denominator is 1 return [numerator, 1].

- Java, C#, C++, F#, Swift, Reason, Kotlin:

'game' returns a string that mimicks the array returned in Ruby, Python, JS, etc...

- Fortran, Bash: 'game' returns a string


- Forth: return on the stack the numerator and the denominator (even if the denominator is 1)


- In Fortran - as in any other language - the returned string is not permitted
to contain any redundant trailing whitespace: you can use dynamically allocated character strings.

#### See Example Test Cases for each language

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, Chef wants to find the smallest positive integer M such that the bitwise XOR of M and M+1 is N. If no such M exists output -1.

-----Input-----
The first line of input contain an integer T denoting the number of test cases. Each of the following T lines contains an integer N for that test case.

-----Output-----
For each test case, output a single line containing the number M or -1 as described above.

-----Constraints-----
- 1 ≤ T ≤ 5000
- 1 ≤ N ≤ 230

-----Example-----
Input:
1
3

Output:
1

-----Explanation-----First Example :  M desired in the problem would be 1. As bitwise XOR of 1 and 2 is equal to 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Momiji has got a rooted tree, consisting of n nodes. The tree nodes are numbered by integers from 1 to n. The root has number 1. Momiji decided to play a game on this tree.

The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by v) and removes all the subtree nodes with the root in node v from the tree. Node v gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number 1.

Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of nodes in the tree. The next n - 1 lines contain the tree edges. The i-th line contains integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — the numbers of the nodes that are connected by the i-th edge.

It is guaranteed that the given graph is a tree.


-----Output-----

Print a single real number — the expectation of the number of steps in the described game.

The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.


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

Output
1.50000000000000000000

Input
3
1 2
1 3

Output
2.00000000000000000000



-----Note-----

In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are: 1 × (1 / 2) + 2 × (1 / 2) = 1.5

In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are: 1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2

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

given f(0)=0 , f(1)=1 , f(2)=1 

f(n) = f(n-2) + f(n-3) + n*2 

Input

First line denotes the number of test cases T

T lines follow each containing a number n

Output

Output T lines, As the number can be very large, output the answer modulo 10000003.

Constraints

1< t ≤1000

1< n ≤10^9

SAMPLE INPUT
3
2
6
17

SAMPLE OUTPUT
1
29
1067

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ram loves those numbers which are square of any number. To check his love for these numbers one day Sham gives him two numbers a and p where p  is prime number and asks him if it is possible to find any square number which gives modulo a when divided by p. This task is difficult for Ram so he asks for your help. Help Ram to find whether such number exists or not.

INPUT
First line contains number of test cases T. Eash test case contains two numbers a and a prime number p.
OUTPUT
Print "YES" if any n exists such that (n*n)%p=a else print "NO"(without quotes).
NOTE : n must be greater than 0.
Constraints
1 ≤ T ≤ 1000
1 ≤ a ≤ 1000000
3 ≤ p ≤ 1000000 (p is prime number)

SAMPLE INPUT
2
4 3
7 5

SAMPLE OUTPUT
YES
NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You get to work and turn on the computer. You start coding and give little thought to the RAM role in the whole process. In this problem your task is to solve one of the problems you encounter in your computer routine.

We'll consider the RAM as a sequence of cells that can contain data. Some cells already contain some data, some are empty. The empty cells form the so-called memory clusters. Thus, a memory cluster is a sequence of some consecutive empty memory cells. 

You have exactly *n* memory clusters, the *i*-th cluster consists of *a**i* cells. You need to find memory for *m* arrays in your program. The *j*-th array takes 2*b**j* consecutive memory cells. There possibly isn't enough memory for all *m* arrays, so your task is to determine what maximum number of arrays can be located in the available memory clusters. Of course, the arrays cannot be divided between the memory clusters. Also, no cell can belong to two arrays.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=106). The next line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109). The next line contains *m* integers *b*1,<=*b*2,<=...,<=*b**m* (1<=≤<=2*b**i*<=≤<=109).

Output Specification:
Print a single integer — the answer to the problem.

Demo Input:
['5 3\n8 4 3 2 2\n3 2 2\n', '10 6\n1 1 1 1 1 1 1 1 1 1\n0 0 0 0 0 0\n']

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

Note:
In the first example you are given memory clusters with sizes 8, 4, 3, 2, 2 and arrays with sizes 8, 4, 4. There are few ways to obtain an answer equals 2: you can locate array with size 8 to the cluster with size 8, and one of the arrays with size 4 to the cluster with size 4. Another way is to locate two arrays with size 4 to the one cluster with size 8.

In the second example you are given 10 memory clusters with size 1 and 6 arrays with size 1. You can choose any 6 clusters and locate all given arrays to them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Yet Another Array Queries Problem

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array *a* of size *n*, and *q* queries to it. There are queries of two types: 
 -  1 *l**i* *r**i* — perform a cyclic shift of the segment [*l**i*,<=*r**i*] to the right. That is, for every *x* such that *l**i*<=≤<=*x*<=&lt;<=*r**i* new value of *a**x*<=+<=1 becomes equal to old value of *a**x*, and new value of *a**l**i* becomes equal to old value of *a**r**i*; -  2 *l**i* *r**i* — reverse the segment [*l**i*,<=*r**i*]. 
There are *m* important indices in the array *b*1, *b*2, ..., *b**m*. For each *i* such that 1<=≤<=*i*<=≤<=*m* you have to output the number that will have index *b**i* in the array after all queries are performed.

Input Specification:
The first line contains three integer numbers *n*, *q* and *m* (1<=≤<=*n*,<=*q*<=≤<=2·105, 1<=≤<=*m*<=≤<=100). 

The second line contains *n* integer numbers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=109). 

Then *q* lines follow. *i*-th of them contains three integer numbers *t**i*, *l**i*, *r**i*, where *t**i* is the type of *i*-th query, and [*l**i*,<=*r**i*] is the segment where this query is performed (1<=≤<=*t**i*<=≤<=2, 1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*). 

The last line contains *m* integer numbers *b*1, *b*2, ..., *b**m* (1<=≤<=*b**i*<=≤<=*n*) — important indices of the array.

Output Specification:
Print *m* numbers, *i*-th of which is equal to the number at index *b**i* after all queries are done.

Demo Input:
['6 3 5\n1 2 3 4 5 6\n2 1 3\n2 3 6\n1 1 6\n2 2 1 5 3\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Master Shifu is training Po to become The Dragon Warrior and as a final assignment he must obtain maximum deliciousness from dumplings. There are  $N$ plates of dumplings in front of him with deliciousness $A_1, A_2, \ldots, A_N$, Po can choose any number of continuous plates of  dumplings. The total deliciousness is the sum of deliciousness of all the  chosen dumplings.
What is the minimum number of plates he must choose so that total deliciousness is maximum possible?
Note: Po must choose atleast one plate.

-----Input:-----
- The first line of the input contains a single 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$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output:-----
For each test case, print a single line containing one integer.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 2 \cdot 10^5$
- $0 \le A_i \le 10^9$

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

-----Sample Output:-----
4
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of n integers and a positive number k. We are allowed to take any k integers from the given array. The task is to find the minimum possible value of the difference between maximum and minimum of k numbers.
 
Example 1:
Input:
N=7
K=3
arr[] = {10, 100, 300, 200, 1000, 20, 30}
Output:
20
Explanation:
20 is the minimum possible difference 
between any maximum and minimum of any 
k numbers.Given k = 3, we get the result 
20 by selecting integers {10, 20, 30}.
max(10, 20, 30) - min(10, 20, 30) = 30 - 10 
= 20.
Example 2:
Input:
N=2
K=2
arr[] = { 1,1 }
Output:
0
Explanation:
max({1,1}) - min({1,1}) = 1 - 1 = 0
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function minDiff() that takes array arr, integer N and integer K as parameters and return the value of friendliness for the given array.
 
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(1).
 
Constraints:
2 ≤ N ≤ 10^{5}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pavel loves grid mazes. A grid maze is an *n*<=×<=*m* rectangle maze where each cell is either empty, or is a wall. You can go from one cell to another only if both cells are empty and have a common side.

Pavel drew a grid maze with all empty cells forming a connected area. That is, you can go from any empty cell to any other one. Pavel doesn't like it when his maze has too little walls. He wants to turn exactly *k* empty cells into walls so that all the remaining cells still formed a connected area. Help him.

Input Specification:
The first line contains three integers *n*, *m*, *k* (1<=≤<=*n*,<=*m*<=≤<=500, 0<=≤<=*k*<=&lt;<=*s*), where *n* and *m* are the maze's height and width, correspondingly, *k* is the number of walls Pavel wants to add and letter *s* represents the number of empty cells in the original maze.

Each of the next *n* lines contains *m* characters. They describe the original maze. If a character on a line equals ".", then the corresponding cell is empty and if the character equals "#", then the cell is a wall.

Output Specification:
Print *n* lines containing *m* characters each: the new maze that fits Pavel's requirements. Mark the empty cells that you transformed into walls as "X", the other cells must be left without changes (that is, "." and "#").

It is guaranteed that a solution exists. If there are multiple solutions you can output any of them.

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

Demo Output:
['#.X#\nX.#.\n#...\n', '#XXX\n#X#.\nX#..\n...#\n.#.#\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The characters of Chima need your help. Their weapons got mixed up! They need you to write a program that accepts the name of a character in Chima then tells which weapon he/she owns.

For example: for the character `"Laval"` your program should return the solution `"Laval-Shado Valious"`

You must complete the following character-weapon pairs:

* Laval-Shado Valious, 
* Cragger-Vengdualize, 
* Lagravis-Blazeprowlor, 
* Crominus-Grandorius, 
* Tormak-Tygafyre, 
* LiElla-Roarburn. 
    
Return `"Not a character"` for invalid inputs.

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

Satake doesn't like being bent.
For example, I don't like pencils, chopsticks, and bent-shaped houses, and I don't like taking actions such as turning right or left.

By the way, Satake who lives on the XY plane is $ N $ shops $ (X_ {1}, Y_ {1}), (X_ {2}, Y_ {2}), \ ldots, (X_ {N} , Y_ {N}) I was asked to shop for $. Depart from the house at coordinates $ (0, 0) $ in the direction of $ (1, 0) $, shop at all stores, and then return home. You can go around the shops in any order. As a user, Satake can perform any of the following actions as many times as you like.

1. Go as much as you like in the direction you are facing
2. When the coordinates are the same as the shop or house, rotate clockwise or counterclockwise by the desired angle on the spot.
3. When the coordinates are the same as the store, shop while maintaining the coordinates and the direction in which they are facing.



As I said earlier, Satake doesn't like to bend. To prepare your mind, find the minimum sum of the angles that Satake will rotate in Action 2. As an example, if you rotate $ 90 ^ {\ circ} $ clockwise and then $ 90 ^ {\ circ} $ counterclockwise, the sum of the angles will be $ 180 ^ {\ circ} $.

Constraints

The input meets the following conditions:

* $ 2 \ le N \ le 8 $
* $ -1000 \ le X_ {i}, Y_ {i} \ le 1000 \ quad (1 \ le i \ le N) $
* $ (X_ {i}, Y_ {i}) \ ne (0, 0) \ quad (1 \ le i \ le N) $
* $ (X_ {i}, Y_ {i}) \ ne (X_ {j}, Y_ {j}) \ quad (i \ ne j) $
* All inputs are integers

Input

The input is given in the following format:


$ N $
$ X_ {1} $ $ Y_ {1} $
$ \ vdots $
$ X_ {N} $ $ Y_ {N} $


The input consists of $ N + 1 $ lines.
The $ 1 $ line is given $ N $, which represents the number of stores to shop.
The $ N $ line starting from the $ 2 $ line is given the coordinates $ X_ {i}, Y_ {i} $ of the store where you shop, separated by blanks.

Output

Please output the minimum value of the sum of the angles that Satake rotates in degrees. However, the correct answer is given only when the absolute error from the assumed solution is $ 10 ^ {-4} $ or less.

Examples

Input

2
0 1
0 -1


Output

450.00000000


Input

3
1 0
0 1
-2 -1


Output

386.565051

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Legend has it that, after being defeated in Waterloo, Napoleon Bonaparte, in retrospect of his days of glory, talked to himself "Able was I ere I saw Elba." Although, it is quite doubtful that he should have said this in English, this phrase is widely known as a typical palindrome.

A palindrome is a symmetric character sequence that looks the same when read backwards, right to left. In the above Napoleon's grumble, white spaces appear at the same positions when read backwards. This is not a required condition for a palindrome. The following, ignoring spaces and punctuation marks, are known as the first conversation and the first palindromes by human beings.


"Madam, I'm Adam."
"Eve."
(by Mark Twain)


Write a program that finds palindromes in input lines.



Input

A multi-line text is given as the input. The input ends at the end of the file.

There are at most 100 lines in the input. Each line has less than 1,024 Roman alphabet characters.

Output

Corresponding to each input line, a line consisting of all the character sequences that are palindromes in the input line should be output. However, trivial palindromes consisting of only one or two characters should not be reported.

On finding palindromes, any characters in the input except Roman alphabets, such as punctuation characters, digits, space, and tabs, should be ignored. Characters that differ only in their cases should be looked upon as the same character. Whether or not the character sequences represent a proper English word or sentence does not matter.

Palindromes should be reported all in uppercase characters. When two or more palindromes are reported, they should be separated by a space character. You may report palindromes in any order.

If two or more occurrences of the same palindromes are found in the same input line, report only once. When a palindrome overlaps with another, even when one is completely included in the other, both should be reported. However, palindromes appearing in the center of another palindrome, whether or not they also appear elsewhere, should not be reported. For example, for an input line of "AAAAAA", two palindromes "AAAAAA" and "AAAAA" should be output, but not "AAAA" nor "AAA". For "AABCAAAAAA", the output remains the same.

One line should be output corresponding to one input line. If an input line does not contain any palindromes, an empty line should be output.

Example

Input

As the first man said to the
first woman:
"Madam, I'm Adam."
She responded:
"Eve."


Output

TOT

MADAMIMADAM MADAM
ERE DED
EVE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of distinct integers, write a program to find if there exist two pairs (a, b) and (c, d) such that ab = cd, where a, b, c and d are distinct elements. If such pairs exists then print 1 else -1.
 
Example 1:
Input:
N=7
arr[] = {3, 4, 7, 1, 2, 9, 8} 
Output: 1
Explanation:
Product of 4 and 2 is 8 and also,
the product of 1 and 8 is 8.  
 
Example 2:
Input:
N=6
arr[] = {1, 6, 3, 9, 2, 10} 
Output: 1
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function findPairs() that takes array arr and n  as parameters and return 1 if any such pair is found otherwise return -1. 
 
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(N^{2}).
 
Constraints:
1 ≤ N ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an $n \times m$ checkerboard. On each cell of the checkerboard, place a positive integer. The values in each column of the checkerboard must be in strictly increasing order from top to bottom, and the values in each row of the checkerboard must be in strictly increasing order from left to right.

1

2

3

4

3

4

5

6

5

6

7

8

7

8

9

10

A Magic Checkerboard has an additional constraint. The cells that share only a corner must have numbers of different parity (Even vs Odd). Note that the following checkboard is invalid, because 2 and 4 share only a corner and have the same parity:

1

2

4

6

The first $4 \times 4$ example is a valid Magic Checkboard. Given a partially filled magic checkboard, can you fill the remaining locations on the checkboard, so that the sum of all values is as small as possible?

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input starts with a line with two space-separated integers $n$ and $m$ ($1 \le n, m \le 2000$), representing the number of rows ($n$) and the number of columns ($m$) of the checkerboard. Each of the next $n$ lines will contain $m$ space-separated integers $c$ ($0 \le c \le 2000$), representing the contents of the checkerboard. Zero is used for cells without numbers that you must fill in. You may use any positive integers to fill in the cells without numbers, so long as you form a valid Magic Checkerboard. You are not limited to numbers $\le 2000$, and the numbers are not required to be unique.

-----Output-----
Output a single integer representing the minimum sum possible by replacing the 0 cells with positive integers to form a valid Magic Checkerboard. Output $-1$ if it is not possible to replace the 0 cells to meet the constraints of a Magic Checkerboard.

-----Examples-----
Sample Input 1:
4 4
1 2 3 0
0 0 5 6
0 0 7 8
7 0 0 10
Sample Output 1:
88

Sample Input 2:
4 4
1 2 3 0
0 0 5 6
0 4 7 8
7 0 0 10
Sample Output 2:
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two square Matrices A[][] and B[][]. Your task is to complete the function multiply which stores the multiplied matrices in a new matrix C[][].
 
Example 1:
Input: 
N = 2
A[][] = {{7, 8}, {2 , 9}}
B[][] = {{14, 5}, {5, 18}}
Output: 
C[][] = {{138, 179}, {73, 172}}
 
Example 2:
Input: 
N = 2
A[][] = {{17, 4}, {17 , 16}}
B[][] = {{9, 2}, {7, 1}}
Output: 
C[][] = {{181, 38}, {265, 50}}
Constraints:
1 <=T<= 100
1 <= N <= 20

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