vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem :

The super aliens aka (MiDsEmS) have taken over the earth and the only people who can save earth are a species genetically engineered by humans called (MuGStUd) . You are also a part of this genetically perfect human race . But defeat is near with the matrix of life (DCPlUsPlUs) locked behind a BACK DOOR. The only way to get through the door is to provide it with the cube of life. 

The cube of life (A is the name given to the cube) is a very special cube of size N with numbers present at each 1 X 1 X 1 cell .

But MiDsEmS have distorted the cube in a very cruel way and in the place of the cube have put up a fake (B is the name given to the distorted cube). What they did is described bellow-

At any position say (i,j,k) in the distorted cube they stored the sum of all elements in the cuboid formed with (i,j,k) and (0,0,0) of the cube of life as the opposite vertices.

Now your task as the most elite hacker of MugStUd is to find the orignal cube of life and give it to unlock the back door.

But time is not with you and you have to be very quick.

So given the distorted matrix, you have to find the original cube of life.

In conclusion you are given a cube B such that at every point (i,j,k) of the cube B is described as below-

   for(c=0;c ≤ i;c++)
     for(c1=0;c1 ≤ j;c1++)
        for(c2=0;c2 ≤ k;c2++)
           B(i,j,k)=B(i,j,k)+A(c,c1,c2);

BOTH A and B are 0 indexed.

Input :

t-number of test cases. Each test case is described below.

The first line of each test case will have N.

Then next N^2 lines follow each containing N numbers.

The first line contains the numbers B(0,0,0,), B (0,0,1)... B(0,0,N-1). 

The second line will have B(0,1,0), B(0,1,1).... B(0,1,N-1)......

The N th line will have B(0,N-1,0), B(0,N-1,1).... B(0,N-1,N-1)

The (N+1) th line will have B(1,0,0), B(1,0,1).... B(1,0,N-1).... and so on.

Output :

Print the cube of life A in the same format as the input

The answer to every test case must be answered in a new line.

Constraints :

1 ≤ t ≤ 100

1 ≤ N ≤ 50

0 ≤ B(i , j , k) ≤ 10^6 

Probem Setter : Sandeep

Problem Tester : Shreyans

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
1
2
1 2
3 4
5 6
7 8

SAMPLE OUTPUT
1 1
2 0
4 0
0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given a permutation sequence a1, a2, ..., an of numbers from 1 to n. Let's assume that in one second, we can choose some disjoint pairs (u1, v1), (u2, v2), ..., (uk, vk) and swap all aui and avi for every i at the same time (1 ≤ ui < vi ≤ n). The pairs are disjoint if every ui and vj are different from each other.

We want to sort the sequence completely in increasing order as fast as possible. Given the initial permutation, calculate the number of ways to achieve this. Two ways are different if and only if there is a time t, such that the set of pairs used for swapping at that time are different as sets (so ordering of pairs doesn't matter). If the given permutation is already sorted, it takes no time to sort, so the number of ways to sort it is 1.

To make the problem more interesting, we have k holes inside the permutation. So exactly k numbers of a1, a2, ..., an are not yet determined. For every possibility of filling the holes, calculate the number of ways, and print the total sum of these values modulo 1000000007 (109 + 7).

Input

The first line contains two integers n (1 ≤ n ≤ 105) and k (0 ≤ k ≤ 12). The second line contains the permutation sequence a1, ..., an (0 ≤ ai ≤ n). If a number is not yet determined, it is denoted as 0. There are exactly k zeroes. All the numbers ai that aren't equal to zero are distinct.

Output

Print the total sum of the number of ways modulo 1000000007 (109 + 7).

Examples

Input

5 0
1 5 2 4 3


Output

6


Input

5 2
1 0 2 4 0


Output

7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number S in the form of string, the task is to check whether the sum of digits at odd places is equal to the sum of digits at even places or not.
Example 1:
Input: S = "132"
Output: 1
Explanation: The sum of digits at odd 
places is 1+2=3. Similarly the sum of 
digits at even places is 3. Since they 
are equal,the answer is 1.
Example 2:
Input: S = "123"
Output: 0
Explanation: The sum of digits at odd 
places is 1+3=4. The sum of digits at 
even places is 2. Since,the sums are 
not equal,Thus answer is 0.
Your Task:
You don't need to read input or print anything.Your task is to complete the function oddAndEven() which takes an integer S (in the form of string) as input parameter and returns 1 if the sum of digits at odd places is equal to the sum of digits at even places.Otherwise, it returns 0.
Expected Time Complexity:O(|S|)
Expected Auxillary Space:O(1)
Constraints:
1≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N. Among the integers between 1 and N (inclusive), how many Shichi-Go-San numbers (literally "Seven-Five-Three numbers") are there?
Here, a Shichi-Go-San number is a positive integer that satisfies the following condition:
 - When the number is written in base ten, each of the digits 7, 5 and 3 appears at least once, and the other digits never appear.

-----Constraints-----
 - 1 \leq N < 10^9
 - N is an integer.

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

-----Output-----
Print the number of the Shichi-Go-San numbers between 1 and N (inclusive).

-----Sample Input-----
575

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

There are four Shichi-Go-San numbers not greater than 575: 357, 375, 537 and 573.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 You are given a string `s`. Let's call its substring a group, if all letters in it are adjacent and the same(such as `"aa","bbb","cccc"`..). Let's call the substiring with 2 or more adjacent group a big group(such as `"aabb","bbccc"`...).
 
 Your task is to count the number of `big groups` in the given string.

# Example

 For `s = "ccccoodeffffiiighhhhhhhhhhttttttts"`, the result should be `3`.
 ```
The groups are "cccc", "oo", "ffff", "iii", "hhhhhhhhhh", "ttttttt"
The big groups are "ccccoo", "ffffiii", "hhhhhhhhhhttttttt", 
3 substrings altogether.```

 For `s = "gztxxxxxggggggggggggsssssssbbbbbeeeeeeehhhmmmmmmmitttttttlllllhkppppp"`, the result should be `2`.
 ```
The big groups are :
"xxxxxggggggggggggsssssssbbbbbeeeeeeehhhmmmmmmm"
and 
"tttttttlllll" ```

 For `s = "soooooldieeeeeer"`, the result should be `0`.
 
 There is no `big group` exist.
 
# Input/Output


 - `[input]` string `s`

  A string of lowercase Latin letters.


 - `[output]` an integer

  The number of big groups.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valya and Tolya are an ideal pair, but they quarrel sometimes. Recently, Valya took offense at her boyfriend because he came to her in t-shirt with lettering that differs from lettering on her pullover. Now she doesn't want to see him and Tolya is seating at his room and crying at her photos all day long.

This story could be very sad but fairy godmother (Tolya's grandmother) decided to help them and restore their relationship. She secretly took Tolya's t-shirt and Valya's pullover and wants to make the letterings on them same. In order to do this, for one unit of mana she can buy a spell that can change some letters on the clothes. Your task is calculate the minimum amount of mana that Tolya's grandmother should spend to rescue love of Tolya and Valya.

More formally, letterings on Tolya's t-shirt and Valya's pullover are two strings with same length n consisting only of lowercase English letters. Using one unit of mana, grandmother can buy a spell of form (c_1, c_2) (where c_1 and c_2 are some lowercase English letters), which can arbitrary number of times transform a single letter c_1 to c_2 and vise-versa on both Tolya's t-shirt and Valya's pullover. You should find the minimum amount of mana that grandmother should spend to buy a set of spells that can make the letterings equal. In addition you should output the required set of spells. 


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the length of the letterings.

The second line contains a string with length n, consisting of lowercase English letters — the lettering on Valya's pullover.

The third line contains the lettering on Tolya's t-shirt in the same format.


-----Output-----

In the first line output a single integer — the minimum amount of mana t required for rescuing love of Valya and Tolya.

In the next t lines output pairs of space-separated lowercase English letters — spells that Tolya's grandmother should buy. Spells and letters in spells can be printed in any order.

If there are many optimal answers, output any.


-----Examples-----
Input
3
abb
dad

Output
2
a d
b a
Input
8
drpepper
cocacola

Output
7
l e
e d
d c
c p
p o
o r
r a



-----Note-----

In first example it's enough to buy two spells: ('a','d') and ('b','a'). Then first letters will coincide when we will replace letter 'a' with 'd'. Second letters will coincide when we will replace 'b' with 'a'. Third letters will coincide when we will at first replace 'b' with 'a' and then 'a' with 'd'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the "computer expert" of a local Athletic Association (C.A.A.).
Many teams of runners come to compete. Each time you get a string of 
all race results of every team who has run.
For example here is a string showing the individual results of a team of 5 runners:

` "01|15|59, 1|47|6, 01|17|20, 1|32|34, 2|3|17" `

Each part of the string is of the form: ` h|m|s `
where h, m, s (h for hour, m for minutes, s for seconds) are positive or null integer (represented as strings) with one or two digits.
There are no traps in this format.

To compare the results of the teams you are asked for giving
three statistics; **range, average and median**.

`Range` : difference between the lowest and highest values. 
In {4, 6, 9, 3, 7} the lowest value is 3, and the highest is 9, 
so the range is 9 − 3 = 6.

`Mean or Average` : To calculate mean, add together all of the numbers 
in a set and then divide the sum by the total count of numbers.

`Median` : In statistics, the median is the number separating the higher half 
of a data sample from the lower half. 
The median of a finite list of numbers can be found by arranging all 
the observations from lowest value to highest value and picking the middle one 
(e.g., the median of {3, 3, 5, 9, 11} is 5) when there is an odd number of observations. 
If there is an even number of observations, then there is no single middle value; 
the median is then defined to be the mean of the two middle values
(the median of {3, 5, 6, 9} is (5 + 6) / 2 = 5.5).

Your task is to return a string giving these 3 values.  For the example given above,
the string result will be

`"Range: 00|47|18 Average: 01|35|15 Median: 01|32|34"`

of the form:

`"Range: hh|mm|ss Average: hh|mm|ss Median: hh|mm|ss"`

where hh, mm, ss are integers (represented by strings) with *each 2 digits*.

*Remarks*: 

1. if a result in seconds is ab.xy... it will be given **truncated** as ab.

2. if the given string is "" you will return ""

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a sequence of integers A_1, A_2, ..., A_N.
If its elements are pairwise distinct, print YES; otherwise, print NO.

-----Constraints-----
 - 2 ≤ N ≤ 200000
 - 1 ≤ A_i ≤ 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 ... A_N

-----Output-----
If the elements of the sequence are pairwise distinct, print YES; otherwise, print NO.

-----Sample Input-----
5
2 6 1 4 5

-----Sample Output-----
YES

The elements are pairwise distinct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a simple undirected graph with N vertices and M edges. The i-th edge connects Vertex c_i and Vertex d_i.
Initially, Vertex i has the value a_i written on it. You want to change the values on Vertex 1, \ldots, Vertex N to b_1, \cdots, b_N, respectively, by doing the operation below zero or more times.
 - Choose an edge, and let Vertex x and Vertex y be the vertices connected by that edge. Choose one of the following and do it:
 - Decrease the value a_x by 1, and increase the value a_y by 1.
 - Increase the value a_x by 1, and decrease the value a_y by 1.
Determine whether it is possible to achieve the objective by properly doing the operation.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 0 \leq M \leq 2 \times 10^5
 - -10^9 \leq a_i,b_i \leq 10^9
 - 1 \leq c_i,d_i \leq N
 - The given graph is simple, that is, has no self-loops and no multi-edges.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1 \cdots a_N
b_1 \cdots b_N
c_1 d_1
\vdots
c_M d_M

-----Output-----
Print Yes if it is possible to achieve the objective by properly doing the operation, and No otherwise.

-----Sample Input-----
3 2
1 2 3
2 2 2
1 2
2 3

-----Sample Output-----
Yes

You can achieve the objective by, for example, doing the operation as follows:
 - In the first operation, choose the edge connecting Vertex 1 and 2. Then, increase a_1 by 1 and decrease a_2 by 1.
 - In the second operation, choose the edge connecting Vertex 2 and 3. Then, increase a_2 by 1 and decrease a_3 by 1.
This sequence of operations makes a_1=2, a_2=2, and a_3=2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has n burles. One bottle of Ber-Cola costs a burles and one Bars bar costs b burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number of Bars bars.

Find out if it's possible to buy some amount of bottles of Ber-Cola and Bars bars and spend exactly n burles.

In other words, you should find two non-negative integers x and y such that Vasya can buy x bottles of Ber-Cola and y Bars bars and x·a + y·b = n or tell that it's impossible.

Input

First line contains single integer n (1 ≤ n ≤ 10 000 000) — amount of money, that Vasya has.

Second line contains single integer a (1 ≤ a ≤ 10 000 000) — cost of one bottle of Ber-Cola.

Third line contains single integer b (1 ≤ b ≤ 10 000 000) — cost of one Bars bar.

Output

If Vasya can't buy Bars and Ber-Cola in such a way to spend exactly n burles print «NO» (without quotes).

Otherwise in first line print «YES» (without quotes). In second line print two non-negative integers x and y — number of bottles of Ber-Cola and number of Bars bars Vasya should buy in order to spend exactly n burles, i.e. x·a + y·b = n. If there are multiple answers print any of them.

Any of numbers x and y can be equal 0.

Examples

Input

7
2
3


Output

YES
2 1


Input

100
25
10


Output

YES
0 10


Input

15
4
8


Output

NO


Input

9960594
2551
2557


Output

YES
1951 1949

Note

In first example Vasya can buy two bottles of Ber-Cola and one Bars bar. He will spend exactly 2·2 + 1·3 = 7 burles.

In second example Vasya can spend exactly n burles multiple ways: 

  * buy two bottles of Ber-Cola and five Bars bars; 
  * buy four bottles of Ber-Cola and don't buy Bars bars; 
  * don't buy Ber-Cola and buy 10 Bars bars. 



In third example it's impossible to but Ber-Cola and Bars bars in order to spend exactly n burles.

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

Great Demon King Megumi wants to defeat the $ N $ hero who lives on the ground.
Megumi can cast explosion magic up to $ M $ times.
Explosion magic is magic that extinguishes heroes who exist within a radius of $ r $ around arbitrary coordinates.
The hero is very thin, so you don't have to consider the size.
All $ M $ explosion spells shall be cast with the same radius.
I decided to use the magic of the minimum radius necessary to annihilate the hero.
Minimize the size of the explosive magic radius.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq M \ leq N \ leq 14 $
* $ 0 \ leq x_i $, $ y_i \ leq 10 ^ 5 $

Input


$ N $ $ M $
$ x_1 $ $ y_1 $
...
$ x_N $ $ y_N $


The input is given in the following format.
The number of heroes $ N $ and the number of explosions to cast $ M $ are given as integers on the first line.
From the second line onward, the coordinates $ x_i $ $, $ $ y_i $ of each hero $ i $ are given as integers.

Output

Output the minimum value of the explosive magic radius as a real number.
Must not contain absolute error greater than $ 10 ^ {-3} $.

Examples

Input

5 2
0 0
5 5
10 10
100 100
200 200


Output

70.710678118755


Input

10 5
321 675
4312 6534
312 532
412 6543
21 43
654 321
543 0
32 5
41 76
5 1


Output

169.824909833728


Input

14 3
312 342
4893 432
321 4
389 4
23 543
0 0
1 1
2 2
432 12
435 32
1 5
2 10
100 100
20 50


Output

218.087711712613


Input

5 2
0 0
0 0
0 0
0 0
0 0


Output

0.000000000001

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose n1, n2, . . . . , nk are positive integers that are pairwise coprime. Then, for any given sequence of integers a1, a2, . . . . , ak, there exists an integer x solving the following system of simultaneous congruences. 

x = a1 mod(n1)

x = a2 mod(n2)

.

.

.

x = ak mod(nk)

Furthermore, all solutions x of this system are congruent modulo the product, N=n1,n2 . . . . nk.
Your task is to write a program to solve a system of linear congruences and find pth such special number.

Input

First line contains t (number of test cases).
Second line contains 2 space seperated integers k and p (k being the number of integers)
Third line contains k space seperated integers n1, n2 . . . . nk.
Fourth line contains k space seperated integers a1, a2 . . . . ak.

Output

You need to print the pth such number which satisfies the above condition. Since the answer can be too large, print the answer % 1000000007

Constraints

1 ≤ t ≤ 100
1 ≤ k ≤ 10^6
1 ≤ p ≤ 100
1 ≤ ni, ai ≤ 10^5

SAMPLE INPUT
1
3 1
3 5 7
2 3 2

SAMPLE OUTPUT
23

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ZS the Coder loves mazes. Your job is to create one so that he can play with it. A maze consists of n × m rooms, and the rooms are arranged in n rows (numbered from the top to the bottom starting from 1) and m columns (numbered from the left to the right starting from 1). The room in the i-th row and j-th column is denoted by (i, j). A player starts in the room (1, 1) and wants to reach the room (n, m).

Each room has four doors (except for ones at the maze border), one on each of its walls, and two adjacent by the wall rooms shares the same door. Some of the doors are locked, which means it is impossible to pass through the door. For example, if the door connecting (i, j) and (i, j + 1) is locked, then we can't go from (i, j) to (i, j + 1). Also, one can only travel between the rooms downwards (from the room (i, j) to the room (i + 1, j)) or rightwards (from the room (i, j) to the room (i, j + 1)) provided the corresponding door is not locked.

<image> This image represents a maze with some doors locked. The colored arrows denotes all the possible paths while a red cross denotes a locked door.

ZS the Coder considers a maze to have difficulty x if there is exactly x ways of travelling from the room (1, 1) to the room (n, m). Two ways are considered different if they differ by the sequence of rooms visited while travelling.

Your task is to create a maze such that its difficulty is exactly equal to T. In addition, ZS the Coder doesn't like large mazes, so the size of the maze and the number of locked doors are limited. Sounds simple enough, right?

Input

The first and only line of the input contains a single integer T (1 ≤ T ≤ 1018), the difficulty of the required maze.

Output

The first line should contain two integers n and m (1 ≤ n, m ≤ 50) — the number of rows and columns of the maze respectively.

The next line should contain a single integer k (0 ≤ k ≤ 300) — the number of locked doors in the maze.

Then, k lines describing locked doors should follow. Each of them should contain four integers, x1, y1, x2, y2. This means that the door connecting room (x1, y1) and room (x2, y2) is locked. Note that room (x2, y2) should be adjacent either to the right or to the bottom of (x1, y1), i.e. x2 + y2 should be equal to x1 + y1 + 1. There should not be a locked door that appears twice in the list.

It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

Examples

Input

3


Output

3 2
0


Input

4


Output

4 3
3
1 2 2 2
3 2 3 3
1 3 2 3

Note

Here are how the sample input and output looks like. The colored arrows denotes all the possible paths while a red cross denotes a locked door.

In the first sample case:

<image>

In the second sample case:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
David has several containers, each with a number of balls in it.  He has just enough containers to sort each type of ball he has into its own container.  David wants to sort the balls using his sort method.

David wants to perform some number of swap operations such that:

Each container contains only balls of the same type.
No two balls of the same type are located in different containers.

Example   

$containers=[[1,4],[2,3]]$   

David has $n=2$ containers and $2$ different types of balls, both of which are numbered from $\mbox{0}$ to $n-1=1$. The distribution of ball types per container are shown in the following diagram.   

In a single operation, David can swap two balls located in different containers.

The diagram below depicts a single swap operation:

In this case, there is no way to have all green balls in one container and all red in the other using only swap operations.  Return Impossible.  

You must perform $\textit{q}$ queries where each query is in the form of a matrix, $\mbox{M}$. For each query, print Possible on a new line if David can satisfy the conditions above for the given matrix.  Otherwise, print Impossible.  

Function Description  

Complete the organizingContainers function in the editor below.   

organizingContainers has the following parameter(s):  

int containter[n][m]: a two dimensional array of integers that represent the number of balls of each color in each container  

Returns   

string:  either Possible or Impossible     

Input Format

The first line contains an integer $\textit{q}$, the number of queries.  

Each of the next $\textit{q}$ sets of lines is as follows:  

The first line contains an integer $n$, the number of containers (rows) and ball types (columns).        
Each of the next $n$ lines contains $n$ space-separated integers describing row $containers[i]$.

Constraints

$1\leq q\leq10$  
$1\leq n\leq100$  
$0\leq\textit{containers}[i][j]\leq10^9$

Scoring

For $33\%$ of score, $1\leq n\leq10$.  
For $\textbf{100\%}$ of score, $1\leq n\leq100$.

Output Format

For each query, print Possible on a new line if David can satisfy the conditions above for the given matrix.  Otherwise, print Impossible.

Sample Input 0
2
2
1 1
1 1
2
0 2
1 1

Sample Output 0
Possible
Impossible

Explanation 0

We perform the following $q=2$ queries:

The diagram below depicts one possible way to satisfy David's requirements for the first query:
 
Thus, we print Possible on a new line.
The diagram below depicts the matrix for the second query:
 
No matter how many times we swap balls of type $\boldsymbol{t_0}$ and $\boldsymbol{t_1}$ between the two containers, we'll never end up with one container only containing type $\boldsymbol{t_0}$ and the other container only containing type $\boldsymbol{t_1}$. Thus, we print Impossible on a new line.

Sample Input 1
2
3
1 3 1
2 1 2
3 3 3
3
0 2 1
1 1 1
2 0 0

Sample Output 1
Impossible
Possible

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