vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Naruto has sneaked into the Orochimaru's lair and is now looking for Sasuke. There are $T$ rooms there. Every room has a door into it, each door can be described by the number $n$ of seals on it and their integer energies $a_1$, $a_2$, ..., $a_n$. All energies $a_i$ are nonzero and do not exceed $100$ by absolute value. Also, $n$ is even.

In order to open a door, Naruto must find such $n$ seals with integer energies $b_1$, $b_2$, ..., $b_n$ that the following equality holds: $a_{1} \cdot b_{1} + a_{2} \cdot b_{2} + ... + a_{n} \cdot b_{n} = 0$. All $b_i$ must be nonzero as well as $a_i$ are, and also must not exceed $100$ by absolute value. Please find required seals for every room there.


-----Input-----

The first line contains the only integer $T$ ($1 \leq T \leq 1000$) standing for the number of rooms in the Orochimaru's lair. The other lines contain descriptions of the doors.

Each description starts with the line containing the only even integer $n$ ($2 \leq n \leq 100$) denoting the number of seals.

The following line contains the space separated sequence of nonzero integers $a_1$, $a_2$, ..., $a_n$ ($|a_{i}| \leq 100$, $a_{i} \neq 0$) denoting the energies of seals.


-----Output-----

For each door print a space separated sequence of nonzero integers $b_1$, $b_2$, ..., $b_n$ ($|b_{i}| \leq 100$, $b_{i} \neq 0$) denoting the seals that can open the door. If there are multiple valid answers, print any. It can be proven that at least one answer always exists.


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

Output
-100 1
1 1 1 -1



-----Note-----

For the first door Naruto can use energies $[-100, 1]$. The required equality does indeed hold: $1 \cdot (-100) + 100 \cdot 1 = 0$.

For the second door Naruto can use, for example, energies $[1, 1, 1, -1]$. The required equality also holds: $1 \cdot 1 + 2 \cdot 1 + 3 \cdot 1 + 6 \cdot (-1) = 0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have $n$ lights, each with its own button, in a line. Pressing a light’s button will toggle that light’s state; if the light is on, it will turn off, and if the light is off, it will turn on. The lights change at $1$ second timesteps. You can press a button at any time, but it will not take effect until the next timestep. Before each timestep, you may choose to push at most one button (you may also choose to not press any button).

Pushing a button will affect not just the light in question, but all lights down the line. More specifically, if you choose to press the $i^\textrm {th}$ button right before the $k^\textrm {th}$ timestep, then the $(i+m)^\textrm {th}$ light will toggle on the $(k+m)^\textrm {th}$ timestep (with $i+m \le n$). For example, if you press button $5$ just before time $19$, then light $5$ will toggle at time $19$, light $6$ will toggle at time $20$, light $7$ will toggle at time $21$, and so on. If you push a button that will take effect at the same time as its light would have toggled due to an earlier button press, then the two cancel each other out, including subsequent toggles.

Suppose there are three lights, all of which are off at the start. If you press the first button before the first timestep, this will happen in three timesteps:

Now, suppose you press the first button before the first timestep, and then the second button between the first and second timesteps. The button press will cancel out the propagation, and this will happen (note that the propagation will go no further):


 Now, suppose you press the first button before the first timestep, and then the third button between the first and second timesteps. All three lights will be on at the second timestep (but not the third):

You wish to turn on all the lights. What is the earliest time you could possibly see all of the lights turned on? Note that if the lights are all on at time $t$ but not at time $t+1$ due to this propagation, $t$ is still the correct answer.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single string $S$ ($1 \le |S| \le 16$). The string $S$ will contain only the characters $1$ and $0$, where $1$ represents that that light is initially on, and $0$ represents that that light is initially off. The first character is light $1$, the next is light $2$, and so on.

-----Output-----
Output a single integer, which is the earliest time at which all of the lights are on.

-----Examples-----
Sample Input 1:
1101
Sample Output 1:
1

Sample Input 2:
1
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a with n distinct integers. Construct an array b by permuting a such that for every non-empty subset of indices S = {x_1, x_2, ..., x_{k}} (1 ≤ x_{i} ≤ n, 0 < k < n) the sums of elements on that positions in a and b are different, i. e. $\sum_{i = 1}^{k} a_{x_{i}} \neq \sum_{i = 1}^{k} b_{x_{i}}$


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 22) — the size of the array.

The second line contains n space-separated distinct integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — the elements of the array.


-----Output-----

If there is no such array b, print -1.

Otherwise in the only line print n space-separated integers b_1, b_2, ..., b_{n}. Note that b must be a permutation of a.

If there are multiple answers, print any of them.


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

Output
2 1 

Input
4
1000 100 10 1

Output
100 1 1000 10



-----Note-----

An array x is a permutation of y, if we can shuffle elements of y such that it will coincide with x.

Note that the empty subset and the subset containing all indices are not counted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're researching friendships between groups of $n$ new college students where each student is distinctly numbered from $1$ to $n$. At the beginning of the semester, no student knew any other student; instead, they met and formed individual friendships as the semester went on. The friendships between students are:

Bidirectional. If student $\class{ML__boldsymbol}{\boldsymbol{a}}$ is friends with student $\boldsymbol{b}$, then student $\boldsymbol{b}$ is also friends with student $\class{ML__boldsymbol}{\boldsymbol{a}}$.
Transitive. If student $\class{ML__boldsymbol}{\boldsymbol{a}}$ is friends with student $\boldsymbol{b}$ and student $\boldsymbol{b}$ is friends with student $c$, then student $\class{ML__boldsymbol}{\boldsymbol{a}}$ is friends with student $c$. In other words, two students are considered to be friends even if they are only indirectly linked through a network of mutual (i.e., directly connected) friends. 

The purpose of your research is to find the maximum total value of a group's friendships, denoted by $total$. Each time a direct friendship forms between two students, you sum the number of friends that each of the $n$ students has and add the sum to $total$. 

You are given $\textit{q}$ queries, where each query is in the form of an unordered list of $m$ distinct direct friendships between $n$ students. For each query, find the maximum value of $total$ among all possible orderings of formed friendships and print it on a new line.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains two space-separated integers describing the respective values of $n$ (the number of students) and $m$ (the number of distinct direct friendships).
Each of the $m$ subsequent lines contains two space-separated integers describing the respective values of $\boldsymbol{x}$ and $y$ (where $x\neq y$) describing a friendship between student $\boldsymbol{x}$ and student $y$.

Constraints

$1\leq q\leq16$  
$1\leq n\leq10^5$   
$1\leq m\leq\text{min}(\frac{n\cdot(n-1)}{2},2\times10^5)$  

Output Format

For each query, print the maximum value of $total$ on a new line.

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

Sample Output 0
32

Explanation 0

The value of $total$ is maximal if the students form the $m=4$ direct friendships in the following order:

Students $1$ and $2$ become friends: 

We then sum the number of friends that each student has to get $1+1+0+0+0=2$.

Students $2$ and $\begin{array}{c}4\end{array}$ become friends: 

We then sum the number of friends that each student has to get $2+2+0+2+0=6$.

Students $3$ and $\begin{array}{c}4\end{array}$ become friends: 

We then sum the number of friends that each student has to get $3+3+3+3+0=12$.

Students $3$ and $2$ become friends: 

We then sum the number of friends that each student has to get $3+3+3+3+0=12$.

When we add the sums from each step, we get $total=2+6+12+12=32$. We then print $32$ on a new line.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A permutation *p* of size *n* is an array such that every integer from 1 to *n* occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least *n*<=-<=*k* indices *i* (1<=≤<=*i*<=≤<=*n*) such that *p**i*<==<=*i*.

Your task is to count the number of almost identity permutations for given numbers *n* and *k*.

Input Specification:
The first line contains two integers *n* and *k* (4<=≤<=*n*<=≤<=1000, 1<=≤<=*k*<=≤<=4).

Output Specification:
Print the number of almost identity permutations for given *n* and *k*.

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

Demo Output:
['1\n', '7\n', '31\n', '76\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
And now the numerous qualifying tournaments for one of the most prestigious Russian contests Russian Codec Cup are over. All n participants who have made it to the finals found themselves in a huge m-floored 108-star hotel. Of course the first thought to come in a place like this is "How about checking out the elevator?".

The hotel's elevator moves between floors according to one never changing scheme. Initially (at the moment of time 0) the elevator is located on the 1-st floor, then it moves to the 2-nd floor, then — to the 3-rd floor and so on until it reaches the m-th floor. After that the elevator moves to floor m - 1, then to floor m - 2, and so on until it reaches the first floor. This process is repeated infinitely. We know that the elevator has infinite capacity; we also know that on every floor people get on the elevator immediately. Moving between the floors takes a unit of time.

For each of the n participant you are given si, which represents the floor where the i-th participant starts, fi, which represents the floor the i-th participant wants to reach, and ti, which represents the time when the i-th participant starts on the floor si.

For each participant print the minimum time of his/her arrival to the floor fi. 

If the elevator stops on the floor si at the time ti, then the i-th participant can enter the elevator immediately. If the participant starts on the floor si and that's the floor he wanted to reach initially (si = fi), then the time of arrival to the floor fi for this participant is considered equal to ti.

Input

The first line contains two space-separated integers n and m (1 ≤ n ≤ 105, 2 ≤ m ≤ 108). 

Next n lines contain information about the participants in the form of three space-separated integers si fi ti (1 ≤ si, fi ≤ m, 0 ≤ ti ≤ 108), described in the problem statement.

Output

Print n lines each containing one integer — the time of the arrival for each participant to the required floor.

Examples

Input

7 4
2 4 3
1 2 0
2 2 0
1 2 1
4 3 5
1 2 2
4 2 0


Output

9
1
0
7
10
7
5


Input

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


Output

12
10
10
8
7

Note

Let's consider the first sample. The first participant starts at floor s = 2 by the time equal to t = 3. To get to the floor f = 4, he has to wait until the time equals 7, that's the time when the elevator will go upwards for the second time. Then the first participant should get on the elevator and go two floors up. In this case the first participant gets to the floor f at time equal to 9. The second participant starts at the time t = 0 on the floor s = 1, enters the elevator immediately, and arrives to the floor f = 2. The third participant doesn't wait for the elevator, because he needs to arrive to the same floor where he starts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

 
Example 1:
Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8). 

Example 2:
Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].

Example 3:
Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

Example 4:
Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.

 
Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The kingdom of Olympia consists of *N* cities and *M* bidirectional roads. Each road connects exactly two cities and two cities can be connected with more than one road. Also it possible that some roads connect city with itself making a loop.

All roads are constantly plundered with bandits. After a while bandits became bored of wasting time in road robberies, so they suggested the king of Olympia to pay off. According to the offer, bandits want to get a gift consisted of gold and silver coins. Offer also contains a list of restrictions: for each road it is known *g**i* — the smallest amount of gold and *s**i* — the smallest amount of silver coins that should be in the gift to stop robberies on the road. That is, if the gift contains *a* gold and *b* silver coins, then bandits will stop robberies on all the roads that *g**i*<=≤<=*a* and *s**i*<=≤<=*b*.

Unfortunately kingdom treasury doesn't contain neither gold nor silver coins, but there are Olympian tugriks in it. The cost of one gold coin in tugriks is *G*, and the cost of one silver coin in tugriks is *S*. King really wants to send bandits such gift that for any two cities there will exist a safe path between them. Your task is to find the minimal cost in Olympian tugriks of the required gift.

Input Specification:
The first line of the input contains two integers *N* and *M* (2<=≤<=*N*<=≤<=200, 1<=≤<=*M*<=≤<=50<=000) — the number of cities and the number of roads, respectively. The second line contains two integers *G* and *S* (1<=≤<=*G*,<=*S*<=≤<=109) — the prices of gold and silver coins in tugriks. The following *M* lines contain information about the offer. Each of the records in list is given as four integers *x**i*,<=*y**i*,<=*g**i*,<=*s**i*, where *x**i* and *y**i* are the numbers of cities that the road connects and *g**i*, *s**i* are minimal gold and silver coins requirements for the *i*-th road (1<=≤<=*x**i*,<=*y**i*<=≤<=*N*, 1<=≤<=*g**i*,<=*s**i*<=≤<=109). Cities are numbered from 1 to *N*. It is possible that there are more than one road between a pair of cities. It is possible that a road connects the city with itself.

Output Specification:
The output should contain the minimal cost of the gift in Olympian tugriks. If there is no gift that satisfies the given requirements output .

Demo Input:
['3 3\n2 1\n1 2 10 15\n1 2 4 20\n1 3 5 1\n']

Demo Output:
['30\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Queen of England has n trees growing in a row in her garden. At that, the i-th (1 ≤ i ≤ n) tree from the left has height a_{i} meters. Today the Queen decided to update the scenery of her garden. She wants the trees' heights to meet the condition: for all i (1 ≤ i < n), a_{i} + 1 - a_{i} = k, where k is the number the Queen chose.

Unfortunately, the royal gardener is not a machine and he cannot fulfill the desire of the Queen instantly! In one minute, the gardener can either decrease the height of a tree to any positive integer height or increase the height of a tree to any positive integer height. How should the royal gardener act to fulfill a whim of Her Majesty in the minimum number of minutes?


-----Input-----

The first line contains two space-separated integers: n, k (1 ≤ n, k ≤ 1000). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000) — the heights of the trees in the row. 


-----Output-----

In the first line print a single integer p — the minimum number of minutes the gardener needs. In the next p lines print the description of his actions. 

If the gardener needs to increase the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, then print in the corresponding line "+ j x". If the gardener needs to decrease the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, print on the corresponding line "- j x".

If there are multiple ways to make a row of trees beautiful in the minimum number of actions, you are allowed to print any of them.


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

Output
2
+ 3 2
- 4 1

Input
4 1
1 2 3 4

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree.  (Recall that a node is a leaf if and only if it has 0 children.)
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node.  It is guaranteed this sum fits into a 32-bit integer.
 
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

 
Constraints:

2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef has defined a new type of rooted tree - divisor tree. In this tree, every node has a positive integer written on it. It follows some rules:
The root can have any positive integer written on it.
Suppose a node has the integer A written on it, and suppose A has k proper divisors. [Note: Proper divisors of an integer are all its divisors except the integer itself. 1 has no proper divisor] Then this node will have exactly k child nodes, and each of A's proper divisors will be written on exactly one of the child nodes. For example, a node with number 12 written on it would have children with the numbers 1, 2, 3, 4, and 6 written on them.

You can observe that the nodes have 1 written on them, if and only if, they are leaves. 

The score of a path in this tree is defined as the sum of degrees of all of the nodes in the path. The Score of the tree is defined as the maximum score of a path from the root to one of the leaves.

You are given two integers A, B. You want to find the sum of Scores of all the divisor trees which have n written on their root, where A ≤ n ≤ B.

------ Input ------ 

The only line of the input contains two space separated integers A and B respectively.

------ Output ------ 

Output a single integer corresponding to the answer of the problem.

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

$1 ≤  A ≤ B  ≤ 10^{12}$ 
$ B - A  < 10^{5}$

------ Subtasks ------ 

Subtask #1 (10 points):
$1 ≤  A ≤ B  ≤ 50$

Subtask #2 (25 points):
$1 ≤  A ≤ B  ≤ 10^{6}$
$ B - A < 10^{5}$

Subtask #3 (25 points):
$  A = B  $

Subtask #4 (40 points):
$Original constraints.$ 

----- Sample Input 1 ------ 
11 12
----- Sample Output 1 ------ 
14
----- explanation 1 ------ 

----- Sample Input 2 ------ 
932451 935212
----- Sample Output 2 ------ 
101245
----- explanation 2 ------ 

Input 1.

Here we have, A = 11 and B = 12.

The Score of the divisor tree which has 12 written on its root is 12. This because the path 12 -> 6 -> 3 -> 1  (look at the figure below) has sum of the degrees of all nodes in it = 5 + 4 + 2 + 1 = 12. This is the maximum score of a path among all paths from root to the leaves. Hence, the Score of this tree is 12.

Note that in the figure, the nodes are denoted by (value written on it, degree of node), and the leaves are marked green.

You can find that the score of divisor tree which has 11 written on its root is 2. 

Hence, answer will be 12 + 2 = 14.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our friendly friend Pete is really a nice person, but he tends to be rather... Inappropriate.

And possibly loud, if given enough ethanol and free rein, so we ask you to write a function that should take its not always "clean" speech and cover as much as possible of it, in order not to offend some more sensible spirits.

For example, given an input like
```
What the hell am I doing here? And where is my wallet? PETE SMASH!
```
You are expected to turn it into something like:
```
W**t t*e h**l am i d***g h**e? A*d w***e is my w****t? P**e s***h!
```
In case you didn't figure out the rules yet: any words longer than 2 characters need to have its "inside" (meaning every character which is not the first or the last) changed into `*`;  as we do not want Pete to scream too much, every uppercase letter which is not at the beginning of the string or coming after a punctuation mark among [".","!","?"] needs to be put to lowercase; spaces and other punctuation marks can be ignored.

Conversely, you need to be sure that the start of each sentence has a capitalized word at the beginning. Sentences are divided by the aforementioned punctuation marks.

Finally, the function will take an additional parameter consisting of an array/list of allowed words (upper or lower case) which are not to be replaced (the match has to be case insensitive).

Extra cookies if you can do it all in some efficient way and/or using our dear regexes ;)

**Note:** Absolutely not related to [a certain codewarrior I know](http://www.codewars.com/users/petegarvin1) :p

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