vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
See Russian Translation

A few months ago, it was discovered that there exists a gate that opens into another world!

In the new world, there are some primitive civilizations. Therefore, your country has decided to set up a communication network on the straight road between the gate and the foreign capital city. To accomplish this, the country has K available communications towers and hired you to make a plan for the placement of some or all of these towers.

There are N possible locations on the straight road that you can set up a communications tower at. If we number these positions with the natural numbers from 1 to N, we find that the distance between position i and position i + 1 is a constant 1 unit over all i. Therefore, the distance between two towers i and j is equal to |i - j|.

Before a tower is set up, the land must first be prepared. You will hire local workers to prepare the land, but you must pay them in local currency. The current exchange rate of your currency to local currency is 1024 : 1. The cost to prepare the land at the location i is given by Ai, which is guaranteed to be a positive multiple of 1024.

Additionally, it is necessary to build towers at the location of the gate and at the location of the foreign capital. These two locations are locations 1 and N, respectively.

You have devised a formula to calculate the overall cost of the operation. A feasible plan is a set S (2 ≤ |S| ≤ K) of locations that you plan to build towers on. Assume Si denotes the i^th element of the set S, and that Si < Si+1 for all i. The overall cost for a set S is

K × K × (AS1 + AS2 + ... + AS|S|) + (S2 - S1)^2 + (S3 - S2)^2 + ... + (S|S| - S|S|-1)^2.

This formula accounts for the cost of preparing the land to build towers on as well as the communication strength on all points on the road. Intuitively, building too few towers will reduce the cost of land preparation, but it will also reduce the communication strength, resulting in a higher overall cost.

You should formulate a feasible plan to minimize the overall cost, and output this minimum value.

Input Format: 
The first line of input will contain N and K, the number of locations and the number of towers at your disposal, respectively. 
The second line of input will contain N integers, A1 to AN.

Output Format: 
The first and only line of output should contain the minimum overall cost for a feasible plan.

Constraints: 
For all subtasks, 
2 ≤ K ≤ N 
1024 ≤ Ai ≤ 2^20 
Ai will be divisible by 1024. 
[Subtask 1 - 8%] 
2 ≤ N ≤ 15 
[Subtask 2 - 4%] 
2 ≤ N ≤ 30 
[Subtask 3 - 25%] 
2 ≤ N ≤ 300 
[Subtask 4 - 13%] 
2 ≤ N ≤ 10^5 
Additionally, Ai = 1024 for all i. 
[Subtask 5 - 50%] 
2 ≤ N ≤ 10^5 

SAMPLE INPUT
4 3
3072 65536 65536 2048

SAMPLE OUTPUT
46089

Explanation

The optimal solution is to build 2 towers at locations 1 and 4, with overall cost 3 × 3 × (3072 + 2048) + 3^2 = 46089.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given an array of arrays and your task will be to return the number of unique arrays that can be formed by picking exactly one element from each subarray. 

For example: `solve([[1,2],[4],[5,6]]) = 4`, because it results in only `4` possiblites. They are `[1,4,5],[1,4,6],[2,4,5],[2,4,6]`. 

```if:r
In R, we will use a list data structure.
So the argument for `solve` is a list of numeric vectors.
~~~
solve(list(c(1, 2), 4, c(5, 6)))
[1] 4
~~~
```

Make sure that you don't count duplicates; for example `solve([[1,2],[4,4],[5,6,6]]) = 4`, since the extra outcomes are just duplicates. 

See test cases for more examples.

Good luck!

If you like this Kata, please try:

[Sum of integer combinations](https://www.codewars.com/kata/59f3178e3640cef6d90000d5)

[Sum of array singles](https://www.codewars.com/kata/59f11118a5e129e591000134)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an undirected tree where each vertex is numbered from $1$ to $n$, and each contains a data value.  The sum of a tree is the sum of all its nodes' data values.  If an edge is cut, two smaller trees are formed.  The difference between two trees is the absolute value of the difference in their sums.  

Given a tree, determine which edge to cut so that the resulting trees have a minimal difference between them, then return that difference.  

Example 

$data=[1,2,3,4,5,6]$ 

$edges=[(1,2),(1,3),(2,6),(3,4),(3,5)]$   

In this case, node numbers match their weights for convenience.  The graph is shown below.   

The values are calculated as follows:  

Edge    Tree 1  Tree 2  Absolute
Cut     Sum      Sum     Difference
1        8         13         5
2        9         12         3
3        6         15         9
4        4         17        13
5        5         16        11

The minimum absolute difference is $3$.

Note: The given tree is always rooted at vertex $1$.  

Function Description  

Complete the cutTheTree function in the editor below.    

cutTheTree has the following parameter(s):  

int data[n]: an array of integers that represent node values  
int edges[n-1][2]: an 2 dimensional array of integer pairs where each pair represents nodes connected by the edge  

Returns  

int: the minimum achievable absolute difference of tree sums  

Input Format

The first line contains an integer $n$, the number of vertices in the tree. 

The second line contains $n$ space-separated integers, where each integer $\mbox{u}$ denotes the $node[u]$ data value, $\textit{data}[u]$. 

Each of the $n-1$ subsequent lines contains two space-separated integers $\mbox{u}$ and $\boldsymbol{\nu}$ that describe edge $u\leftrightarrow v$ in tree $\boldsymbol{\boldsymbol{t}}$.        

Constraints

$3\leq n\leq10^5$  
$1\leq data[u]\leq1001$, where $1\leq u\leq n$.

Sample Input
STDIN                       Function
-----                       --------
6                           data[] size n = 6
100 200 100 500 100 600     data = [100, 200, 100, 500, 100, 600]
1 2                         edges = [[1, 2], [2, 3], [2, 5], [4, 5], [5, 6]]
2 3
2 5
4 5
5 6

Sample Output
400

Explanation

We can visualize the initial, uncut tree as:  

There are $n-1=5$ edges we can cut:

Edge $1\leftrightarrow2$ results in $d_{1\leftrightarrow2}=1500-100=1400$ 
Edge $2\leftrightarrow3$ results in $d_{2\leftrightarrow3}=1500-100=1400$
Edge $2\leftrightarrow5$ results in $d_{2\leftrightarrow5}=1200-400=800$ 
Edge $4\leftrightarrow5$ results in $d_{4\leftrightarrow5}=1100-500=600$
Edge $5\leftrightarrow6$ results in $d_{5\leftrightarrow6}=1000-600=400$

The minimum difference is $\textbf{400}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petr has just bought a new car. He's just arrived at the most known Petersburg's petrol station to refuel it when he suddenly discovered that the petrol tank is secured with a combination lock! The lock has a scale of $360$ degrees and a pointer which initially points at zero:

 [Image] 

Petr called his car dealer, who instructed him to rotate the lock's wheel exactly $n$ times. The $i$-th rotation should be $a_i$ degrees, either clockwise or counterclockwise, and after all $n$ rotations the pointer should again point at zero.

This confused Petr a little bit as he isn't sure which rotations should be done clockwise and which should be done counterclockwise. As there are many possible ways of rotating the lock, help him and find out whether there exists at least one, such that after all $n$ rotations the pointer will point at zero again.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 15$) — the number of rotations.

Each of the following $n$ lines contains one integer $a_i$ ($1 \leq a_i \leq 180$) — the angle of the $i$-th rotation in degrees.


-----Output-----

If it is possible to do all the rotations so that the pointer will point at zero after all of them are performed, print a single word "YES". Otherwise, print "NO". Petr will probably buy a new car in this case.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
3
10
20
30

Output
YES

Input
3
10
10
10

Output
NO

Input
3
120
120
120

Output
YES



-----Note-----

In the first example, we can achieve our goal by applying the first and the second rotation clockwise, and performing the third rotation counterclockwise.

In the second example, it's impossible to perform the rotations in order to make the pointer point at zero in the end.

In the third example, Petr can do all three rotations clockwise. In this case, the whole wheel will be rotated by $360$ degrees clockwise and the pointer will point at zero again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Petya wanted to give an April Fools Day present to some scientists. After some hesitation he decided to give them the array that he got as a present in Codeforces Round #153 (Div.2). The scientists rejoiced at the gift and decided to put some important facts to this array. Here are the first few of the facts: The highest mountain above sea level in the world is Mount Everest. Its peak rises to 8848 m.  The largest board game tournament consisted of 958 participants playing chapaev. The largest online maths competition consisted of 12766 participants. The Nile is credited as the longest river in the world. From its farthest stream in Burundi, it extends 6695 km in length. While not in flood, the main stretches of the Amazon river in South America can reach widths of up to 1100 km at its widest points. Angel Falls is the highest waterfall. Its greatest single drop measures 807 m. The Hotel Everest View above Namche, Nepal — the village closest to Everest base camp – is at a record height of 31962 m Uranium is the heaviest of all the naturally occurring elements. Its most common isotope has a nucleus containing 146 neutrons. The coldest permanently inhabited place is the Siberian village of Oymyakon, where the temperature of -68°C was registered in the twentieth century. The longest snake held in captivity is over 25 feet long. Its name is Medusa. Colonel Meow holds the world record for longest fur on a cat — almost 134 centimeters. Sea otters can have up to 10000 hairs per square inch. This is the most dense fur in the animal kingdom. The largest state of USA is Alaska; its area is 663268 square miles Alaska has a longer coastline than all of the other 49 U.S. States put together: it is 154103 miles long. Lake Baikal is the largest freshwater lake in the world. It reaches 1642 meters in depth and contains around one-fifth of the world’s unfrozen fresh water. The most colorful national flag is the one of Turkmenistan, with 106 colors. 


-----Input-----

The input will contain a single integer between 1 and 16.


-----Output-----

Output a single integer.


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

Output
1

Input
7

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an integer variable x.
Initially, x=0.
Some person gave you a string S of length N, and using the string you performed the following operation N times.
In the i-th operation, you incremented the value of x by 1 if S_i=I, and decremented the value of x by 1 if S_i=D.
Find the maximum value taken by x during the operations (including before the first operation, and after the last operation).

-----Constraints-----
 - 1≤N≤100
 - |S|=N
 - No characters except I and D occur in S.

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

-----Output-----
Print the maximum value taken by x during the operations.

-----Sample Input-----
5
IIDID

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

After each operation, the value of x becomes 1, 2, 1, 2 and 1, respectively. Thus, the output should be 2, the maximum value.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr of size N, the goal is to find out the smallest number that is repeated exactly ‘K’ times.
 
Example 1:
Input:
N=5, K=2
arr[] = { 2 2 1 3 1 }
Output: 1
Explanation: Here in array,
2 is repeated 2 times, 1 is repeated
2 times, 3 is repeated 1 time.
Hence 2 and 1 both are repeated 'k' 
times i.e 2 and min(2, 1) is 1 .
 
Example 2:
Input:
N=4, K=1 
arr[] = { 3 5 3 2 }
Output:  2 
Explanation: Both 2 and 5 are repeating 1
time but min(5, 2) is 2.
 
Your Task:
You just need to complete the function findDuplicate() that takes array arr, integer N and integer K as parameters and returns the required answer.
Note- If there is no such element then return -1.
 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(MAX). where MAX is maximum element in the array.
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
User ainta is making a web site. This time he is going to make a navigation of the pages. In his site, there are *n* pages numbered by integers from 1 to *n*. Assume that somebody is on the *p*-th page now. The navigation will look like this:

When someone clicks the button "&lt;&lt;" he is redirected to page 1, and when someone clicks the button "&gt;&gt;" he is redirected to page *n*. Of course if someone clicks on a number, he is redirected to the corresponding page.

There are some conditions in the navigation:
 -  If page 1 is in the navigation, the button "&lt;&lt;" must not be printed. -  If page *n* is in the navigation, the button "&gt;&gt;" must not be printed. -  If the page number is smaller than 1 or greater than *n*, it must not be printed. 
You can see some examples of the navigations. Make a program that prints the navigation.

Input Specification:
The first and the only line contains three integers *n*, *p*, *k* (3<=≤<=*n*<=≤<=100; 1<=≤<=*p*<=≤<=*n*; 1<=≤<=*k*<=≤<=*n*)

Output Specification:
Print the proper navigation. Follow the format of the output from the test samples.

Demo Input:
['17 5 2\n', '6 5 2\n', '6 1 2\n', '6 2 2\n', '9 6 3\n', '10 6 3\n', '8 5 4\n']

Demo Output:
['&lt;&lt; 3 4 (5) 6 7 &gt;&gt; ', '&lt;&lt; 3 4 (5) 6 ', '(1) 2 3 &gt;&gt; ', '1 (2) 3 4 &gt;&gt;', '&lt;&lt; 3 4 5 (6) 7 8 9', '&lt;&lt; 3 4 5 (6) 7 8 9 &gt;&gt;', '1 2 3 4 (5) 6 7 8 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef recently solved his first problem on CodeChef. The problem he solved has N test cases. He gets a score for his submission according to the following rules:

1) If Chef’s code passes all the N test cases, he gets 100 points.

2) If Chef’s code does not pass all the test cases, but passes all the first M\;(M < N) test cases, he gets K\;(K < 100) points.

3) If the conditions 1 and 2 are not satisfied, Chef does not get any points (i.e his score remains at 0 points).

You are given a binary array A_{1}, A_{2}, \dots, A_{N} of length N, where A_{i} = 1 denotes Chef's code passed the i^{th} test case, A_{i} = 0 denotes otherwise. You are also given the two integers M, K. Can you find how many points does Chef get?

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

- First line will contain T, number of testcases. Then the testcases follow.
- The first line of each test case contains three space-separated integers N, M, K.
- The second line contains N space-separated integer A_{1}, A_{2},\dots, A_{N}.

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

For each testcase, output in a single line the score of Chef.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 100$
$1 ≤ M < N$
$1 ≤ K < 100$
$0 ≤ A_{i} ≤ 1$

----- Sample Input 1 ------ 
4
4 2 50
1 0 1 1
3 2 50
1 1 0
4 2 50
1 1 1 1
5 3 30
1 1 0 1 1

----- Sample Output 1 ------ 
0
50
100
0

----- explanation 1 ------ 
Test case $1$: Chef's code neither passes all $4$ test cases nor passes the first $2$ test cases. Hence he does not get any points.

Test case $2$: Chef's code does not pass all $3$ test cases, but passes the first $2$ test cases. Hence he gets $50$ points.

Test case $3$: Chef's code passes all the $4$ test cases. Hence he gets $100$ points.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:


Input Specification:
The input contains two integers *a*1,<=*a*2 (0<=≤<=*a**i*<=≤<=32), separated by a single space.

Output Specification:
Output a single integer.

Demo Input:
['1 1\n', '3 7\n', '13 10\n']

Demo Output:
['0\n', '0\n', '1\n']

Note:
none

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Thumbelina has had an accident. She has found herself on a little island in the middle of a swamp and wants to get to the shore very much.

One can get to the shore only by hills that are situated along a straight line that connects the little island with the shore. Let us assume that the hills are numbered from 1 to *n* and the number of a hill is equal to the distance in meters between it and the island. The distance between the *n*-th hill and the shore is also 1 meter.

Thumbelina is too small to make such jumps. Fortunately, a family of frogs living in the swamp suggests to help her. Each frog agrees to give Thumbelina a ride but Thumbelina should choose only one frog. Each frog has a certain jump length. If Thumbelina agrees to accept help from a frog whose jump length is *d*, the frog will jump from the island on the hill *d*, then — on the hill 2*d*, then 3*d* and so on until they get to the shore (i.e. find itself beyond the hill *n*).

However, there is one more problem: mosquitoes also live in the swamp. At the moment they have a siesta, and they are having a nap on some hills. If the frog jumps on a hill with a mosquito the frog will smash it. The frogs Thumbelina has met are pacifists, so they will find the death of each mosquito very much sad. Help Thumbelina choose a frog that will bring her to the shore and smash as small number of mosquitoes as possible.

Input Specification:
The first line contains three integers *n*, *m* and *k* (1<=≤<=*n*<=≤<=109, 1<=≤<=*m*,<=*k*<=≤<=100) — the number of hills, frogs and mosquitoes respectively. The second line contains *m* integers *d**i* (1<=≤<=*d**i*<=≤<=109) — the lengths of the frogs’ jumps. The third line contains *k* integers — the numbers of the hills on which each mosquito is sleeping. No more than one mosquito can sleep on each hill. The numbers in the lines are separated by single spaces.

Output Specification:
In the first line output the number of frogs that smash the minimal number of mosquitoes, in the second line — their numbers in increasing order separated by spaces. The frogs are numbered from 1 to *m* in the order of the jump length given in the input data.

Demo Input:
['5 3 5\n2 3 4\n1 2 3 4 5\n', '1000000000 2 3\n2 5\n999999995 999999998 999999996\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's pretend your company just hired your friend from college and paid you a referral bonus. Awesome! To celebrate, you're taking your team out to the terrible dive bar next door and using the referral bonus to buy, and build, the largest three-dimensional beer can pyramid you can. And then probably drink those beers, because let's pretend it's Friday too. 

A beer can pyramid will square the number of cans in each level - 1 can in the top level, 4 in the second, 9 in the next, 16, 25... 

Complete the beeramid function to return the number of **complete** levels of a beer can pyramid you can make, given the parameters of: 

1) your referral bonus, and

2) the price of a beer can

For example:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have 4 bags A, B, C and D each of which includes N coins (there are totally 4N coins). Values of the coins in each bag are ai, bi, ci and di respectively.

Find the number of combinations that result when you choose one coin from each bag (totally 4 coins) in such a way that the total value of the coins is V. You should distinguish the coins in a bag.

Constraints

* 1 ≤ N ≤ 1000
* 1 ≤ ai, bi, ci, di ≤ 1016
* 1 ≤ V ≤ 1016
* All input values are given in integers

Input

The input is given in the following format.


N V
a1 a2 ... aN
b1 b2 ... bN
c1 c2 ... cN
d1 d2 ... dN


Output

Print the number of combinations in a line.

Examples

Input

3 14
3 1 2
4 8 2
1 2 3
7 3 2


Output

9


Input

5 4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1


Output

625

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right.

Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.


-----Input-----

The first line of the input contains n (1 ≤ n ≤ 200 000) — the number of bishops.

Each of next n lines contains two space separated integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ 1000) — the number of row and the number of column where i-th bishop is positioned. It's guaranteed that no two bishops share the same position.


-----Output-----

Output one integer — the number of pairs of bishops which attack each other. 


-----Examples-----
Input
5
1 1
1 5
3 3
5 1
5 5

Output
6

Input
3
1 1
2 3
3 5

Output
0



-----Note-----

In the first sample following pairs of bishops attack each other: (1, 3), (1, 5), (2, 3), (2, 4), (3, 4) and (3, 5). Pairs (1, 2), (1, 4), (2, 5) and (4, 5) do not attack each other because they do not share the same diagonal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Amr and The Large Array

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Amr has got a large array of size *n*. Amr doesn't like large arrays so he intends to make it smaller.

Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.

Help Amr by choosing the smallest subsegment possible.

Input Specification:
The first line contains one number *n* (1<=≤<=*n*<=≤<=105), the size of the array.

The second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=106), representing elements of the array.

Output Specification:
Output two integers *l*,<=*r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*), the beginning and the end of the subsegment chosen respectively.

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

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

Demo Output:
['1 5', '2 3', '1 5']

Note:
A subsegment *B* of an array *A* from *l* to *r* is an array of size *r* - *l* + 1 where *B*<sub class="lower-index">*i*</sub> = *A*<sub class="lower-index">*l* + *i* - 1</sub> for all 1 ≤ *i* ≤ *r* - *l* + 1

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