vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Little Artem has invented a time machine! He could go anywhere in time, but all his thoughts of course are with computer science. He wants to apply this time machine to a well-known data structure: multiset.

Artem wants to create a basic multiset of integers. He wants these structure to support operations of three types:

  Add integer to the multiset. Note that the difference between set and multiset is that multiset may store several instances of one integer.  Remove integer from the multiset. Only one instance of this integer is removed. Artem doesn't want to handle any exceptions, so he assumes that every time remove operation is called, that integer is presented in the multiset.  Count the number of instances of the given integer that are stored in the multiset. 

But what about time machine? Artem doesn't simply apply operations to the multiset one by one, he now travels to different moments of time and apply his operation there. Consider the following example.

  First Artem adds integer 5 to the multiset at the 1-st moment of time.  Then Artem adds integer 3 to the multiset at the moment 5.  Then Artem asks how many 5 are there in the multiset at moment 6. The answer is 1.  Then Artem returns back in time and asks how many integers 3 are there in the set at moment 4. Since 3 was added only at moment 5, the number of integers 3 at moment 4 equals to 0.  Then Artem goes back in time again and removes 5 from the multiset at moment 3.  Finally Artyom asks at moment 7 how many integers 5 are there in the set. The result is 0, since we have removed 5 at the moment 3. 

Note that Artem dislikes exceptions so much that he assures that after each change he makes all delete operations are applied only to element that is present in the multiset. The answer to the query of the third type is computed at the moment Artem makes the corresponding query and are not affected in any way by future changes he makes.

Help Artem implement time travellers multiset.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of Artem's queries.

Then follow n lines with queries descriptions. Each of them contains three integers a_{i}, t_{i} and x_{i} (1 ≤ a_{i} ≤ 3, 1 ≤ t_{i}, x_{i} ≤ 10^9) — type of the query, moment of time Artem travels to in order to execute this query and the value of the query itself, respectively. It's guaranteed that all moments of time are distinct and that after each operation is applied all operations of the first and second types are consistent.


-----Output-----

For each ask operation output the number of instances of integer being queried at the given moment of time.


-----Examples-----
Input
6
1 1 5
3 5 5
1 2 5
3 6 5
2 3 5
3 7 5

Output
1
2
1

Input
3
1 1 1
2 2 1
3 3 1

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have two arrays of integers, $V=\{V_1,V_2,\ldots,V_N\}$ and $P=\{P_1,P_2,\ldots,P_N\}$, where both have $N$ number of elements. Consider the following function:

score = 0

int Go(step, energy) {
    if (step == N) {
        score += V[step];
        return (score);
    }
    else {
        int way = random(1, 2);
        if (way == 1) {
            score += V[step];
        }
        else {
            energy = P[step];
        }
        if (energy > 0) {
            Go(step + 1, energy - 1);
        }
        else {
            KillTheWorld();
        }
    }
}

What is the maximum possible value of score that we can get in the end, if we call $Go(1,0)$?. 

Note that the function should never invoke KillTheWorld function. And $\textit{random(1,2)}$ generates a random integer from set  [1, 2]. 

It is guaranteed there will be a solution that wont kill the world.

Input Format

The first line contains an integer N. Each of the following N lines contains a pair of integers. The i-th line contains a pair of numbers, $V_i,P_i$, separated by space.  

Constraints

$1\leq N\leq5\times10^5$ 

$0\leq V_i\leq10^9$ 

$0\leq P_i\leq10^5$  

Output Format

Derive the maximum score given by return (score);.

Sample Input
4
4 2
0 2
4 0
3 4

Sample Output
7

Explanation

In the best case, the first and second function call in Go variable $\textbf{way}$ will take value 2, while in the other calls it will be equal to 1 then the final score will be equal to the value of 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $LCM(x, y)$ be the minimum positive integer that is divisible by both $x$ and $y$. For example, $LCM(13, 37) = 481$, $LCM(9, 6) = 18$.

You are given two integers $l$ and $r$. Find two integers $x$ and $y$ such that $l \le x < y \le r$ and $l \le LCM(x, y) \le r$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10000$) — the number of test cases.

Each test case is represented by one line containing two integers $l$ and $r$ ($1 \le l < r \le 10^9$).


-----Output-----

For each test case, print two integers:

  if it is impossible to find integers $x$ and $y$ meeting the constraints in the statement, print two integers equal to $-1$;  otherwise, print the values of $x$ and $y$ (if there are multiple valid answers, you may print any of them). 


-----Example-----
Input
4
1 1337
13 69
2 4
88 89

Output
6 7
14 21
2 4
-1 -1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that accepts two square matrices (`N x N` two dimensional arrays), and return the sum of the two. Both matrices being passed into the function will be of size `N x N` (square), containing only integers.

How to sum two matrices:

Take each cell `[n][m]` from the first matrix, and add it with the same `[n][m]` cell from the second matrix. This will be cell `[n][m]` of the solution matrix.

Visualization: 
```
|1 2 3|     |2 2 1|     |1+2 2+2 3+1|     |3 4 4|
|3 2 1|  +  |3 2 3|  =  |3+3 2+2 1+3|  =  |6 4 4|
|1 1 1|     |1 1 3|     |1+1 1+1 1+3|     |2 2 4|
```

## Example

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Since Sonya has just learned the basics of matrices, she decided to play with them a little bit.

Sonya imagined a new type of matrices that she called rhombic matrices. These matrices have exactly one zero, while all other cells have the Manhattan distance to the cell containing the zero. The cells with equal numbers have the form of a rhombus, that is why Sonya called this type so.

The Manhattan distance between two cells ($x_1$, $y_1$) and ($x_2$, $y_2$) is defined as $|x_1 - x_2| + |y_1 - y_2|$. For example, the Manhattan distance between the cells $(5, 2)$ and $(7, 1)$ equals to $|5-7|+|2-1|=3$. [Image] Example of a rhombic matrix. 

Note that rhombic matrices are uniquely defined by $n$, $m$, and the coordinates of the cell containing the zero.

She drew a $n\times m$ rhombic matrix. She believes that you can not recreate the matrix if she gives you only the elements of this matrix in some arbitrary order (i.e., the sequence of $n\cdot m$ numbers). Note that Sonya will not give you $n$ and $m$, so only the sequence of numbers in this matrix will be at your disposal.

Write a program that finds such an $n\times m$ rhombic matrix whose elements are the same as the elements in the sequence in some order.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^6$) — the number of cells in the matrix.

The second line contains $t$ integers $a_1, a_2, \ldots, a_t$ ($0\leq a_i< t$) — the values in the cells in arbitrary order.


-----Output-----

In the first line, print two positive integers $n$ and $m$ ($n \times m = t$) — the size of the matrix.

In the second line, print two integers $x$ and $y$ ($1\leq x\leq n$, $1\leq y\leq m$) — the row number and the column number where the cell with $0$ is located.

If there are multiple possible answers, print any of them. If there is no solution, print the single integer $-1$.


-----Examples-----
Input
20
1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4

Output
4 5
2 2

Input
18
2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1

Output
3 6
2 3

Input
6
2 1 0 2 1 2

Output
-1



-----Note-----

You can see the solution to the first example in the legend. You also can choose the cell $(2, 2)$ for the cell where $0$ is located. You also can choose a $5\times 4$ matrix with zero at $(4, 2)$.

In the second example, there is a $3\times 6$ matrix, where the zero is located at $(2, 3)$ there.

In the third example, a solution does not exist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mary Thomas has a number of sheets of squared paper. Some of squares are painted either in black or some colorful color (such as red and blue) on the front side. Cutting off the unpainted part, she will have eight opened-up unit cubes. A unit cube here refers to a cube of which each face consists of one square.

She is going to build those eight unit cubes with the front side exposed and then a bicube with them. A bicube is a cube of the size 2 × 2 × 2, consisting of eight unit cubes, that satisfies the following conditions:

* faces of the unit cubes that comes to the inside of the bicube are all black;
* each face of the bicube has a uniform colorful color; and
* the faces of the bicube have colors all different.



Your task is to write a program that reads the specification of a sheet of squared paper and decides whether a bicube can be built with the eight unit cubes resulting from it.



Input

The input contains the specification of a sheet. The first line contains two integers H and W, which denote the height and width of the sheet (3 ≤ H, W ≤ 50). Then H lines follow, each consisting of W characters. These lines show the squares on the front side of the sheet. A character represents the color of a grid: alphabets and digits ('A' to 'Z', 'a' to 'z', '0' to '9') for colorful squares, a hash ('#') for a black square, and a dot ('.') for an unpainted square. Each alphabet or digit denotes a unique color: squares have the same color if and only if they are represented by the same character.

Each component of connected squares forms one opened-up cube. Squares are regarded as connected when they have a common edge; those just with a common vertex are not.

Output

Print "Yes" if a bicube can be built with the given sheet; "No" otherwise.

Examples

Input

3 40
.a....a....a....a....f....f....f....f...
#bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.#be#.
.#....#....#....#....#....#....#....#...


Output

Yes


Input

3 40
.a....a....a....a....f....f....f....f...
bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.#be#.
.#....#....#....#....#....#....#....#...


Output

Yes


Input

5 35
.a....a....a....a....f....f....f...
bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.
.#..f.#....#....#....#....#....#...
..e##..............................
.b#................................


Output

Yes


Input

3 40
.a....a....a....a....f....f....f....f...
bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.#eb#.
.#....#....#....#....#....#....#....#...


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have recently found an array of N non-negative integers. You like it a lot but unfortunately it is too long. So now you are going to divide in exactly K blocks and each of the blocks should  consist of several consecutive elements of the array.

There are many ways to divide the array. You wish to minimize the value X calculated in the following way :
Let's suppose that sums of the elements in blocks are S1, S2 ... Sk correspondingly. X = sum (Si - Sj)^2  through all i, j from 1 to K and i ≤ j.

Before dividing the array you are interested in the exact value of X. So the only thing you have to do is to find it.

Input
The first line contains two space-separated integers N and K.
The second line contains N space-separated integers - your array.

Output
Output one integer - answer for the question.

Constraints
N ≤ 500, K ≤ 300, K ≤ N
Each element of the array is an integer from  0 to 10^5
N ≤ 20 in 40% of the test data.

SAMPLE INPUT
7 3
1 7 3 5 1 4 4
 

SAMPLE OUTPUT
2

Explanation

The best way is to divide the array in such 3 groups : (1, 7), (3, 5), (1, 4, 4) with Si correspondingly 8, 8, 9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Donald is playing a game of cards against his cousin Gladstone. Each round proceeds as follows:
 - Donald chooses an (integer) amount of coins and both of the cousins puts that many coins in the pot.
 - The cards are dealt.
 - The game is played.
 - The player who won gets all the coins in the pot.

This continues until either $n$ rounds have been played, or until one of the players have run out of coins.

Unfortunately, Gladstone is quite possibly the luckiest person alive. As his luck would let him win every single round, the cousins’ game would surely lead to a quick economic demise for Donald. To balance the situation, Donald has hired his nephews to distract Gladstone a few times, by giving him a prank phone call between steps 2 and 3 above. Every round in which Gladstone is distracted, Donald is able to look at Gladstone’s cards and can with this extra knowledge and some card swapping be certain to win the round.

But things are still not easy for Donald. Gladstone will not be distracted during every round, and Donald has no way of knowing in advance during which rounds Gladstone will be distracted, which effectively means that Gladstone’s luck will take its course and do its best to cheat Donald out of his hard-earned coins. Is it still possible for Donald to come out richer from this experience, by being careful in how he chooses his bets?

Note that in step 2, Donald can never bet more coins than he has, or more coins than Gladstone has.

-----Input-----
The input consists of four integers $d$, $g$, $n$, and $k$, where $1 \le d, g \le 1000$ are the amounts of coins Donald and Gladstone initially have, $1 \le n \le 50$ is the number of rounds they will play, and $0 \le k \le n$ is the number of rounds during which Gladstone will be distracted.

-----Output-----
Write a single line containing an integer $M$ giving the maximum amount of coins Donald can be certain to have at the end of the game.

-----Examples-----
Sample Input 1:
2 10 3 2
Sample Output 1:
4

Sample Input 2:
10 10 5 0
Sample Output 2:
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mishka started participating in a programming contest. There are $n$ problems in the contest. Mishka's problem-solving skill is equal to $k$.

Mishka arranges all problems from the contest into a list. Because of his weird principles, Mishka only solves problems from one of the ends of the list. Every time, he chooses which end (left or right) he will solve the next problem from. Thus, each problem Mishka solves is either the leftmost or the rightmost problem in the list.

Mishka cannot solve a problem with difficulty greater than $k$. When Mishka solves the problem, it disappears from the list, so the length of the list decreases by $1$. Mishka stops when he is unable to solve any problem from any end of the list.

How many problems can Mishka solve?


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \le n, k \le 100$) — the number of problems in the contest and Mishka's problem-solving skill.

The second line of input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$), where $a_i$ is the difficulty of the $i$-th problem. The problems are given in order from the leftmost to the rightmost in the list.


-----Output-----

Print one integer — the maximum number of problems Mishka can solve.


-----Examples-----
Input
8 4
4 2 3 1 5 1 6 4

Output
5

Input
5 2
3 1 2 1 3

Output
0

Input
5 100
12 34 55 43 21

Output
5



-----Note-----

In the first example, Mishka can solve problems in the following order: $[4, 2, 3, 1, 5, 1, 6, 4] \rightarrow [2, 3, 1, 5, 1, 6, 4] \rightarrow [2, 3, 1, 5, 1, 6] \rightarrow [3, 1, 5, 1, 6] \rightarrow [1, 5, 1, 6] \rightarrow [5, 1, 6]$, so the number of solved problems will be equal to $5$.

In the second example, Mishka can't solve any problem because the difficulties of problems from both ends are greater than $k$.

In the third example, Mishka's solving skill is so amazing that he can solve all the problems.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mike is the president of country What-The-Fatherland. There are *n* bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to *n* from left to right. *i*-th bear is exactly *a**i* feet high. 

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.

Mike is a curious to know for each *x* such that 1<=≤<=*x*<=≤<=*n* the maximum strength among all groups of size *x*.

Input Specification:
The first line of input contains integer *n* (1<=≤<=*n*<=≤<=2<=×<=105), the number of bears.

The second line contains *n* integers separated by space, *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109), heights of bears.

Output Specification:
Print *n* integers in one line. For each *x* from 1 to *n*, print the maximum strength among all groups of size *x*.

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

Demo Output:
['6 4 4 3 3 2 2 1 1 1 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of stick lengths, use $3$ of them to construct a non-degenerate triangle with the maximum possible perimeter. Return an array of the lengths of its sides as $3$ integers in non-decreasing order.

If there are several valid triangles having the maximum perimeter: 

Choose the one with the longest maximum side. 
If more than one has that maximum, choose from them the one with the longest minimum side. 
If more than one has that maximum as well, print any one them.

If no non-degenerate triangle exists, return $\left[{-1}\right]$.

Example 

$sticks=[1,2,3,4,5,10]$   

The triplet $(1,2,3)$ will not form a triangle.  Neither will $(4,5,10)$ or $(2,3,5)$, so the problem is reduced to $(2,3,4)$ and $(3,4,5)$.  The longer perimeter is $3+4+5=12$.  

Function Description  

Complete the maximumPerimeterTriangle function in the editor below.  

maximumPerimeterTriangle has the following parameter(s):  

int sticks[n]: the lengths of sticks available   

Returns   

int[3] or int[1]:  the side lengths of the chosen triangle in non-decreasing order or -1    

Input Format

The first line contains single integer $n$, the size of array $sticks$. 

The second line contains $n$ space-separated integers $sticks[i]$, each a stick length.

Constraints

$3\leq n\leq50$
$1\leq sticks[i]\leq10^9$

Sample Input 0
5
1 1 1 3 3

Sample Output 0
1 3 3

Explanation 0

There are $2$ possible unique triangles: 

$(1,1,1)$ 
$(1,3,3)$

The second triangle has the largest perimeter, so we print its side lengths on a new line in non-decreasing order.

Sample Input 1
3
1 2 3

Sample Output 1
-1

Explanation 1

The triangle $(1,2,3)$ is degenerate and thus can't be constructed, so we print -1 on a new line.

Sample Input 2
6
1 1 1 2 3 5

Sample Output 2
1 1 1

Explanation 2

The triangle (1,1,1) is the only valid triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the tangent lines between a point $p$ and a circle $c$.

Constraints

* $-1,000 \leq px, py, cx, cy \leq 1,000$
* $1 \leq r \leq 1,000$
* Distance between $p$ and the center of $c$ is greater than the radius of $c$.

Input

The input is given in the following format.

$px \; py$
$cx \; cy \; r$

$px$ and $py$ represents the coordinate of the point $p$. $cx$, $cy$ and $r$ represents the center coordinate and radius of the circle $c$ respectively. All input values are given in integers.

Output

Print coordinates of the tangent points on the circle $c$ based on the following rules.

* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.00001.

Examples

Input

0 0
2 2 2


Output

0.0000000000 2.0000000000
2.0000000000 0.0000000000


Input

-3 0
2 2 2


Output

0.6206896552 3.4482758621
2.0000000000 0.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is time again for the annual International Convention for Phonetic Communication. Because there are attendees from all over the world, and they do not all speak the same languages, the organizers have hired translators to help out.

To thank the translators at the end of the conference for their hard work, the organizers want to arrange a dinner at a nice local restaurant. However, the restaurant only has small, two person tables, hence the translators will have to be divided into pairs. As the organizers would like the translators to have a nice evening, they prefer that two translators sitting at the same table are both able to speak the same language. Write a program to help the organizers determine a way to match up the translators in pairs, so that each of the translators speaks a language that the other also speaks.

-----Input-----
The first line contains two numbers $N$ and $M$, the number of languages spoken at the convention, and the number of hired translators respectively ($2 \leq N \leq 100$, $1 \leq M \leq 200$).

The following $M$ lines each describe a translator. Each of these lines contains two integers specifying the two languages that the translator speaks. Languages are identified by integers in the range $[0,N-1]$.

Translators are identified by integers in the range $[0,M-1]$. Translators are listed in order of increasing identifier (i.e. the first listed translator has identifier $0$).

There are no two translators who both speak the same two languages. Translators have been chosen such that any two languages spoken at the conference can be translated into one another, although it may take several translators.

-----Output-----
If it is possible to match up all translators such that each pair speaks a common language, output a possible matching: print $M/2$ lines, each line containing the two identifiers of a pair of matched translators. The pairs, as well as the translators within a pair, may be listed in any order.

There may be multiple possible matchings. In that case, print any one of them.

If it is not possible to match up all translators, output a single line containing the word “impossible”.

-----Examples-----
Sample Input:
5 6
0 1
0 2
1 3
2 3
1 2
4 3
Sample Output:
5 3
1 0
2 4

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