vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Splits

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's define a split of $n$ as a nonincreasing sequence of positive integers, the sum of which is $n$. 

For example, the following sequences are splits of $8$: $[4, 4]$, $[3, 3, 2]$, $[2, 2, 1, 1, 1, 1]$, $[5, 2, 1]$.

The following sequences aren't splits of $8$: $[1, 7]$, $[5, 4]$, $[11, -3]$, $[1, 1, 4, 1, 1]$.

The weight of a split is the number of elements in the split that are equal to the first element. For example, the weight of the split $[1, 1, 1, 1, 1]$ is $5$, the weight of the split $[5, 5, 3, 3, 3]$ is $2$ and the weight of the split $[9]$ equals $1$.

For a given $n$, find out the number of different weights of its splits.

Input Specification:
The first line contains one integer $n$ ($1 \leq n \leq 10^9$).

Output Specification:
Output one integer — the answer to the problem.

Demo Input:
['7\n', '8\n', '9\n']

Demo Output:
['4\n', '5\n', '5\n']

Note:
In the first sample, there are following possible weights of splits of $7$:

Weight 1: [$\textbf 7$] 

Weight 2: [$\textbf 3$, $\textbf 3$, 1] 

Weight 3: [$\textbf 2$, $\textbf 2$, $\textbf 2$, 1] 

Weight 7: [$\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities along the road, which can be represented as a straight line. The i-th city is situated at the distance of a_i kilometers from the origin. All cities are situated in the same direction from the origin. There are m trucks travelling from one city to another. 

Each truck can be described by 4 integers: starting city s_i, finishing city f_i, fuel consumption c_i and number of possible refuelings r_i. The i-th truck will spend c_i litres of fuel per one kilometer. 

When a truck arrives in some city, it can be refueled (but refueling is impossible in the middle of nowhere). The i-th truck can be refueled at most r_i times. Each refueling makes truck's gas-tank full. All trucks start with full gas-tank.

All trucks will have gas-tanks of the same size V litres. You should find minimum possible V such that all trucks can reach their destinations without refueling more times than allowed.

Input

First line contains two integers n and m (2 ≤ n ≤ 400, 1 ≤ m ≤ 250000) — the number of cities and trucks.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9, a_i < a_{i+1}) — positions of cities in the ascending order.

Next m lines contains 4 integers each. The i-th line contains integers s_i, f_i, c_i, r_i (1 ≤ s_i < f_i ≤ n, 1 ≤ c_i ≤ 10^9, 0 ≤ r_i ≤ n) — the description of the i-th truck.

Output

Print the only integer — minimum possible size of gas-tanks V such that all trucks can reach their destinations.

Example

Input


7 6
2 5 7 10 14 15 17
1 3 10 0
1 7 12 7
4 5 13 3
4 7 10 1
4 7 10 1
1 5 11 2


Output


55

Note

Let's look at queries in details: 

  1. the 1-st truck must arrive at position 7 from 2 without refuelling, so it needs gas-tank of volume at least 50. 
  2. the 2-nd truck must arrive at position 17 from 2 and can be refueled at any city (if it is on the path between starting point and ending point), so it needs gas-tank of volume at least 48. 
  3. the 3-rd truck must arrive at position 14 from 10, there is no city between, so it needs gas-tank of volume at least 52. 
  4. the 4-th truck must arrive at position 17 from 10 and can be refueled only one time: it's optimal to refuel at 5-th city (position 14) so it needs gas-tank of volume at least 40. 
  5. the 5-th truck has the same description, so it also needs gas-tank of volume at least 40. 
  6. the 6-th truck must arrive at position 14 from 2 and can be refueled two times: first time in city 2 or 3 and second time in city 4 so it needs gas-tank of volume at least 55. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Roman has no idea, why this problem is called Stone. He also has no idea on how to solve the followong problem: given array of N integers A and a number K. During a turn the maximal value over all Ai is chosen, let's call it MAX. Then Ai = 
MAX - Ai is done for every 1 <= i <= N. Help Roman to find out how will the array look like after K turns.

-----Input-----
The numbers N and K are given in the first line of an input. Then N integers are given in the second line which denote the array A. 

-----Output-----
Output N numbers on a single line. It should be the array A after K turns.

-----Constraints-----

- 1 <= N <= 105
- 0 <= K <= 109
- Ai does not exceed 2 * 109 by it's absolute value.

-----Example-----
Input:
4 1
5 -1 7 0

Output:
2 8 0 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In africa jungle , there were zebra's who liked to spit.
There owner watched them for whole day and noted in his sheet where each zebra spitted.
Now he's in a confusion and wants to know if in the jungle there are two zebra's which spitted at each other.
Help him solve this task.
If the zebra is present in position a spits b metres right , he can hit only zebra in position a+b , if such a zebra exists.

-----Input:-----
- The first line contains integer t(1<=t<100)- amount of zebras in jungle.
- Each of following t lines contains two integers a(i) and b(i)(-10^4<=x(i)<=10^4,1<|d(i)|<=2.10^4) - records in owner sheet.
- a(i) is the position of i-th zebra and b(i) is distance at which the i-th camel spitted.
Positive values of d(i) correspond to spits right, negative values correspond to spit left.No two zebras may stand in the same position.

-----Output:-----
If there are two zebras , which spitted at each other , output YES, otherwise , output NO.

-----Sample Input:-----
2
0 1
1 -1

-----Sample Output:-----
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Japanese game of Shiritori is the perfect 2-player game for a long car ride. The rules are simple: the first player picks any word to say, then the second player must choose a new word that begins with the last letter of the word that the first player just said. Then it is the first player’s turn again to say a word that begins with the last letter of the previous word the second player said, and so on. At each turn, the player whose turn it is must say a word that links to the previous one and which has not been called out before during the game. Your job is to determine if the game was played according to these rules, given a history of the words used in a particular game. In a game, player $1$ always starts first.

-----Input-----
Input consists of one test case that begins with an integer $N$ ($2 \leq N \leq 100000$) on a single line. Each of the following $N$ lines contains $1$ word. The words are presented in the order in which the players called them out, starting with player $1$. All words consist of between $1$ and $120$ lowercase English letters.

-----Output-----
If the game was played according to the rules, output “Fair Game”. Otherwise, find out which player first violated the rules of the game. That player lost the game, so output “Player <i> lost”. For example, if player $1$ violated the rules first, output “Player 1 lost”.

-----Examples-----
Sample Input 1:
5
apple
ear
real
letters
style
Sample Output 1:
Fair Game

Sample Input 2:
3
apple
extra
apple
Sample Output 2:
Player 1 lost

Sample Input 3:
2
apple
neat
Sample Output 3:
Player 2 lost

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hi! Welcome to my first kata.

In this kata the task is to take a list of integers (positive and negative) and split them according to a simple rule; those ints greater than or equal to the key, and those ints less than the key (the itself key will always be positive).

However, in this kata the goal is to sort the numbers IN PLACE, so DON'T go messing around with the order in with the numbers appear.

You are to return a nested list. If the list is empty, simply return an empty list.

Confused? Okay, let me walk you through an example...

    The input is: [1, 1, 1, 0, 0, 6, 10, 5, 10], the key is: 6
Okay so the first five numbers are less than the key, 6, so we group them together.

    [1, 1, 1, 0, 0]
The next two numbers, 6 & 10, are both >= 6 to they belong in a seperate group, which we will add to the first group. Like so:

    [[1, 1, 1, 0, 0], [6, 10]]
The next two numbers are 5 & 10. Since the key is 6 these two numbers form seperate groups, which we will add to the previous result. like so:

    [[1, 1, 1, 0, 0], [6, 10], [5], [10]]
And voila! We're done.
 
Here are a few more basic examples:

    group_ints([1, 0], key= 0)  
    --> [[1,0]]
  
    group_ints([1, 0, -1, 5], key= 0) 
    --> [[1, 0], [-1], [5]]
  
    group_ints([1, 0, -1, 5], key= 5) 
    --> [[1, 0, -1], [5]]

Good luck guys/gals!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has $n$ coins, the value of the $i$-th coin is $a_i$. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket.

For example, if Polycarp has got six coins represented as an array $a = [1, 2, 4, 3, 3, 2]$, he can distribute the coins into two pockets as follows: $[1, 2, 3], [2, 3, 4]$.

Polycarp wants to distribute all the coins with the minimum number of used pockets. Help him to do that.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 100$) — the number of coins.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — values of coins.


-----Output-----

Print only one integer — the minimum number of pockets Polycarp needs to distribute all the coins so no two coins with the same value are put into the same pocket.


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

Output
2

Input
1
100

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Catherine is a brilliant software engineer, but she has been having difficulty landing a job, despite having submitted a superb resume to dozens of tech companies. After doing some research, she discovered that most tech companies in her area use an algorithm to prescreen resumes by scanning for certain keywords before the resume is even seen by a human. Any resume that does not contain sufficiently many technology-related keywords is automatically rejected!

Catherine has devised a plan to outwit the prescreening algorithm: she intends to cram as many keywords as possible into her resume to maximize her chances of passing the prescreening process. As a first step, she has downloaded a list of the most common tech buzzwords from an online data bank that includes entries such as “machine learning”, “Big data”, “AI”, “C++”, “Neural-network”, “unix”, “cryptography”, etc. (Note that keyword sometimes really means keyphrase.)

In the early stages of drafting her new resume, Catherine notices that many keywords from the data bank are very similar to each other (e.g., “Machine-learning” vs. “machine learning”, or “MySQL” vs. “MySql”). Since she suspects that including nearly identical keywords won’t help her fool the prescreening algorithm, she wants to filter out such similar keywords in order to save room on her resume. Catherine considers two keywords $k_1$ and $k_2$ to be similar if, after replacing hyphens with spaces and ignoring capitalization, $k_1$ is the same as $k_2$.

Can you help Catherine craft the perfect resume to land her a job?

-----Input-----
The first line contains an integer, $n$ $(1 \leq n \leq 40000)$, the number of keywords in the data bank. This is followed by $n$ lines, each of which contains a keyword string $k$ that is between $1$ and $25$ characters in length (inclusive). All characters in a keyword are guaranteed to fall in the $[32, 126]$ ASCII range, and no keyword begins or ends with a space or a hyphen.

-----Output-----
Output a single line containing the number of (pairwise) non-similar keywords in the data bank.

-----Examples-----
Sample Input 1:
4
c++
C++
c
c#
Sample Output 1:
3

Sample Input 2:
5
cryptography
blockchain
Artificial intelligence
Machine-Learning
Linux
Sample Output 2:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given array A[] of integers, the task is to complete the function findMaxDiff which finds the maximum absolute difference between nearest left and right smaller element of every element in array.If the element is the leftmost element, nearest smaller element on left side is considered as 0. Similarly if the element is the rightmost elements, smaller element on right side is considered as 0.
Examples:
Input : arr[] = {2, 1, 8}
Output : 1
Left smaller  LS[] {0, 0, 1}
Right smaller RS[] {1, 0, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 1 
Input  : arr[] = {2, 4, 8, 7, 7, 9, 3}
Output : 4
Left smaller   LS[] = {0, 2, 4, 4, 4, 7, 2}
Right smaller  RS[] = {0, 3, 7, 3, 3, 3, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 7 - 3 = 4 
Input : arr[] = {5, 1, 9, 2, 5, 1, 7}
Output : 1
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow .Each test case contains an integer N denoting the size of the array A. In the next line are N space separated values of the array A.
Output:
For each test case output will be in a new line denoting the the maximum absolute difference between nearest left and right smaller element of every element in array.
Constraints:
1<=T<=100
1<=N<=100
1<=A[ ]<=100
Example(To be used only for expected output) :
Input:
2
3
2 1 8
7
2 4 8 7 7 9 3
Output
1
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Death Stars (medium)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The stardate is 1983, and Princess Heidi is getting better at detecting the Death Stars. This time, two Rebel spies have yet again given Heidi two maps with the possible locations of the Death Star. Since she got rid of all double agents last time, she knows that both maps are correct, and indeed show the map of the solar system that contains the Death Star. However, this time the Empire has hidden the Death Star very well, and Heidi needs to find a place that appears on both maps in order to detect the Death Star.

The first map is an *N*<=×<=*M* grid, each cell of which shows some type of cosmic object that is present in the corresponding quadrant of space. The second map is an *M*<=×<=*N* grid. Heidi needs to align those two maps in such a way that they overlap over some *M*<=×<=*M* section in which all cosmic objects are identical. Help Heidi by identifying where such an *M*<=×<=*M* section lies within both maps.

Input Specification:
The first line of the input contains two space-separated integers *N* and *M* (1<=≤<=*N*<=≤<=2000, 1<=≤<=*M*<=≤<=200, *M*<=≤<=*N*). The next *N* lines each contain *M* lower-case Latin characters (a-z), denoting the first map. Different characters correspond to different cosmic object types. The next *M* lines each contain *N* characters, describing the second map in the same format.

Output Specification:
The only line of the output should contain two space-separated integers *i* and *j*, denoting that the section of size *M*<=×<=*M* in the first map that starts at the *i*-th row is equal to the section of the second map that starts at the *j*-th column. Rows and columns are numbered starting from 1.

If there are several possible ways to align the maps, Heidi will be satisfied with any of those. It is guaranteed that a solution exists.

Demo Input:
['10 5\nsomer\nandom\nnoise\nmayth\neforc\nebewi\nthyou\nhctwo\nagain\nnoise\nsomermayth\nandomeforc\nnoiseebewi\nagainthyou\nnoisehctwo\n']

Demo Output:
['4 6\n']

Note:
The 5-by-5 grid for the first test case looks like this:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Your Story
"A *piano* in the home meant something." - *Fried Green Tomatoes at the Whistle Stop Cafe*

You've just realized a childhood dream by getting a beautiful and beautiful-sounding upright piano from a friend who was leaving the country. You immediately started doing things like playing "Heart and Soul" over and over again, using one finger to pick out any melody that came into your head, requesting some sheet music books from the library, signing up for some MOOCs like Developing Your Musicianship, and wondering if you will think of any good ideas for writing piano-related katas and apps. 

Now you're doing an exercise where you play the very first (leftmost, lowest in pitch) key on the 88-key keyboard, which (as shown below) is white, with the little finger on your left hand, then the second key, which is black, with the ring finger on your left hand, then the third key, which is white, with the middle finger on your left hand, then the fourth key, also white, with your left index finger, and then the fifth key, which is black, with your left thumb. Then you play the sixth key, which is white, with your right thumb, and continue on playing the seventh, eighth, ninth, and tenth keys with the other four fingers of your right hand. Then for the eleventh key you go back to your left little finger, and so on. Once you get to the rightmost/highest, 88th, key, you start all over again with your left little finger on the first key. Your thought is that this will help you to learn to move smoothly and with uniform pressure on the keys from each finger to the next and back and forth between hands.



You're not saying the names of the notes while you're doing this, but instead just counting each key press out loud (not starting again at 1 after 88, but continuing on to 89 and so forth) to try to keep a steady rhythm going and to see how far you can get before messing up. You move gracefully and with flourishes, and between screwups you hear, see, and feel that you are part of some great repeating progression between low and high notes and black and white keys. 

## Your Function
The function you are going to write is not actually going to help you with your piano playing, but just explore one of the patterns you're experiencing: Given the number you stopped on, was it on a black key or a white key? For example, in the description of your piano exercise above, if you stopped at 5, your left thumb would be on the fifth key of the piano, which is black. Or if you stopped at 92, you would have gone all the way from keys 1 to 88 and then wrapped around, so that you would be on the fourth key, which is white.

Your function will receive an integer between 1 and 10000 (maybe you think that in principle it would be cool to count up to, say, a billion, but considering how many years it would take it is just not possible) and return the string "black" or "white" -- here are a few more examples:
```
1     "white"
12    "black"
42    "white"
100   "black"
2017  "white"
```
Have fun! And if you enjoy this kata, check out the sequel: Piano Kata, Part 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike and some bears are playing a game just for fun. Mike is the judge. All bears except Mike are standing in an n × m grid, there's exactly one bear in each cell. We denote the bear standing in column number j of row number i by (i, j). Mike's hands are on his ears (since he's the judge) and each bear standing in the grid has hands either on his mouth or his eyes. [Image] 

They play for q rounds. In each round, Mike chooses a bear (i, j) and tells him to change his state i. e. if his hands are on his mouth, then he'll put his hands on his eyes or he'll put his hands on his mouth otherwise. After that, Mike wants to know the score of the bears.

Score of the bears is the maximum over all rows of number of consecutive bears with hands on their eyes in that row.

Since bears are lazy, Mike asked you for help. For each round, tell him the score of these bears after changing the state of a bear selected in that round. 


-----Input-----

The first line of input contains three integers n, m and q (1 ≤ n, m ≤ 500 and 1 ≤ q ≤ 5000).

The next n lines contain the grid description. There are m integers separated by spaces in each line. Each of these numbers is either 0 (for mouth) or 1 (for eyes).

The next q lines contain the information about the rounds. Each of them contains two integers i and j (1 ≤ i ≤ n and 1 ≤ j ≤ m), the row number and the column number of the bear changing his state.


-----Output-----

After each round, print the current score of the bears.


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

Output
3
4
3
3
4

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 interseted in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Given a matrix G where G(i,j) denotes i^{th }applicant is interested in j^{th }job. Find an assignment of jobs to applicant in such that as many applicants as possible get jobs.
 
Example 1:
Input: 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 3rd job.
Example 2:
Input: 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.