vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.

Nam created a sequence a consisting of n (1 ≤ n ≤ 10^5) elements a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). A subsequence a_{i}_1, a_{i}_2, ..., a_{i}_{k} where 1 ≤ i_1 < i_2 < ... < i_{k} ≤ n is called increasing if a_{i}_1 < a_{i}_2 < a_{i}_3 < ... < a_{i}_{k}. An increasing subsequence is called longest if it has maximum length among all increasing subsequences. 

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups: group of all i such that a_{i} belongs to no longest increasing subsequences. group of all i such that a_{i} belongs to at least one but not every longest increasing subsequence. group of all i such that a_{i} belongs to every longest increasing subsequence. 

Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.


-----Input-----

The first line contains the single integer n (1 ≤ n ≤ 10^5) denoting the number of elements of sequence a.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index i belongs to.


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

Output
3

Input
4
1 3 2 5

Output
3223

Input
4
1 5 2 3

Output
3133



-----Note-----

In the second sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a_1, a_2, a_4} = {1, 3, 5} and {a_1, a_3, a_4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a_1, a_3, a_4} = {1, 2, 3}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This contest, AtCoder Beginner Contest, is abbreviated as ABC.
When we refer to a specific round of ABC, a three-digit number is appended after ABC. For example, ABC680 is the 680th round of ABC.
What is the abbreviation for the N-th round of ABC? Write a program to output the answer.

-----Constraints-----
 - 100 ≤ N ≤ 999

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

-----Output-----
Print the abbreviation for the N-th round of ABC.

-----Sample Input-----
100

-----Sample Output-----
ABC100

The 100th round of ABC is ABC100.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Four-digit palindromes start with `[1001,1111,1221,1331,1441,1551,1551,...]` and the number at position `2` is `1111`.  

You will be given two numbers `a` and `b`. Your task is to return the `a-digit` palindrome at position `b` if the palindromes were arranged in increasing order. 

Therefore, `palin(4,2) = 1111`, because that is the second element of the `4-digit` palindrome series.

More examples in the test cases. Good luck!

If you like palindrome Katas, please try:

[Palindrome integer composition](https://www.codewars.com/kata/599b1a4a3c5292b4cc0000d5)

[Life without primes](https://www.codewars.com/kata/59f8750ac374cba8f0000033)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This Christmas Santa gave Masha a magic picture and a pencil. The picture consists of n points connected by m segments (they might cross in any way, that doesn't matter). No two segments connect the same pair of points, and no segment connects the point to itself. Masha wants to color some segments in order paint a hedgehog. In Mashas mind every hedgehog consists of a tail and some spines. She wants to paint the tail that satisfies the following conditions:   Only segments already presented on the picture can be painted;  The tail should be continuous, i.e. consists of some sequence of points, such that every two neighbouring points are connected by a colored segment;  The numbers of points from the beginning of the tail to the end should strictly increase. 

Masha defines the length of the tail as the number of points in it. Also, she wants to paint some spines. To do so, Masha will paint all the segments, such that one of their ends is the endpoint of the tail. Masha defines the beauty of a hedgehog as the length of the tail multiplied by the number of spines. Masha wants to color the most beautiful hedgehog. Help her calculate what result she may hope to get.

Note that according to Masha's definition of a hedgehog, one segment may simultaneously serve as a spine and a part of the tail (she is a little girl after all). Take a look at the picture for further clarifications.


-----Input-----

First line of the input contains two integers n and m(2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — the number of points and the number segments on the picture respectively. 

Then follow m lines, each containing two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the numbers of points connected by corresponding segment. It's guaranteed that no two segments connect the same pair of points.


-----Output-----

Print the maximum possible value of the hedgehog's beauty.


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

Output
9

Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output
12



-----Note-----

The picture below corresponds to the first sample. Segments that form the hedgehog are painted red. The tail consists of a sequence of points with numbers 1, 2 and 5. The following segments are spines: (2, 5), (3, 5) and (4, 5). Therefore, the beauty of the hedgehog is equal to 3·3 = 9.

[Image]

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Currently Tiny is learning Computational Geometry. When trying to solve a problem called "The Closest Pair Of Points In The Plane", he found that a code which gave a wrong time complexity got Accepted instead of Time Limit Exceeded.

The problem is the follows. Given *n* points in the plane, find a pair of points between which the distance is minimized. Distance between (*x*1,<=*y*1) and (*x*2,<=*y*2) is .

The pseudo code of the unexpected code is as follows:

Here, *tot* can be regarded as the running time of the code. Due to the fact that a computer can only run a limited number of operations per second, *tot* should not be more than *k* in order not to get Time Limit Exceeded.

You are a great hacker. Would you please help Tiny generate a test data and let the code get Time Limit Exceeded?

Input Specification:
A single line which contains two space-separated integers *n* and *k* (2<=≤<=*n*<=≤<=2000, 1<=≤<=*k*<=≤<=109).

Output Specification:
If there doesn't exist such a data which let the given code get TLE, print "no solution" (without quotes); else print *n* lines, and the *i*-th line contains two integers *x**i*,<=*y**i* (|*x**i*|,<=|*y**i*|<=≤<=109) representing the coordinates of the *i*-th point.

The conditions below must be held:
 -  All the points must be distinct. -  |*x**i*|,<=|*y**i*|<=≤<=109. -  After running the given code, the value of *tot* should be larger than *k*.

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

Demo Output:
['0 0\n0 1\n1 0\n1 1\n', 'no solution\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Appleman and Toastman play a game. Initially Appleman gives one group of n numbers to the Toastman, then they start to complete the following tasks:  Each time Toastman gets a group of numbers, he sums up all the numbers and adds this sum to the score. Then he gives the group to the Appleman.  Each time Appleman gets a group consisting of a single number, he throws this group out. Each time Appleman gets a group consisting of more than one number, he splits the group into two non-empty groups (he can do it in any way) and gives each of them to Toastman. 

After guys complete all the tasks they look at the score value. What is the maximum possible value of score they can get?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 3·10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — the initial group that is given to Toastman.


-----Output-----

Print a single integer — the largest possible score.


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

Output
26

Input
1
10

Output
10



-----Note-----

Consider the following situation in the first example. Initially Toastman gets group [3, 1, 5] and adds 9 to the score, then he give the group to Appleman. Appleman splits group [3, 1, 5] into two groups: [3, 5] and [1]. Both of them should be given to Toastman. When Toastman receives group [1], he adds 1 to score and gives the group to Appleman (he will throw it out). When Toastman receives group [3, 5], he adds 8 to the score and gives the group to Appleman. Appleman splits [3, 5] in the only possible way: [5] and [3]. Then he gives both groups to Toastman. When Toastman receives [5], he adds 5 to the score and gives the group to Appleman (he will throws it out). When Toastman receives [3], he adds 3 to the score and gives the group to Appleman (he will throws it out). Finally Toastman have added 9 + 1 + 8 + 5 + 3 = 26 to the score. This is the optimal sequence of actions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are M job applicants and N jobs.  Each applicant has a subset of jobs that he/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Given a matrix G with M rows and N columns where G(i,j) denotes i^{th }applicant is interested in the j^{th }job. Find the maximum number of applicants who can get the job.
Example 1:
Input: 
M = 3, N = 5
G = {{1,1,0,1,1},{0,1,0,0,1},
{1,1,0,1,1}}
Output: 3
Explanation: There is one of the possible
assignment-
First applicant gets the 1st job.
Second applicant gets the 2nd job.
Third applicant gets the 4th job.
Example 2:
Input:
M = 6, N = 2
G = {{1,1},{0,1},{0,1},{0,1},
{0,1},{1,0}}
Output: 2
Explanation: There is one of the possible
assignment-
First applicant gets the 1st job.
Second applicant gets the 2nd job.
 
Your Task:
You don't need to read to print anything. Your task is to complete the function maximumMatch() which takes matrix G as input parameter and returns the maximum number of applicants who can get the job.
Expected Time Complexity: O(N^{3}).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N, M ≤ 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first r_{i} numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).

Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence a_{i} of length n and the description of each manager, that is value r_{i} and his favourite order. You are asked to speed up the process and determine how the final report will look like.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.

The second line contains n integers a_{i} (|a_{i}| ≤ 10^9) — the initial report before it gets to the first manager.

Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers t_{i} and r_{i} ($t_{i} \in \{1,2 \}$, 1 ≤ r_{i} ≤ n), meaning that the i-th manager sorts the first r_{i} numbers either in the non-descending (if t_{i} = 1) or non-ascending (if t_{i} = 2) order.


-----Output-----

Print n integers — the final report, which will be passed to Blake by manager number m.


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

Output
2 1 3 
Input
4 2
1 2 4 3
2 3
1 2

Output
2 4 1 3 


-----Note-----

In the first sample, the initial report looked like: 1 2 3. After the first manager the first two numbers were transposed: 2 1 3. The report got to Blake in this form.

In the second sample the original report was like this: 1 2 4 3. After the first manager the report changed to: 4 2 1 3. After the second manager the report changed to: 2 4 1 3. This report was handed over to Blake.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nexus 4.O is going to be organized by ASME, GLA University. Shubhanshu, Head of Finance Team is working for it. He has $N$ number of bills of different values as $a$$1$,$ a$$2$, $a$$3$…$a$$n$.
He is interested in a game in which one has to do the addition of the bills. But due to privacy concerns, he cannot share the details with others. 
He can only trust his best friend Avani with such a confidential thing. So, he asked her to play this game.
Rules of the game :
- Avani needs to answer $Q$ queries.
- Every $Q$$i$ query has 2 values $X$$i$ and $Y$$i$.
- Avani needs to find the sum of the values between $X$$i$ and $Y$$i$ (inclusive).
So, you need to help Avani in answering the $Q$ queries

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each test case contains the value $N$ and $Q$.
- The second line of each test case contains the $N$ space-separated values as $a$$1$,$ a$$2$, $a$$3$…$a$$n$.
- The next line of each test case containing $Q$ query with $X$$i$ and $Y$$i$.

-----Output:-----
For each test case, Print the total amount between $X$$i$ and $Y$$i$ for $Q$ number of queries.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^5$
- $1 \leq Q \leq 10^5$
- $1 \leq a$$i$$ \leq 10^9$

-----Subtasks (25 points) :-----
- $1 \leq N \leq 10^2$.
- $1 \leq Q \leq 10^2$.
- $1 \leq a$$i$$ \leq 10^5$.

-----Subtasks (25 points) :-----
- $1 \leq N \leq 10^3$.
- $1 \leq Q \leq 10^3$.
- $1 \leq a$$i$$ \leq 10^5$.

-----Subtasks (50 points) :-----
- $Original  Constraints$.

-----Sample Input:-----
1
8 3
1 2 3 4 5 6 7 8
2 3
1 6
5 8

-----Sample Output:-----
5
21
26

-----EXPLANATION:-----
$Q$$1$ : (2,3) 2+3=5
$Q$$2$ : (1,6) 1+2+3+4+5+6=21
$Q$$3$ : (5,8) 5+6+7+8=26

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gena doesn't like geometry, so he asks you to solve this problem for him.

A rectangle with sides parallel to coordinate axes contains n dots. Let's consider some point of the plane. Let's count the distances from this point to the given n points. Let's sort these numbers in the non-decreasing order. We'll call the beauty of the point the second element of this array. If there are two mimimum elements in this array, the beaty will be equal to this minimum.

Find the maximum beauty of a point inside the given rectangle.

Input

The first line contains three integers w, h, n (1 ≤ w, h ≤ 106, 2 ≤ n ≤ 1000) — the lengths of the rectangle sides and the number of points. Next n lines contain two integers xi, yi (0 ≤ xi ≤ w, 0 ≤ yi ≤ h) each — the coordinates of a point. It is possible that it will be coincident points.

Output

Print a single number — the maximum beauty of a point with the absolute or relative error of at most 10 - 9.

Examples

Input

5 5 4
0 0
5 0
0 5
5 5


Output

4.99999999941792340


Input

5 5 3
4 0
2 5
4 1


Output

5.65685424744772010

Note

The point which beauty we need to find must have coordinates (x, y), where 0 ≤ x ≤ w, 0 ≤ y ≤ h. Some of the n points can coincide.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
A group of university students wants to get to the top of a mountain to have a picnic there. For that they decided to use a cableway.

A cableway is represented by some cablecars, hanged onto some cable stations by a cable. A cable is scrolled cyclically between the first and the last cable stations (the first of them is located at the bottom of the mountain and the last one is located at the top). As the cable moves, the cablecar attached to it move as well.

The number of cablecars is divisible by three and they are painted three colors: red, green and blue, in such manner that after each red cablecar goes a green one, after each green cablecar goes a blue one and after each blue cablecar goes a red one. Each cablecar can transport no more than two people, the cablecars arrive with the periodicity of one minute (i. e. every minute) and it takes exactly 30 minutes for a cablecar to get to the top.

All students are divided into three groups: *r* of them like to ascend only in the red cablecars, *g* of them prefer only the green ones and *b* of them prefer only the blue ones. A student never gets on a cablecar painted a color that he doesn't like,

The first cablecar to arrive (at the moment of time 0) is painted red. Determine the least time it will take all students to ascend to the mountain top.

Input Specification:
The first line contains three integers *r*, *g* and *b* (0<=≤<=*r*,<=*g*,<=*b*<=≤<=100). It is guaranteed that *r*<=+<=*g*<=+<=*b*<=&gt;<=0, it means that the group consists of at least one student.

Output Specification:
Print a single number — the minimal time the students need for the whole group to ascend to the top of the mountain.

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

Demo Output:
['34', '33']

Note:
Let's analyze the first sample.

At the moment of time 0 a red cablecar comes and one student from the *r* group get on it and ascends to the top at the moment of time 30.

At the moment of time 1 a green cablecar arrives and two students from the *g* group get on it; they get to the top at the moment of time 31.

At the moment of time 2 comes the blue cablecar and two students from the *b* group get on it. They ascend to the top at the moment of time 32.

At the moment of time 3 a red cablecar arrives but the only student who is left doesn't like red and the cablecar leaves empty.

At the moment of time 4 a green cablecar arrives and one student from the *g* group gets on it. He ascends to top at the moment of time 34.

Thus, all the students are on the top, overall the ascension took exactly 34 minutes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

For a positive integer $n$, we call a permutation $p$ of length $n$ good if the following condition holds for every pair $i$ and $j$ ($1 \le i \le j \le n$) —   $(p_i \text{ OR } p_{i+1} \text{ OR } \ldots \text{ OR } p_{j-1} \text{ OR } p_{j}) \ge j-i+1$, where $\text{OR}$ denotes the bitwise OR operation. 

In other words, a permutation $p$ is good if for every subarray of $p$, the $\text{OR}$ of all elements in it is not less than the number of elements in that subarray. 

Given a positive integer $n$, output any good permutation of length $n$. We can show that for the given constraints such a permutation always exists.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first and only line of every test case contains a single integer $n$ ($1 \le n \le 100$).


-----Output-----

For every test, output any good permutation of length $n$ on a separate line. 


-----Example-----
Input
3
1
3
7

Output
1
3 1 2
4 3 5 2 7 1 6



-----Note-----

For $n = 3$, $[3,1,2]$ is a good permutation. Some of the subarrays are listed below.   $3\text{ OR }1 = 3 \geq 2$ $(i = 1,j = 2)$  $3\text{ OR }1\text{ OR }2 = 3 \geq 3$ $(i = 1,j = 3)$  $1\text{ OR }2 = 3 \geq 2$ $(i = 2,j = 3)$  $1 \geq 1$ $(i = 2,j = 2)$ 

Similarly, you can verify that $[4,3,5,2,7,1,6]$ is also good.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
SHIN-CHAN and KAZAMA grew up to become very good friends. They went to high school together and shared the same bench in class. In one of the maths classes, while the teacher was teaching the class about the XOR (exclusive OR) operator, the two of them were busy thinking of SHIZUKA (both of them had a big crush on her since childhood days).
The teacher saw this and decided to punish them by giving them a punishment for not paying attention in class. As a punishment, he gave them a very difficult assignment in which there were several questions on a sequence of given numbers. 

Given an array of integers A [ 1 - N ] , they had to answer a number of queries. Each query had three integers l , r , and X. They had to find a number Z in the array in range A[ l ], A[ l + 1 ], .... A[ r ]. Z for a range and integer X is defined as  a number A [ i ] ( l  ≤ i  ≤ r) such that the value of Z when taken XOR with X comes out to be lesser than that for any other element in the given range. 

As the two of them did not know anything about XOR and were busy planning a surprise for SHIZUKA's b'day, help them finding the answers of the given queries. The answer to each query is the number Z and the number of times it occurs in the given range.

INPUT : 

The first line of the input contains an integer N. The next line contains N space separated integers, the elements of the array A. The third line of the input contains Q the number of queries. next Q lines contains three space separated integers l, r and X (description of a particular query) .

OUTPUT : 

For each query, output the number Z and the number of times it occurs in the range l to r separated by a space.

CONSTRAINTS :

1 ≤ N ≤ 10^6

1 ≤ X,A[i] ≤ 10^9

1 ≤ l ≤ r ≤ N

1 ≤ Q ≤ 50000

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

SAMPLE OUTPUT
1 1
3 1
3 2
4 1
5 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easier version of the next problem. The difference is only in constraints.

You are given a rectangular $n \times m$ matrix $a$. In one move you can choose any column and cyclically shift elements in this column. You can perform this operation as many times as you want (possibly zero). You can perform this operation to a column multiple times.

After you are done with cyclical shifts, you compute for every row the maximal value in it. Suppose that for $i$-th row it is equal $r_i$. What is the maximal possible value of $r_1+r_2+\ldots+r_n$?


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 40$), the number of test cases in the input.

The first line of each test case contains integers $n$ and $m$ ($1 \le n \le 4$, $1 \le m \le 100$) — the number of rows and the number of columns in the given matrix $a$. 

Each of the following $n$ lines contains $m$ integers, the elements of $a$ ($1 \le a_{i, j} \le 10^5$).


-----Output-----

Print $t$ integers: answers for all test cases in the order they are given in the input.


-----Example-----
Input
2
2 3
2 5 7
4 2 4
3 6
4 1 5 2 10 4
8 6 6 4 9 10
5 4 9 5 8 7

Output
12
29



-----Note-----

In the first test case, you can shift the third column down by one, this way there will be $r_1 = 5$ and $r_2 = 7$.

In the second case you can don't rotate anything at all, this way there will be $r_1 = r_2 = 10$ and $r_3 = 9$.

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