vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array of unique numbers. The numbers represent points. The higher the number the higher the points.  
In the array [1,3,2] 3 is the highest point value so it gets 1st place. 2 is the second highest so it gets second place. 1 is the 3rd highest so it gets 3rd place. 

Your task is to return an array giving each number its rank in the array.  
input // [1,3,2] 
output // [3,1,2]

```rankings([1,2,3,4,5]) // [5,4,3,2,1]``` 
```rankings([3,4,1,2,5])//  [3,2,5,4,1]``` 
```rankings([10,20,40,50,30]) //  [5, 4, 2, 1, 3]``` 
```rankings([1, 10]) //   [2, 1]``` 
```rankings([22, 33, 18, 9, 110, 4, 1, 88, 6, 50]) //```
```[5, 4, 6, 7, 1, 9, 10, 2, 8, 3]```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the country there are n cities and m bidirectional roads between them. Each city has an army. Army of the i-th city consists of ai soldiers. Now soldiers roam. After roaming each soldier has to either stay in his city or to go to the one of neighboring cities by at moving along at most one road.

Check if is it possible that after roaming there will be exactly bi soldiers in the i-th city.

Input

First line of input consists of two integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 200).

Next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 100).

Next line contains n integers b1, b2, ..., bn (0 ≤ bi ≤ 100).

Then m lines follow, each of them consists of two integers p and q (1 ≤ p, q ≤ n, p ≠ q) denoting that there is an undirected road between cities p and q. 

It is guaranteed that there is at most one road between each pair of cities.

Output

If the conditions can not be met output single word "NO".

Otherwise output word "YES" and then n lines, each of them consisting of n integers. Number in the i-th line in the j-th column should denote how many soldiers should road from city i to city j (if i ≠ j) or how many soldiers should stay in city i (if i = j).

If there are several possible answers you may output any of them.

Examples

Input

4 4
1 2 6 3
3 5 3 1
1 2
2 3
3 4
4 2


Output

YES
1 0 0 0 
2 0 0 0 
0 5 1 0 
0 0 2 1 


Input

2 0
1 2
2 1


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced participant, she guessed that she should match trees to some sequences and then compare these sequences instead of trees. Sasha wants to match each tree with a sequence a_0, a_1, ..., a_{h}, where h is the height of the tree, and a_{i} equals to the number of vertices that are at distance of i edges from root. 

Unfortunately, this time Sasha's intuition was wrong, and there could be several trees matching the same sequence. To show it, you need to write a program that, given the sequence a_{i}, builds two non-isomorphic rooted trees that match that sequence, or determines that there is only one such tree.

Two rooted trees are isomorphic, if you can reenumerate the vertices of the first one in such a way, that the index of the root becomes equal the index of the root of the second tree, and these two trees become equal.

The height of a rooted tree is the maximum number of edges on a path from the root to any other vertex.


-----Input-----

The first line contains a single integer h (2 ≤ h ≤ 10^5) — the height of the tree.

The second line contains h + 1 integers — the sequence a_0, a_1, ..., a_{h} (1 ≤ a_{i} ≤ 2·10^5). The sum of all a_{i} does not exceed 2·10^5. It is guaranteed that there is at least one tree matching this sequence.


-----Output-----

If there is only one tree matching this sequence, print "perfect".

Otherwise print "ambiguous" in the first line. In the second and in the third line print descriptions of two trees in the following format: in one line print $\sum_{i = 0}^{h} a_{i}$ integers, the k-th of them should be the parent of vertex k or be equal to zero, if the k-th vertex is the root.

These treese should be non-isomorphic and should match the given sequence.


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

Output
perfect

Input
2
1 2 2

Output
ambiguous
0 1 1 3 3
0 1 1 3 2



-----Note-----

The only tree in the first example and the two printed trees from the second example are shown on the picture:

$88$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that calculates the *least common multiple* of its arguments; each argument is assumed to be a non-negative integer. In the case that there are no arguments (or the provided array in compiled languages is empty), return `1`.

~~~if:objc
NOTE: The first (and only named) argument of the function `n` specifies the number of arguments in the variable-argument list. Do **not** take `n` into account when computing the LCM of the numbers.
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:


Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya plays the Geometry Horse.

The game goal is to destroy geometric figures of the game world. A certain number of points is given for destroying each figure depending on the figure type and the current factor value. 

There are *n* types of geometric figures. The number of figures of type *k**i* and figure cost *c**i* is known for each figure type. A player gets *c**i*·*f*  points for destroying one figure of type *i*, where *f* is the current factor. The factor value can be an integer number from 1 to *t*<=+<=1, inclusive. At the beginning of the game the factor value is equal to 1. The factor is set to *i*<=+<=1 after destruction of *p**i* (1<=≤<=*i*<=≤<=*t*) figures, so the (*p**i*<=+<=1)-th figure to be destroyed is considered with factor equal to *i*<=+<=1.

Your task is to determine the maximum number of points Vasya can get after he destroys all figures. Take into account that Vasya is so tough that he can destroy figures in any order chosen by him.

Input Specification:
The first line contains the only integer number *n* (1<=≤<=*n*<=≤<=100) — the number of figure types.

Each of the following *n* lines contains two integer numbers *k**i* and *c**i* (1<=≤<=*k**i*<=≤<=109,<=0<=≤<=*c**i*<=≤<=1000), separated with space — the number of figures of the *i*-th type and the cost of one *i*-type figure, correspondingly.

The next line contains the only integer number *t* (1<=≤<=*t*<=≤<=100) — the number that describe the factor's changes. 

The next line contains *t* integer numbers *p**i* (1<=≤<=*p*1<=&lt;<=*p*2<=&lt;<=...<=&lt;<=*p**t*<=≤<=1012), separated with spaces.

Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

Output Specification:
Print the only number — the maximum number of points Vasya can get.

Demo Input:
['1\n5 10\n2\n3 6\n', '2\n3 8\n5 10\n1\n20\n']

Demo Output:
['70', '74']

Note:
In the first example Vasya destroys three figures first and gets 3·1·10 = 30 points. Then the factor will become equal to 2 and after destroying the last two figures Vasya will get 2·2·10 = 40 points. As a result Vasya will get 70 points.

In the second example all 8 figures will be destroyed with factor 1, so Vasya will get (3·8 + 5·10)·1 = 74 points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John Smith knows that his son, Thomas Smith, is among the best students in his class and even in his school. After the students of the school took the exams in English, German, Math, and History, a table of results was formed.

There are $n$ students, each of them has a unique id (from $1$ to $n$). Thomas's id is $1$. Every student has four scores correspond to his or her English, German, Math, and History scores. The students are given in order of increasing of their ids.

In the table, the students will be sorted by decreasing the sum of their scores. So, a student with the largest sum will get the first place. If two or more students have the same sum, these students will be sorted by increasing their ids. 

Please help John find out the rank of his son. 


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of students.

Each of the next $n$ lines contains four integers $a_i$, $b_i$, $c_i$, and $d_i$ ($0\leq a_i, b_i, c_i, d_i\leq 100$) — the grades of the $i$-th student on English, German, Math, and History. The id of the $i$-th student is equal to $i$.


-----Output-----

Print the rank of Thomas Smith. Thomas's id is $1$.


-----Examples-----
Input
5
100 98 100 100
100 100 100 100
100 100 99 99
90 99 90 100
100 98 60 99

Output
2

Input
6
100 80 90 99
60 60 60 60
90 60 100 60
60 100 60 80
100 100 0 100
0 0 0 0

Output
1



-----Note-----

In the first sample, the students got total scores: $398$, $400$, $398$, $379$, and $357$. Among the $5$ students, Thomas and the third student have the second highest score, but Thomas has a smaller id, so his rank is $2$.

In the second sample, the students got total scores: $369$, $240$, $310$, $300$, $300$, and $0$. Among the $6$ students, Thomas got the highest score, so his rank is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string of lowercase letters in the range ascii[a-z], determine the index of a character that can be removed to make the string a palindrome.  There may be more than one solution, but any will do.  If the word is already a palindrome or there is no solution, return -1.  Otherwise, return the index of a character to remove.  

Example 

$s="bcbc"$  

Either remove 'b' at index $0$ or 'c' at index $3$.  

Function Description  

Complete the palindromeIndex function in the editor below.    

palindromeIndex has the following parameter(s):  

string s: a string to analyze  

Returns  

int: the index of the character to remove or $-1$  

Input Format

The first line contains an integer $q$, the number of queries. 

Each of the next $q$ lines contains a query string $s$.

Constraints

$1 \leq q \leq 20$  
$1\leq\text{length of}s\leq10^5+5$  
All characters are in the range ascii[a-z].

Sample Input
STDIN   Function
-----   --------
3       q = 3
aaab    s = 'aaab' (first query)
baa     s = 'baa'  (second query)
aaa     s = 'aaa'  (third query)

Sample Output
3
0
-1

Explanation

Query 1: "aaab" 

Removing 'b' at index $3$ results in a palindrome, so return $3$.     

Query 2: "baa" 

Removing 'b' at index $0$ results in a palindrome, so return $0$.

Query 3: "aaa" 

This string is already a palindrome, so return $-1$.  Removing any one of the characters would result in a palindrome, but this test comes first.

Note: The custom checker logic for this challenge is available here.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string containing a list of integers separated by commas, write the function string_to_int_list(s) that takes said string and returns a new list containing all integers present in the string, preserving the order.

For example, give the string "-1,2,3,4,5", the function string_to_int_list() should return [-1,2,3,4,5]

Please note that there can be one or more consecutive commas whithout numbers, like so: "-1,-2,,,,,,3,4,5,,6"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two integer sequences $A_1, A_2, \ldots, A_N$ and $B_1, B_2, \ldots, B_M$. You should choose $N+M-1$ pairs, each in the form $(A_x, B_y)$, such that the sums $A_x + B_y$ are all pairwise distinct.
It is guaranteed that under the given constraints, a solution always exists. If there are multiple solutions, you may find any one.

-----Input-----
- The first line of the input contains two space-separated integers $N$ and $M$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains $M$ space-separated integers $B_1, B_2, \ldots, B_M$.

-----Output-----
Print $N+M-1$ lines. Each of these lines should contain two space-separated integers $x$ and $y$ denoting that you chose a pair $(A_{x+1}, B_{y+1})$.

-----Constraints-----
- $1 \le N, M \le 2 \cdot 10^5$
- $|A_i| \le 10^9$ for each valid $i$
- $|B_i| \le 10^9$ for each valid $i$
- $A_1, A_2, \ldots, A_N$ are pairwise distinct
- $B_1, B_2, \ldots, B_M$ are pairwise distinct

-----Subtasks-----
Subtask #1 (25 points): $1 \le N, M \le 10^3$
Subtask #2 (75 points): original constraints

-----Example Input-----
3 2
10 1 100
4 3

-----Example Output-----
2 1
0 0
1 0
0 1

-----Explanation-----
The chosen pairs and their sums are:
- $A_3 + B_2 = 100+3 = 103$
- $A_1 + B_1 = 10+4 = 14$
- $A_2 + B_1 = 1+4 = 5$
- $A_1 + B_2 = 10+3 = 13$
Since all sums are distinct, this is a correct output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string of numbers between 0-9. Find the average of these numbers and return it as a floored whole number (ie: no decimal places) written out as a string. Eg:

"zero nine five two" -> "four"

If the string is empty or includes a number greater than 9, return "n/a"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When working with color values it can sometimes be useful to extract the individual red, green, and blue (RGB) component values for a color. Implement a function that meets these requirements:

+ Accepts a case-insensitive hexadecimal color string as its parameter (ex. `"#FF9933"` or `"#ff9933"`)
+ Returns an object with the structure `{r: 255, g: 153, b: 51}` where *r*, *g*, and *b* range from 0 through 255

**Note:** your implementation does not need to support the shorthand form of hexadecimal notation (ie `"#FFF"`)


## Example

```
"#FF9933" --> {r: 255, g: 153, b: 51}
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array (arr) as an argument complete the function `countSmileys` that should return the total number of smiling faces.  

Rules for a smiling face:
- Each smiley face must contain a valid pair of eyes. Eyes can be marked as `:` or `;`
- A smiley face can have a nose but it does not have to. Valid characters for a nose are `-` or `~`
- Every smiling face must have a smiling mouth that should be marked with either `)` or `D`

No additional characters are allowed except for those mentioned.  

**Valid smiley face examples:** `:) :D ;-D :~)`  
**Invalid smiley faces:**  `;( :> :} :]`

## Example

```
countSmileys([':)', ';(', ';}', ':-D']);       // should return 2;
countSmileys([';D', ':-(', ':-)', ';~)']);     // should return 3;
countSmileys([';]', ':[', ';*', ':$', ';-D']); // should return 1;
```

## Note

In case of an empty array return 0. You will not be tested with invalid input (input will always be an array). Order of the face (eyes, nose, mouth) elements will always be the same.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The R1 company wants to hold a web search championship. There were *n* computers given for the competition, each of them is connected to the Internet. The organizers believe that the data transfer speed directly affects the result. The higher the speed of the Internet is, the faster the participant will find the necessary information. Therefore, before the competition started, each computer had its maximum possible data transfer speed measured. On the *i*-th computer it was *a**i* kilobits per second.

There will be *k* participants competing in the championship, each should get a separate computer. The organizing company does not want any of the participants to have an advantage over the others, so they want to provide the same data transfer speed to each participant's computer. Also, the organizers want to create the most comfortable conditions for the participants, so the data transfer speed on the participants' computers should be as large as possible.

The network settings of the R1 company has a special option that lets you to cut the initial maximum data transfer speed of any computer to any lower speed. How should the R1 company configure the network using the described option so that at least *k* of *n* computers had the same data transfer speed and the data transfer speed on these computers was as large as possible?

Input Specification:
The first line contains two space-separated integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=100) — the number of computers and the number of participants, respectively. In the second line you have a space-separated sequence consisting of *n* integers: *a*1,<=*a*2,<=...,<=*a**n* (16<=≤<=*a**i*<=≤<=32768); number *a**i* denotes the maximum data transfer speed on the *i*-th computer.

Output Specification:
Print a single integer — the maximum Internet speed value. It is guaranteed that the answer to the problem is always an integer.

Demo Input:
['3 2\n40 20 30\n', '6 4\n100 20 40 20 50 50\n']

Demo Output:
['30\n', '40\n']

Note:
In the first test case the organizers can cut the first computer's speed to 30 kilobits. Then two computers (the first and the third one) will have the same speed of 30 kilobits. They should be used as the participants' computers. This answer is optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The game of bingo is played on a 5 × 5 square grid filled with distinct numbers between 1 and 75. In this problem you will consider a generalized version played on an n × n grid with distinct numbers between 1 and m (m ≥ n2). 

A player begins by selecting a randomly generated bingo grid (generated uniformly among all available grids). Then k distinct numbers between 1 and m will be called at random (called uniformly among all available sets of k numbers). For each called number that appears on the grid, the player marks that cell. The score at the end is 2 raised to the power of (number of completely marked rows plus number of completely marked columns).

Determine the expected value of the score. The expected score may be very large. If the expected score is larger than 1099, print 1099 instead (for example as "1e99" without the quotes).

Input

Input will consist of three integers n, m, k (1 ≤ n ≤ 300; n2 ≤ m ≤ 100000; n ≤ k ≤ m).

Output

Print the smaller of 1099 and the expected score. Your answer must be correct within an absolute or relative error of 10 - 9.

Examples

Input

1 2 1


Output

2.5


Input

2 4 3


Output

4


Input

7 59164 40872


Output

3.1415926538

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development.  

You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting of $n$ integers $[a_1,a_2,\ldots,a_n]$, define $f(l,r)=\text{gcd}(a_l,a_{l+1},\ldots,a_r)\cdot\left(\left(\sum\limits_{i=l}^r a_i\right)-\text{max}(a_l,a_{l+1},\ldots,a_r)\right).$

For example, for an input array [ 10, -5, 5, 20 ], a subsegment $f(1,1)$ would be computed as follows: 

What is $\max\limits_{1\leq l\leq r\leq n}f(l,r)$, i.e., the maximum value of $f(l,r)$ among all subsegments $[l,r]$?  

Complete the function maximumValue which takes an integer array as input and returns the maximum value of $\mbox{f}$ among all subsegments $[l,r]$.

Note that:

$\text{gcd}(x,y)=\text{gcd}(|x|,|y|)$
$\text{gcd}(x,0)=\text{gcd}(0,x)=|x|$

Input Format

The first line contains a single integer $n$

The second line contains $n$ space-separated integers $a_1,a_2,\ldots a_n$

Constraints

$1\leq n\leq50000$ 

$-10^6\leq a_i\leq10^6$  

Output Format

Print a single integer denoting the answer

Sample Input 0
4
10 -5 5 20

Sample Output 0
50

Explanation 0

The maximum value occurs at $f(1,4)=50$ as shown below. 

Sample Input 1
5
7 12 24 6 5

Sample Output 1
144

Explanation 1

The maximum value occurs at $f(2,3)=144$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Dexterina’s Lab

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dexterina and Womandark have been arch-rivals since they’ve known each other. Since both are super-intelligent teenage girls, they’ve always been trying to solve their disputes in a peaceful and nonviolent way. After god knows how many different challenges they’ve given to one another, their score is equal and they’re both desperately trying to best the other in various games of wits. This time, Dexterina challenged Womandark to a game of Nim.

Nim is a two-player game in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects from a single heap. The player who can't make a turn loses. By their agreement, the sizes of piles are selected randomly from the range [0,<=*x*]. Each pile's size is taken independently from the same probability distribution that is known before the start of the game.

Womandark is coming up with a brand new and evil idea on how to thwart Dexterina’s plans, so she hasn’t got much spare time. She, however, offered you some tips on looking fabulous in exchange for helping her win in Nim. Your task is to tell her what is the probability that the first player to play wins, given the rules as above.

Input Specification:
The first line of the input contains two integers *n* (1<=≤<=*n*<=≤<=109) and *x* (1<=≤<=*x*<=≤<=100) — the number of heaps and the maximum number of objects in a heap, respectively. The second line contains *x*<=+<=1 real numbers, given with up to 6 decimal places each: *P*(0),<=*P*(1),<=... ,<=*P*(*X*). Here, *P*(*i*) is the probability of a heap having exactly *i* objects in start of a game. It's guaranteed that the sum of all *P*(*i*) is equal to 1.

Output Specification:
Output a single real number, the probability that the first player wins. The answer will be judged as correct if it differs from the correct answer by at most 10<=-<=6.

Demo Input:
['2 2\n0.500000 0.250000 0.250000\n']

Demo Output:
['0.62500000\n']

Note:
none

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