vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an array $A$ of size $N$ , count number of pairs of index $i,j$ such that $A_i$ is even, $A_j$ is odd and $i < j$

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases.   
- The first line of each test case contains integer $N$.    
- The second line of each test case contains $N$ space separated integers $A_i$. 

-----Output-----
For each test case, print a single line containing an integer denoting number of pairs.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 10^5$ 
- $1 \le A_i \le 10^9$
- Sum of $N$ over all test cases doesn't exceed $10^6 $ 

-----Subtasks-----
Subtask #1 (30 points):
- $2 \le N \le 100$ 
Subtask #2 (70 points): original constraints

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

-----Example Output-----
2
3

-----Explanation-----
Example case 1:$(A_2,A_3)$ and $(A_2,A_4)$ . 
Example case 2:$(A_2,A_3)$ , $(A_2,A_5)$ and $(A_4,A_5)$  .

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the computer-generated world Matriks, you work as a consultant for some hip IT companies that need unique slides for their cool office spaces. During the past year, you got a number of job offers at different points in time, measured in milliseconds since the start of the year. For each job you could choose to design a small, medium or humongous slide for the company, which would take $2 \cdot 10^5$, $3 \cdot 10^5$ or $4 \cdot 10^5$ milliseconds respectively, starting immediately after the offer is given (if accepted). During an assignment, you have to decline every other assignment that is offered during that time. When looking back at the year you’re not particularly dissatisfied (who can complain about designing slides?), but perhaps you could have chosen what job offers to accept in a different way to earn even more. You charge your clients $1$ cookie per $10^5$ milliseconds that you work. If you chose what assignments to accept and their lengths optimally, how many cookies could you have earned?

-----Input-----
The first line contains an integer $N$ ($1 \le N \le 10^5$), the number of job offers you got during the year.

The second and final line contains $N$ integers separated with spaces, the times at which you got job offers measured in milliseconds from the start of the year. A year consists of $31556926 \cdot 10^3$ milliseconds. It is guaranteed that each job offer was given at least $4 \cdot 10^5$ milliseconds before the end of the year.

-----Output-----
Output an integer, the maximum number of cookies you could have earned.

-----Explanation of sample 1-----
A possible solution is to take the first, third and fourth jobs and build a humongous slide for each one. This results in $12$ cookies. The time between the job offers is at least $4 \cdot 10^5$ milliseconds, so no assignments overlap.

-----Examples-----
Sample Input 1:
4
10000 400000 500000 900000
Sample Output 1:
12

Sample Input 2:
5
8 10 2 1000000 30556926000
Sample Output 2:
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is an integer x that is greater than or equal to 0, and less than or equal to 1.
Output 1 if x is equal to 0, or 0 if x is equal to 1.

-----Constraints-----
 - 0 \leq x \leq 1
 - x is an integer

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

-----Output-----
Print 1 if x is equal to 0, or 0 if x is equal to 1.

-----Sample Input-----
1

-----Sample Output-----
0


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

Elections are in progress!

Given an array of numbers representing votes given to each of the candidates, and an integer which is equal to the number of voters who haven't cast their vote yet, find the number of candidates who still have a chance to win the election.

The winner of the election must secure strictly more votes than any other candidate. If two or more candidates receive the same (maximum) number of votes, assume there is no winner at all.

**Note**: big arrays will be tested.

# Examples

```
votes = [2, 3, 5, 2]
voters = 3

result = 2
```

* Candidate `#3` may win, because he's already leading.
* Candidate `#2` may win, because with 3 additional votes he may become the new leader.
* Candidates `#1` and `#4` have no chance, because in the best case scenario each of them can only tie with the candidate `#3`.

___

```
votes = [3, 1, 1, 3, 1]
voters = 2

result = 2
```

* Candidate `#1` and `#4` can become leaders if any of them gets the votes.
* If any other candidate gets the votes, they will get tied with candidates `#1` and `#4`.

___

```
votes = [1, 3, 3, 1, 1]
voters = 0

result = 0
```

* There're no additional votes to cast, and there's already a tie.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is given two strings A and B of length N containing lowercase English letters.

Chef can rearrange both the strings in any way he wants. He wants to minimize the length of LCS ([Longest Common Subsequence] of both the strings.

Find the minimum length of LCS of A and B if he optimally rearranges both the strings.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N - denoting the length of A and B.
- The second line of each test case contains a string A.
- The third line of each test case contains a string B.

------ Output Format ------ 

For each test case, output the minimum length of LCS Chef can obtain.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$A$ and $B$ contain lowercase English letters
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
aaaa
aaab
1
c
z
5
abcde
cdefg

----- Sample Output 1 ------ 
3
0
1

----- explanation 1 ------ 
Test case 1: $\mathrm{LCS}(\texttt{aaaa}, \texttt{aaab}) = \texttt{aaa}$. It can be shown that no other rearrangement of the strings produces a smaller LCS.

Test case 3: $\mathrm{LCS}(\texttt{acbed}, \texttt{gdefc}) = \texttt{c}$. Note that multiple longest common subsequences exist for this arrangement. It can be shown that no other rearrangement of the strings produces a smaller LCS.

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

Make a custom esolang interpreter for the language Tick. Tick is a descendant of [Ticker](https://www.codewars.com/kata/esolang-ticker) but also very different data and command-wise.

Syntax/Info
========

Commands are given in character format. Non-command characters should be ignored. Tick has an potentially infinite memory as opposed to Ticker(which you have a special command to add a new cell) and only has 4 commands(as opposed to 7). Read about this esolang [here](https://esolangs.org/wiki/Tick).

Commands
========

`>`: Move data selector right

`<`: Move data selector left(infinite in both directions)

`+`: Increment memory cell by 1. 255+1=0

`*`: Add ascii value of memory cell to the output tape.

Examples
========

**Hello world!**

```
'++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++**>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>++++++++++++++++++++++++++++++++*>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*<<*>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*<<<<*>>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>+++++++++++++++++++++++++++++++++*'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A carpet shop sells carpets in different varieties. Each carpet can come in a different roll width and can have a different price per square meter. 

Write a function `cost_of_carpet` which calculates the cost (rounded to 2 decimal places) of carpeting a room, following these constraints:

* The carpeting has to be done in one unique piece. If not possible, retrun `"error"`.
* The shop sells any length of a roll of carpets, but always with a full width.
* The cost has to be minimal.
* The length of the room passed as argument can sometimes be shorter than its width (because we define these relatively to the position of the door in the room).
* A length or width equal to zero is considered invalid, return `"error"` if it occurs.


INPUTS:

`room_width`, `room_length`, `roll_width`, `roll_cost` as floats.

OUTPUT:

`"error"` or the minimal cost of the room carpeting, rounded to two decimal places.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
Given an initial string `s`, switch case of the minimal possible number of letters to make the whole string written in the upper case or in the lower case.

# Input/Output


`[input]` string `s`

String of odd length consisting of English letters.

3 ≤ inputString.length ≤ 99.

`[output]` a string

The resulting string.

# Example

For `s = "Aba"`, the output should be `"aba"`

For `s = "ABa"`, the output should be `"ABA"`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given sequence a_1, a_2, ..., a_{n} of integer numbers of length n. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences. It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.


-----Input-----

The first line contains integer number n (1 ≤ n ≤ 10^5).

The second line contains n integer numbers a_1, a_2, ..., a_{n} ( - 10^4 ≤ a_{i} ≤ 10^4). The sequence contains at least one subsequence with odd sum.


-----Output-----

Print sum of resulting subseqeuence.


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

Output
3

Input
3
2 -5 -3

Output
-1



-----Note-----

In the first example sum of the second and the fourth elements is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we know, DZY loves playing games. One day DZY decided to play with a n × m matrix. To be more precise, he decided to modify the matrix with exactly k operations.

Each modification is one of the following:

  1. Pick some row of the matrix and decrease each element of the row by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing. 
  2. Pick some column of the matrix and decrease each element of the column by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing. 



DZY wants to know: what is the largest total value of pleasure he could get after performing exactly k modifications? Please, help him to calculate this value.

Input

The first line contains four space-separated integers n, m, k and p (1 ≤ n, m ≤ 103; 1 ≤ k ≤ 106; 1 ≤ p ≤ 100).

Then n lines follow. Each of them contains m integers representing aij (1 ≤ aij ≤ 103) — the elements of the current row of the matrix.

Output

Output a single integer — the maximum possible total pleasure value DZY could get.

Examples

Input

2 2 2 2
1 3
2 4


Output

11


Input

2 2 5 2
1 3
2 4


Output

11

Note

For the first sample test, we can modify: column 2, row 2. After that the matrix becomes:
    
    
      
    1 1  
    0 0  
      
    

For the second sample test, we can modify: column 2, row 2, row 1, column 1, column 2. After that the matrix becomes:
    
    
      
    -3 -3  
    -2 -2

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

After William is done with work for the day, he enjoys playing his favorite video game.

The game happens in a 2D world, starting at turn 0. William can pick any cell in the game world and spawn in it. Then, each turn, William may remain at his current location or move from the current location (x, y) to one of the following locations: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).

To accelerate movement the game has n fast travel towers. i-th tower is located at location (xa_i, ya_i). To be able to instantly travel to the tower from any location in the game world it must first be activated. Activation of tower i happens at the moment when the player is in cell (xa_i, ya_i) after this the tower remains active throughout the entire game.

William also knows that the game has m quests. i-th quest can be completed instantly by being at location (xb_i, yb_i) on turn t_i.

William wants to find out the maximal number of quests he will be able to complete by optimally traversing the game world.

Input

The first line contains two integers n and m (0 ≤ n ≤ 14, 1 ≤ m ≤ 100), which are the number of towers and the number of quests, respectively.

Each of the next n lines contains two integers xa_i, ya_i (1 ≤ xa_i, ya_i ≤ 10^6), which are the coordinates of fast travel towers.

Each of the next m lines contains two integers xb_i, yb_i and t_i (1 ≤ xb_i, yb_i ≤ 10^6, 1 ≤ t_i ≤ 10^9), which are the coordinates of quests and the turn at which it may be completed.

It is guaranteed that all locations in a test are different.

Output

Print a single number — the maximal number of quests William will be able to complete.

Example

Input


3 4
1 1
2 3
5 2
2 2 12
5 1 4
6 2 11
3 5 10


Output


3

Note

In the first sample test one of the possible sequences of William's actions is as follows: 

  * Spawn at (3, 2) 
  * On turn 1 move to (4, 2) 
  * On turn 2 move to (5, 2). By visiting this cell William activates tower number 3. 
  * On turn 3 move to (5, 1), where he waits for 1 turn to complete the 2nd quest 
  * On turn 5 move to (5, 2) 
  * On turn 6 move to (5, 3) 
  * On turn 7 move to (5, 4) 
  * On turn 8 move to (5, 5) 
  * On turn 9 move to (4, 5) 
  * On turn 10 move to (3, 5). By moving to this location William will complete the 4th quest 
  * On turn 10 instantly move to an already activated fast travel tower at (5, 2) 
  * On turn 11 move to (6, 2). By moving to this location William will complete the 3rd quest 
  * William will not be able to complete the quest number 1, because the tower at (2, 3) was not activated 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are K items placed on a grid of squares with R rows and C columns. Let (i, j) denote the square at the i-th row (1 \leq i \leq R) and the j-th column (1 \leq j \leq C). The i-th item is at (r_i, c_i) and has the value v_i.
Takahashi will begin at (1, 1), the start, and get to (R, C), the goal. When he is at (i, j), he can move to (i + 1, j) or (i, j + 1) (but cannot move to a non-existent square).
He can pick up items on the squares he visits, including the start and the goal, but at most three for each row. It is allowed to ignore the item on a square he visits.
Find the maximum possible sum of the values of items he picks up.

-----Constraints-----
 - 1 \leq R, C \leq 3000
 - 1 \leq K \leq \min(2 \times 10^5, R \times C)
 - 1 \leq r_i \leq R
 - 1 \leq c_i \leq C
 - (r_i, c_i) \neq (r_j, c_j) (i \neq j)
 - 1 \leq v_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
R C K
r_1 c_1 v_1
r_2 c_2 v_2
:
r_K c_K v_K

-----Output-----
Print the maximum possible sum of the values of items Takahashi picks up.

-----Sample Input-----
2 2 3
1 1 3
2 1 4
1 2 5

-----Sample Output-----
8

He has two ways to get to the goal:
 - Visit (1, 1), (1, 2), and (2, 2), in this order. In this case, the total value of the items he can pick up is 3 + 5 = 8.
 - Visit (1, 1), (2, 1), and (2, 2), in this order. In this case, the total value of the items he can pick up is 3 + 4 = 7.
Thus, the maximum possible sum of the values of items he picks up is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef works in a similar way to a travelling salesman ― he always travels to new cities in order to sell his delicious dishes.
Today, Chef is planning to visit $N$ cities (numbered $1$ through $N$). There is a direct way to travel between each pair of cities. Each city has a specific temperature; let's denote the temperature in the $i$-th city by $C_i$. Chef has a fixed temperature tolerance $D$ with the following meaning: for each pair of cities $a$ and $b$, he may travel from city $a$ directly to city $b$ only if $|C_a-C_b| \le D$, otherwise he would catch a heavy flu because of the sudden change in temperature.
Chef starts from city $1$. Is he able to visit all $N$ cities in such a way that each city is visited exactly once?
Notes:
- Chef is not able to travel through a city without visiting it.
- City $1$ is visited at the beginning.
- It is not necessary to be able to travel directly to city $1$ from the last city Chef visits.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $D$.
- The second line contains $N$ space-separated integers $C_1, C_2, \ldots, C_N$.

-----Output-----
For each test case, print a single line containing the string "YES" (without quotes) if Chef can visit all cities or "NO" (without quotes) if he cannot.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 10^5$
- $0 \le D \le 10^9$
- $0 \le C_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points):
- $N \le 1,000$
- the sum of $N$ over all test cases does not exceed $10,000$
Subtask #2 (80 points): original constraints

-----Example Input-----
2
5 3
3 2 1 4 5
5 4
10 1 3 2 9

-----Example Output-----
YES
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abhinav is master in game theory. He creates new games with a great logic and today he has created another one. He invites his best friend Ravi to play against him.

The rules of the game are, a set of N powers are given. Players start with initial power zero. In their turn, each player should choose a power from the set. A player can choose any power from the set that are only to either ends of the set. Once a power is chosen, it is removed from the set and its value is added to value of individual power of the player who chose it. The one who ends with maximum power wins the game.

Abhinav lets his friend Ravi to start the game always. Now you have to find who wins the game if both the players play optimally.
Input :
First line has an integer T(number of test cases).  
Each test case is a single line with first number denoting N, size of set of powers and N numbers follows in the same line.

Output :
For each test case, print who wins the game along with his power at the end of the game. If both the players get equal power, print "Tie"(without quotes).

Constraints :
1 ≤ T ≤ 250
1 ≤ N ≤ 1000
1 ≤ P ≤ 1000 (P is value of individual powers in the set).

Problem Setter : Vinay Kumar

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

SAMPLE OUTPUT
Ravi 1
Ravi 2
Abhinav 8
Tie

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's winter and taking a bath is a delicate matter. Chef has two buckets of water. The first bucket has $v_1$ volume of cold water at temperature $t_1$. The second has $v_2$ volume of hot water at temperature $t_2$. Chef wants to take a bath with at least $v_3$ volume of water which is at exactly $t_3$ temperature. To get the required amount of water, Chef can mix some water obtained from the first and second buckets.
Mixing $v_x$ volume of water at temperature $t_x$ with $v_y$ volume of water at temperature $t_y$ yields $v_x + v_y$ volume of water at temperature calculated as
vxtx+vytyvx+vyvxtx+vytyvx+vy\frac{v_x t_x + v_y t_y}{v_x + v_y}
Help Chef figure out if it is possible for him to take a bath with at least $v_3$ volume of water at temperature $t_3$.
Assume that Chef has no other source of water and that no heat is lost by the water in the buckets with time, so Chef cannot simply wait for the water to cool.

-----Input-----
- The first line contains $n$, the number of test cases. $n$ cases follow.
- Each testcase contains of a single line containing 6 integers $v_1, t_1, v_2, t_2, v_3, t_3$.

-----Output-----
- For each test case, print a single line containing "YES" if Chef can take a bath the way he wants and "NO" otherwise.

-----Constraints-----
- $1 \leq n \leq 10^5$
- $1 \leq v_1, v_2, v_3 \leq 10^6$
- $1 \leq t_1 < t_2 \leq 10^6$
- $1 \leq t_3 \leq 10^6$

-----Sample Input-----
3
5 10 5 20 8 15
5 10 5 20 1 30
5 10 5 20 5 20

-----Sample Output-----
YES
NO
YES

-----Explanation-----
- Case 1: Mixing all the water in both buckets yields 10 volume of water at temperature 15, which is more than the required 8.
- Case 2: It is not possible to get water at 30 temperature.
- Case 3: Chef can take a bath using only the water in the second bucket.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have received data from a Bubble bot. You know your task is to make factory facilities, but before you even start, you need to know how big the factory is and how many rooms it has. When you look at the data you see that you have the dimensions of the construction, which is in rectangle shape: N x M. 

Then in the next N lines you have M numbers. These numbers represent factory tiles and they can go from 0 to 15. Each of these numbers should be looked in its binary form. Because from each number you know on which side the tile has walls. For example number 10 in it's binary form is 1010, which means that it has a wall from the North side, it doesn't have a wall from the East, it has a wall on the South side and it doesn't have a wall on the West side. So it goes North, East, South, West. 

It is guaranteed that the construction always has walls on it's edges. The input will be correct. 

Your task is to print the size of the rooms from biggest to smallest. 

Input

The first line has two numbers which are N and M, the size of the construction. Both are integers: 

n (1 ≤ n ≤ 10^3)

m (1 ≤ m ≤ 10^3)

Next N x M numbers represent each tile of construction.

Output

Once you finish processing the data your output consists of one line sorted from biggest to smallest room sizes. 

Example

Input


4 5
9 14 11 12 13
5 15 11 6 7
5 9 14 9 14
3 2 14 3 14


Output


9 4 4 2 1

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