vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array nums of size n and q queries. Now for each query of the form l, r and k, output the kth smallest number in sub-array between l and r.
 
Example 1:
Input: nums = {4, 1, 2, 2, 3},
Query = {{1, 5, 2}, {3, 5, 3}}
Output: {2, 3}
Explanation: For the 1st query 2nd smallest in
[1, 5] is 2. For the 2nd query 3rd smallest in
[3, 5] is 3.
Example 2:
Input: nums = {1, 2, 3, 4, 5},
Query = {{2, 5, 1}}
Output: {2}
Explanation: The 1st smallest in [2, 5] is 2.
 
Your Task:
You don't need to read or print anyhting. Your Task is to complete the function FindQuery() which takes nums and Query as input parameter and returns a list containing kth smallest for every query.
 
Expected Time Complexity: O(nlog(n))
Expected Space Complexity: O(n)
 
Constraints:
1 <= n <= 15000
1 <= nums[i] <= n
1 <= no. of queries <= 10^{4}
1 <= l <= r <= n
1 <= k <= r-l+1

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

There are $ N $ balls, each with its own color and value.
There are $ C $ types of ball colors from $ 1 $ to $ C $, and each color has an upper limit on the number of balls that can be selected.
Maximize the total value you get when choosing at most $ M $ balls in total.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq M \ leq N \ leq 10 ^ 5 $
* $ 1 \ leq C \ leq 10 ^ 5 $
* $ 0 \ leq l_i \ leq N $
* $ 1 \ leq c_i \ leq C $
* $ 1 \ leq w_i \ leq 1000 $

Input

The input is given in the following format.


$ N $ $ M $ $ C $
$ l_1 $ $ l_2 $ ... $ l_C $
$ c_1 $ $ w_1 $
$ c_2 $ $ w_2 $
...
$ c_N $ $ w_N $


All inputs are given as integers.
$ N $, $ M $, $ C $ are given on the first line, separated by blanks.
On the second line, the upper limit of the number of balls that can be selected for the color $ i $ ($ 1 \ leq i \ leq C $) is given, separated by blanks.
The color $ c_i $ of the ball $ i $ and the value $ w_i $ ($ 1 \ leq i \ leq N $) are given in the third and subsequent lines of $ N $, separated by blanks.

Output

Output the maximum value you can get on one line.

Examples

Input

3 3 2
1 1
1 1
1 100
2 10


Output

110


Input

3 3 3
1 0 1
1 1
2 100
3 1


Output

2


Input

22 7 26
11 14 15 3 11 7 16 17 1 4 2 19 4 14 16 16 3 13 17 12 7 11 2 20 12 22
6 10
1 3
13 1
16 5
4 1
20 7
18 4
26 6
9 1
12 2
21 1
21 7
18 1
14 5
24 5
6 1
3 1
2 5
21 2
7 6
10 9
15 7


Output

52

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An eccentric coach asks players on the team to line up alphabetically at the start of practice. The coach does not tell the players whether they need to line up in increasing or decreasing order, so they guess. If they guess wrong, the coach makes them run laps before practice. Given a list of names, you are to determine if the list is in increasing alphabetical order, decreasing alphabetical order or neither.

-----Input-----
The input consists of a single test case. The first line will contain the number $N$ of people on the team ($2 \leq N \leq 20$). Following that are $N$ lines, each containing the name of one person. A name will be at least two characters and at most $12$ characters in length and will consist only of capital letters, and with no white spaces (sorry BILLY BOB and MARY JOE). Duplicates names will not be allowed on a team.

-----Output-----
Output a single word: INCREASING if the list is in increasing alphabetical order, DECREASING if it is in decreasing alphabetical order, and otherwise NEITHER.

-----Examples-----
Sample Input 1:
5
JOE
BOB
ANDY
AL
ADAM
Sample Output 1:
DECREASING

Sample Input 2:
11
HOPE
ALI
BECKY
JULIE
MEGHAN
LAUREN
MORGAN
CARLI
MEGAN
ALEX
TOBIN
Sample Output 2:
NEITHER

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have m = n·k wooden staves. The i-th stave has length a_{i}. You have to assemble n barrels consisting of k staves each, you can use any k staves to construct a barrel. Each stave must belong to exactly one barrel.

Let volume v_{j} of barrel j be equal to the length of the minimal stave in it. [Image] 

You want to assemble exactly n barrels with the maximal total sum of volumes. But you have to make them equal enough, so a difference between volumes of any pair of the resulting barrels must not exceed l, i.e. |v_{x} - v_{y}| ≤ l for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.

Print maximal total sum of volumes of equal enough barrels or 0 if it's impossible to satisfy the condition above.


-----Input-----

The first line contains three space-separated integers n, k and l (1 ≤ n, k ≤ 10^5, 1 ≤ n·k ≤ 10^5, 0 ≤ l ≤ 10^9).

The second line contains m = n·k space-separated integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^9) — lengths of staves.


-----Output-----

Print single integer — maximal total sum of the volumes of barrels or 0 if it's impossible to construct exactly n barrels satisfying the condition |v_{x} - v_{y}| ≤ l for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.


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

Output
7

Input
2 1 0
10 10

Output
20

Input
1 2 1
5 2

Output
2

Input
3 2 1
1 2 3 4 5 6

Output
0



-----Note-----

In the first example you can form the following barrels: [1, 2], [2, 2], [2, 3], [2, 3].

In the second example you can form the following barrels: [10], [10].

In the third example you can form the following barrels: [2, 5].

In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array a_{i} either with a_{i} + x or with a_{i} - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. $\prod_{i = 1}^{n} a_{i}$) can reach, if Maxim would apply no more than k operations to it. Please help him in that.


-----Input-----

The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 10^9) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers a_1, a_2, ..., a_{n} ($|a_{i}|\leq 10^{9}$) — the elements of the array found by Maxim.


-----Output-----

Print n integers b_1, b_2, ..., b_{n} in the only line — the array elements after applying no more than k operations to the array. In particular, $a_{i} \equiv b_{i} \operatorname{mod} x$ should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.


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

Output
5 4 3 5 -1 

Input
5 3 1
5 4 3 5 5

Output
5 4 0 5 5 

Input
5 3 1
5 4 4 5 5

Output
5 1 4 5 5 

Input
3 2 7
5 4 2

Output
5 11 -5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 
The staff of one of the most famous ChefLand's restaurants have just received the news! A delegation from the neighbouring country is going to visit the restaurant. The staff want to make this visit exciting and pleasant. Lucy is also a member of the staff and among all the things that the staff want to do, her assignment is to arrange the flowers on the tables.
Generally, there are 26 kinds of flowers, a small latin letter corresponds to a single kind. Equal letters correspond to equal kinds. Different letters correspond to different kinds. According to the old ChefLand tradition, one can make a bouquet from some flowers only if it is a substring of some magic string T. ChefLands make bouquets in such a manner that the order of flowers in them is important. The restaurant has a tradition to decorate a single table with N, not necessary different, bouquets. Their order matters.
Some decorations look really similar. Generally, two arrangements (let's call them A and B) are similar if B is a cyclic shift of A, or B is a reversed cyclic shift of A. For example the sequence ("aba", "c", "b") is a cyclic shift of a sequence ("b", "aba", "c"), and the sequence ("c", "b", "a", "e", "d") is a reversed cyclic shift of a sequence ("a", "b", "c", "d", "e").
Now Lucy thinks that the most beautiful bouquets are "symmetric" ones. The bouquet is "symmetric" if the string that corresponds to the arrangement of flowers in it is a palindrome (it reads from left to right the same as from right to left). 
So, she thinks that the decoration of the table will be especially beautiful if all the bouquets in it are "symmetric". But then, Lucy had realized that the number of such decorations of the tables can be less than the number of guests. She doesn't want to decorate two tables in a similar manner, so she would like to know the number of distinct  decorations such that no two tables looks similar.

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

The first line of input consists of a single string T.

The second line of input consists of a single integer N.

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

Output the number of distinct decorations.

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

1 ≤ |T| ≤ 100000;

1 ≤ N ≤ 600;

String T consists only of lowercase English letters.

------ Example ------ 

Input:
aba
4

Output:
21

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer -3.
 
Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
 

Constraints:

The input must be a binary string of length 32.
 
Follow up: If this function is called many times, how would you optimize it?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Because my other two parts of the serie were pretty well received I decided to do another part.

Puzzle Tiles

You will get two Integer n (width) and m (height) and your task is to draw following pattern. Each line is seperated with '\n'.


Both integers are equal or greater than 1. No need to check for invalid parameters.
There are no whitespaces at the end of each line.

e.g.:


 

                                       \_( )\_\_ \_( )\_\_ \_( )\_\_ \_( )\_\_
                                     \_|     \_|     \_|     \_|     \_|
                                    (\_   \_ (\_   \_ (\_   \_ (\_   \_ (\_
                                     |\_\_( )\_|\_\_( )\_|\_\_( )\_|\_\_( )\_|
                                     |\_     |\_     |\_     |\_     |\_
             puzzleTiles(4,3)=>       \_) \_   \_) \_   \_) \_   \_) \_   \_)
                                     |\_\_( )\_|\_\_( )\_|\_\_( )\_|\_\_( )\_|
                                     \_|     \_|     \_|     \_|     \_|
                                    (\_   \_ (\_   \_ (\_   \_ (\_   \_ (\_
                                     |\_\_( )\_|\_\_( )\_|\_\_( )\_|\_\_( )\_|
                                     


For more informations take a look in the test cases!


 Serie: ASCII Fun

ASCII Fun #1: X-Shape
ASCII Fun #2: Funny Dots
ASCII Fun #3: Puzzle Tiles
ASCII Fun #4: Build a pyramid

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time l_{i} and the finish time r_{i} (l_{i} ≤ r_{i}).

Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.


-----Input-----

The first line contains integer number n (1 ≤ n ≤ 5·10^5) — number of orders. The following n lines contain integer values l_{i} and r_{i} each (1 ≤ l_{i} ≤ r_{i} ≤ 10^9).


-----Output-----

Print the maximal number of orders that can be accepted.


-----Examples-----
Input
2
7 11
4 7

Output
1

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

Output
3

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

Output
2

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One day Bob got a letter in an envelope. Bob knows that when Berland's post officers send a letter directly from city «A» to city «B», they stamp it with «A B», or «B A». Unfortunately, often it is impossible to send a letter directly from the city of the sender to the city of the receiver, that's why the letter is sent via some intermediate cities. Post officers never send a letter in such a way that the route of this letter contains some city more than once. Bob is sure that the post officers stamp the letters accurately.

There are *n* stamps on the envelope of Bob's letter. He understands that the possible routes of this letter are only two. But the stamps are numerous, and Bob can't determine himself none of these routes. That's why he asks you to help him. Find one of the possible routes of the letter.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — amount of mail stamps on the envelope. Then there follow *n* lines with two integers each — description of the stamps. Each stamp is described with indexes of the cities between which a letter is sent. The indexes of cities are integers from 1 to 109. Indexes of all the cities are different. Every time the letter is sent from one city to another, exactly one stamp is put on the envelope. It is guaranteed that the given stamps correspond to some valid route from some city to some other city.

Output Specification:
Output *n*<=+<=1 numbers — indexes of cities in one of the two possible routes of the letter.

Demo Input:
['2\n1 100\n100 2\n', '3\n3 1\n100 2\n3 2\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kitahara Haruki has bought n apples for Touma Kazusa and Ogiso Setsuna. Now he wants to divide all the apples between the friends.

Each apple weights 100 grams or 200 grams. Of course Kitahara Haruki doesn't want to offend any of his friend. Therefore the total weight of the apples given to Touma Kazusa must be equal to the total weight of the apples given to Ogiso Setsuna.

But unfortunately Kitahara Haruki doesn't have a knife right now, so he cannot split any apple into some parts. Please, tell him: is it possible to divide all the apples in a fair way between his friends?


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 100) — the number of apples. The second line contains n integers w_1, w_2, ..., w_{n} (w_{i} = 100 or w_{i} = 200), where w_{i} is the weight of the i-th apple.


-----Output-----

In a single line print "YES" (without the quotes) if it is possible to divide all the apples between his friends. Otherwise print "NO" (without the quotes).


-----Examples-----
Input
3
100 200 100

Output
YES

Input
4
100 100 100 200

Output
NO



-----Note-----

In the first test sample Kitahara Haruki can give the first and the last apple to Ogiso Setsuna and the middle apple to Touma Kazusa.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A sky scraper with 1000 floors has been built in the city of N. It has modern superfast elevators to help to travel from one floor to another. Each elevator has two doors, the front one and the back one. If one goes in through the front door, he goes out through the back one and vice versa. The elevator has two rails numbered with numbers 1 and 2. Rail 1 is located to the left of the entrance to the front door (or correspondingly, to the right of the entrance to the back door). Rail 2 is located opposite it, to the right of the entrance to the front door and to the left of the entrance to the back door. We know that each person in the city of N holds at a rail with the strongest hand. 

One day a VIP person visited the city and of course, he took a look at the skyscraper and took a ride in the elevator. We know the door through which he entered and the rail he was holding at. Now we need to determine as soon as possible whether he is left-handed or right-handed.

Input Specification:
The first line indicates the door through which the very important person entered the elevator. It contains "front" if the person enters the elevator through the front door and "back" if he entered the elevator through the back door. The second line contains integer *a* (1<=≤<=*a*<=≤<=2) which denotes the number of the rail at which the person was holding.

Output Specification:
Print character "R" if the VIP is right-handed or "L" if he is left-handed.

Demo Input:
['front\n1\n']

Demo Output:
['L\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A famous gang of pirates, Sea Dogs, has come back to their hideout from one of their extravagant plunders. They want to split their treasure fairly amongst themselves, that is why You, their trusted financial advisor, devised a game to help them:

All of them take a sit at their round table, some of them with the golden coins they have just stolen. At each iteration of the game if one of them has equal or more than 2 coins, he is eligible to the splitting and he gives one coin to each pirate sitting next to him. If there are more candidates (pirates with equal or more than 2 coins) then You are the one that chooses which one of them will do the splitting in that iteration. The game ends when there are no more candidates eligible to do the splitting. 

Pirates can call it a day, only when the game ends. Since they are beings with a finite amount of time at their disposal, they would prefer if the game that they are playing can end after finite iterations, and if so, they call it a good game. On the other hand, if no matter how You do the splitting, the game cannot end in finite iterations, they call it a bad game. Can You help them figure out before they start playing if the game will be good or bad?

Input

The first line of input contains two integer numbers n and k (1 ≤ n ≤ 10^{9}, 0 ≤ k ≤ 2⋅10^5), where n denotes total number of pirates and k is the number of pirates that have any coins.

The next k lines of input contain integers a_i and b_i (1 ≤ a_i ≤ n, 1 ≤ b_i ≤ 10^{9}), where a_i denotes the index of the pirate sitting at the round table (n and 1 are neighbours) and b_i the total number of coins that pirate a_i has at the start of the game. 

Output

Print 1 if the game is a good game: There is a way to do the splitting so the game ends after finite number of iterations.

Print -1 if the game is a bad game: No matter how You do the splitting the game does not end in finite number of iterations.

Examples

Input


4 2
1 2
2 2


Output


1

Input


6 2
2 3
4 1


Output


1

Input


3 2
1 1
2 2


Output


-1

Note

In the third example the game has no end, because You always only have only one candidate, after whose splitting you end up in the same position as the starting one. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little chef has just been introduced to the world of numbers! While experimenting with addition and multiplication operations, the little chef came up with the following problem:

Given an array A of non-negative integers, how many pairs of indices i and j exist such that  A[i]*A[j] > A[i]+A[j]  where  i < j .

Now being a learner, little chef isn't able to solve this problem efficiently and hence turns to you for help. 

-----Input-----
First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of integers in the array. The next line contains N space separated integers where the ith integer represents A[i]. 
Note : There may be trailing spaces on each line of input. 

-----Output-----
For each test, print the required number of pairs in a single line.

-----Constraints-----
-  1 ≤ T ≤ 10 
-  2 ≤ N ≤ 100000 (105) 
-  0 ≤ A[i] ≤ 1000000 (106)

-----Example-----
Input:
2
3
3 4 5
4
1 1 1 1

Output:
3
0

-----Explanation-----

Example case 1.

All pairs of numbers satisfy the criteria. Total number of pairs equals 3.

Example case 2.

No pair of numbers satisfy the criteria.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that when given a URL as a string, parses out just the domain name and returns it as a string. For example:
```python
domain_name("http://github.com/carbonfive/raygun") == "github" 
domain_name("http://www.zombie-bites.com") == "zombie-bites"
domain_name("https://www.cnet.com") == "cnet"
```

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