vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array $a_1, a_2, \ldots, a_n$.

In one operation you can choose two elements $a_i$ and $a_j$ ($i \ne j$) and decrease each of them by one.

You need to check whether it is possible to make all the elements equal to zero or not.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.


-----Output-----

Print "YES" if it is possible to make all elements zero, otherwise print "NO".


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

Output
YES
Input
6
1 2 3 4 5 6

Output
NO


-----Note-----

In the first example, you can make all elements equal to zero in $3$ operations:   Decrease $a_1$ and $a_2$,  Decrease $a_3$ and $a_4$,  Decrease $a_3$ and $a_4$ 

In the second example, one can show that it is impossible to make all elements equal to zero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Angela is a new PhD student and she is nervous about the upcoming paper submission deadline of this year’s research conference. She has been working on multiple projects throughout the past year. Luckily most of the projects concluded successfully, and she came up with $n$ candidate papers. However not all of the papers were born equal—some have better results than others. Her advisor believes she should only submit the papers with “good enough” results so they have a high chance of getting accepted. 

Angela’s research group has a unique way of evaluating the success of paper submissions. They use the research productivity index, defined as $a^{a/s}$, where $s$ is the total number of papers submitted, and $a$ is the number of papers that are accepted by the conference. When $a = 0$, the index is defined to be zero. For example:
 - if one paper is submitted and it gets accepted, the index is $1^{1/1} = 1$;
 - if $4$ papers are submitted and all get accepted, the index is $4^{4/4} = 4$;
 - if $10$ papers are submitted and $3$ get accepted, the index is $3^{3/10} \approx 1.390389$;
 - if $5$ papers are submitted and $4$ get accepted, the index is $4^{4/5} \approx 3.031433$;
 - if $3$ papers are submitted and all get rejected ($a=0$), the index is $0$.

Intuitively, to get a high research productivity index one wants to get as many papers accepted as possible while keeping the acceptance rate high.

For each of her $n$ papers, Angela knows exactly how likely it is that the conference would accept the paper. If she chooses wisely which papers to submit, what is the maximum expected value of her research productivity index?

-----Input-----
The first line of the input has a single integer $n$ ($1 \leq n \leq 100$), the number of Angela’s candidate papers. The next line has $n$ space-separated integers giving the probability of each paper getting accepted. Each probability value is given as an integer percentage between $1$ and $100$, inclusive.

-----Output-----
Output the maximum expected value of Angela’s research productivity index. Your answer is considered correct if it has an absolute or relative error of no more than $10^{-6}$.

-----Examples-----
Sample Input 1:
5
30 50 70 60 90
Sample Output 1:
2.220889579

Sample Input 2:
6
30 90 30 90 30 90
Sample Output 2:
2.599738456

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program to Validate an IPv4 Address.
According to Wikipedia, IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots, e.g., 172.16.254.1 .
A valid IPv4 Address is of the form x1.x2.x3.x4 where 0 <= (x1, x2, x3, x4) <= 255.
Thus, we can write the generalized form of an IPv4 address as (0-255).(0-255).(0-255).(0-255).
Note: Here we are considering numbers only from 0 to 255 and any additional leading zeroes will be considered invalid.
Your task is to complete the function isValid which returns 1 if the given IPv4 address is valid else returns 0. The function takes the IPv4 address as the only argument in the form of string.
Example 1:
Input:
IPv4 address = 222.111.111.111
Output: 1
Explanation: Here, the IPv4 address is as
per the criteria mentioned and also all
four decimal numbers lies in the mentioned
range.
Example 2:
Input:
IPv4 address = 5555..555
Output: 0
Explanation: 5555..555 is not a valid
IPv4 address, as the middle two portions
are missing.
Your Task:
Complete the function isValid() which takes the address in the form of string s as an input parameter and returns 1 if this is a valid address otherwise returns 0.
Expected Time Complexity: O(N), N = length of the string.
Expected Auxiliary Space: O(1)
Constraints:
1<=length of string <=50
Note: The Input/Output format and Example given are used for the system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.
The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.
Mouse starts at node 1 and goes first, Cat starts at node 2 and goes second, and there is a Hole at node 0.
During each player's turn, they must travel along one edge of the graph that meets where they are.  For example, if the Mouse is at node 1, it must travel to any node in graph[1].
Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)
Then, the game can end in 3 ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (ie. the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.
 



Example 1:
Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Explanation:
4---3---1
|   |
2---5
 \ /
  0

 
Note:

3 <= graph.length <= 50
It is guaranteed that graph[1] is non-empty.
It is guaranteed that graph[2] contains a non-zero element.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pasha has a wooden stick of some positive integer length n. He wants to perform exactly three cuts to get four parts of the stick. Each part must have some positive integer length and the sum of these lengths will obviously be n. 

Pasha likes rectangles but hates squares, so he wonders, how many ways are there to split a stick into four parts so that it's possible to form a rectangle using these parts, but is impossible to form a square.

Your task is to help Pasha and count the number of such ways. Two ways to cut the stick are considered distinct if there exists some integer x, such that the number of parts of length x in the first way differ from the number of parts of length x in the second way.


-----Input-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 2·10^9) — the length of Pasha's stick.


-----Output-----

The output should contain a single integer — the number of ways to split Pasha's stick into four parts of positive integer length so that it's possible to make a rectangle by connecting the ends of these parts, but is impossible to form a square. 


-----Examples-----
Input
6

Output
1

Input
20

Output
4



-----Note-----

There is only one way to divide the stick in the first sample {1, 1, 2, 2}.

Four ways to divide the stick in the second sample are {1, 1, 9, 9}, {2, 2, 8, 8}, {3, 3, 7, 7} and {4, 4, 6, 6}. Note that {5, 5, 5, 5} doesn't work.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
You are given a positive integer N. Print a numerical triangle of height N - 1 like the one below:
1
22
333
4444
55555
......

Can you do it using only arithmetic operations, a single for loop and print statement?

Use no more than two lines. The first line (the for statement) is already written for you. You have to complete the print statement.

Note: Using anything related to strings will give a score of 0.

=====Input Format=====
A single line containing integer, N.

=====Constraints=====
1≤N≤9

=====Output Format=====
Print N - 1 lines as explained above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kamal-ol-molk's Painting

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Rumors say that one of Kamal-ol-molk's paintings has been altered. A rectangular brush has been moved right and down on the painting.

Consider the painting as a *n*<=×<=*m* rectangular grid. At the beginning an *x*<=×<=*y* rectangular brush is placed somewhere in the frame, with edges parallel to the frame, (1<=≤<=*x*<=≤<=*n*,<=1<=≤<=*y*<=≤<=*m*). Then the brush is moved several times. Each time the brush is moved one unit right or down. The brush has been strictly inside the frame during the painting. The brush alters every cell it has covered at some moment.

You have found one of the old Kamal-ol-molk's paintings. You want to know if it's possible that it has been altered in described manner. If yes, you also want to know minimum possible area of the brush.

Input Specification:
The first line of input contains two integers *n* and *m*, (1<=≤<=*n*,<=*m*<=≤<=1000), denoting the height and width of the painting.

The next *n* lines contain the painting. Each line has *m* characters. Character 'X' denotes an altered cell, otherwise it's showed by '.'. There will be at least one altered cell in the painting.

Output Specification:
Print the minimum area of the brush in a line, if the painting is possibly altered, otherwise print <=-<=1.

Demo Input:
['4 4\nXX..\nXX..\nXXXX\nXXXX\n', '4 4\n....\n.XXX\n.XXX\n....\n', '4 5\nXXXX.\nXXXX.\n.XX..\n.XX..\n']

Demo Output:
['4\n', '2\n', '-1\n']

Note:
none

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

Errors detected during execution are called exceptions.

Examples:

ZeroDivisionError 

This error is raised when the second argument of a division or modulo operation is zero.

>>> a = '1'
>>> b = '0'
>>> print int(a) / int(b)
>>> ZeroDivisionError: integer division or modulo by zero

ValueError 

This error is raised when a built-in operation or function receives an argument that has the right type but an inappropriate value. 

>>> a = '1'
>>> b = '#'
>>> print int(a) / int(b)
>>> ValueError: invalid literal for int() with base 10: '#'

 To learn more about different built-in exceptions click here.    

Handling Exceptions

The statements try and except can be used to handle selected exceptions. A try statement may have more than one except clause to specify handlers for different exceptions.

#Code
try:
    print 1/0
except ZeroDivisionError as e:
    print "Error Code:",e

Output

Error Code: integer division or modulo by zero

Task

You are given two values $\boldsymbol{\alpha}$ and $\boldsymbol{b}$. 

Perform integer division and print $a/b$. 

Input Format

The first line contains $\mathbf{T}$, the number of test cases. 

The next $\mathbf{T}$ lines each contain the space separated values of $\boldsymbol{\alpha}$ and $\boldsymbol{b}$.

Constraints

$0<T<10$

Output Format

Print the value of $a/b$. 

In the case of ZeroDivisionError or ValueError, print the error code.

Sample Input
3
1 0
2 $
3 1

Sample Output
Error Code: integer division or modulo by zero
Error Code: invalid literal for int() with base 10: '$'
3

 Note: 

For integer division in Python 3 use //.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus adores TV series. Right now he is ready to finish watching a season of a popular sitcom "Graph Theory". In total, the season has n episodes, numbered with integers from 1 to n.

Polycarpus watches episodes not one by one but in a random order. He has already watched all the episodes except for one. Which episode has Polycaprus forgotten to watch?


-----Input-----

The first line of the input contains integer n (2 ≤ n ≤ 100000) — the number of episodes in a season. Assume that the episodes are numbered by integers from 1 to n.

The second line contains n - 1 integer a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) — the numbers of episodes that Polycarpus has watched. All values of a_{i} are distinct.


-----Output-----

Print the number of the episode that Polycarpus hasn't watched.


-----Examples-----
Input
10
3 8 10 1 7 9 6 5 2

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are positive integers N, M, Q, and Q quadruples of integers ( a_i , b_i , c_i , d_i ).

Consider a sequence A satisfying the following conditions:

* A is a sequence of N positive integers.
* 1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M.



Let us define a score of this sequence as follows:

* The score is the sum of d_i over all indices i such that A_{b_i} - A_{a_i} = c_i. (If there is no such i, the score is 0.)



Find the maximum possible score of A.

Constraints

* All values in input are integers.
* 2 ≤ N ≤ 10
* 1 \leq M \leq 10
* 1 \leq Q \leq 50
* 1 \leq a_i < b_i \leq N ( i = 1, 2, ..., Q )
* 0 \leq c_i \leq M - 1 ( i = 1, 2, ..., Q )
* (a_i, b_i, c_i) \neq (a_j, b_j, c_j) (where i \neq j)
* 1 \leq d_i \leq 10^5 ( i = 1, 2, ..., Q )

Input

Input is given from Standard Input in the following format:


N M Q
a_1 b_1 c_1 d_1
:
a_Q b_Q c_Q d_Q


Output

Print the maximum possible score of A.

Examples

Input

3 4 3
1 3 3 100
1 2 2 10
2 3 2 10


Output

110


Input

4 6 10
2 4 1 86568
1 4 0 90629
2 3 0 90310
3 4 1 29211
3 4 3 78537
3 4 2 8580
1 2 1 96263
1 4 2 2156
1 2 0 94325
1 4 3 94328


Output

357500


Input

10 10 1
1 10 9 1


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a function that takes a string as a parameter and does the following, in this order:

1. replaces every letter with the letter following it in the alphabet (see note below)
2. makes any vowels capital
3. makes any consonants lower case

**Note:** the alphabet should wrap around, so `Z` becomes `A`

So, for example the string `"Cat30"` would return `"dbU30"` (`Cat30 --> Dbu30 --> dbU30`)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of size N. Output the maximum value of A[i]%A[j] (ie. A[i] mod A[j]) over all 1 ≤ i, j ≤ N.

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

First line of input contains T, the number of testcases.
The first line of each test case contains N, the number of elements in the array.
Second line of each testcase contains N space separated integers in which the ith integer is A[i].

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

For each testcase output a single integer in a new line: the maximum value of A[i]%A[j].

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

$1≤T≤10$
$1≤N≤10^{5}$
$1≤A[i]≤10^{6}$

----- Sample Input 1 ------ 
1
2
1 2
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
The maximum value is obtained by 1%2 = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.
A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.
 
Example 1:
Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:
Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:
Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

 
Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Raj loves to listen to songs in his free time. It’s his birthday tomorrow and his friend Neelansh wants his gift to be the most unique. Being great at making music, he decides to produce a song for him. However, Raj likes songs according to their beauty. He determines the beauty of the song as the number of times all the octave musical tones are completed in ascending order.

He begins with a jumbled tone of length N and numbers each octave tone as 1,2,3….8.

Neelansh wants to maximize the beauty of the song but since he uses the trial version of the software,
- He cannot change the size of N.
- He cannot introduce any new tone, but can choose any two tones and swap their positions

However, Neelansh just received a mail that he needs to submit all his pending assignments by tomorrow. He has tons of assignments left to do, but he doesn’t want to spoil the idea of his gift. Can you help him? 

-----INPUT-----
- The first line contains a single integer T- the number of test cases  
- The first line of each test case contains a single integer N- the length of the song  
- The second line contains N- space separated integers ai,  ai+1,.....aN 

-----OUTPUT-----
For each test case, print a single line containing one integer- the maximum possible beauty of the song  

-----CONSTRAINTS-----
1<=T<=102
1<=N<=105
1<=a<=8

-----EXAMPLE INPUT-----
2

8

1 2 3 4 5 6 7 8

16

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

-----EXAMPLE OUTPUT-----
1

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice lives on a line. Today, she will travel to some place in a mysterious vehicle.
Initially, the distance between Alice and her destination is D. When she input a number x to the vehicle, it will travel in the direction of the destination by a distance of x if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than x.
Alice made a list of N numbers. The i-th number in this list is d_i. She will insert these numbers to the vehicle one by one.
However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after N moves.
She has Q plans to do this, as follows:
 - Rewrite only the q_i-th number in the list with some integer so that Alice will not reach the destination.
Write a program to determine whether each plan is feasible.

-----Constraints-----
 - 1≤ N ≤ 5*10^5
 - 1≤ Q ≤ 5*10^5
 - 1≤ D ≤ 10^9
 - 1≤ d_i ≤ 10^9(1≤i≤N)
 - 1≤ q_i ≤ N(1≤i≤Q)
 - D and each d_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
N D
d_1 d_2 ... d_N
Q
q_1 q_2 ... q_Q

-----Output-----
Print Q lines. The i-th line should contain YES if the i-th plan is feasible, and NO otherwise.

-----Sample Input-----
4 10
3 4 3 3
2
4 3

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

For the first plan, Alice will already arrive at the destination by the first three moves, and therefore the answer is NO.
For the second plan, rewriting the third number in the list with 5 will prevent Alice from reaching the destination as shown in the following figure, and thus the answer is YES.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus has a computer with *n* processors. Also, his computer has *n* memory cells. We'll consider the processors numbered by integers from 1 to *n* and that the memory cells are consecutively numbered by integers from 1 to *n*.

Polycarpus needs to come up with a parallel program model. For each memory cell number *i* this program must record the value *n*<=-<=*i* to this cell. In other words, for each cell you've got to find the distance to cell *n*.

Let's denote the value that is written in the *i*-th cell as *a**i*. Initially, *a**i*<==<=1 (1<=≤<=*i*<=&lt;<=*n*) and *a**n*<==<=0. We will consider that only processor *i* can write values in the memory cell number *i*. All processors can read an information from some cell (several processors can read an information from some cell simultaneously).

The parallel program is executed in several steps. During each step we execute the parallel version of the increment operation. Executing the parallel version of the increment operation goes as follows:
 1.  Each processor independently of the other ones chooses some memory cell. Let's say that processor *i* has chosen a cell with number *c**i* (1<=≤<=*c**i*<=≤<=*n*). 1.  All processors simultaneously execute operation *a**i*<==<=*a**i*<=+<=*a**c**i*. 
Help Polycarpus come up with the parallel program model that is executed in exactly *k* steps. Calculate the operations that need to be executed. Note that after *k* steps for all *i*'s value *a**i* must be equal *n*<=-<=*i*.

Input Specification:
The first line contains two space-separated integers *n* and *k* (1<=≤<=*n*<=≤<=104,<=1<=≤<=*k*<=≤<=20).

It is guaranteed that at the given *n* and *k* the required sequence of operations exists.

Output Specification:
Print exactly *n*·*k* integers in *k* lines. In the first line print numbers *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=*n*) for the first increment operation. In the second line print the numbers for the second increment operation. In the *k*-th line print the numbers for the *k*-th increment operation.

As a result of the printed operations for any *i* value *a**i* must equal *n*<=-<=*i*.

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

Demo Output:
['1\n', '2 3 3\n3 3 3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given three points p1, p2, p, find the projection point x of p onto p1p2.

<image>

Constraints

* 1 ≤ q ≤ 1000
* -10000 ≤ xi, yi ≤ 10000
* p1 and p2 are not identical.

Input


xp1 yp1 xp2 yp2
q
xp0 yp0
xp1 yp1
...
xpq−1 ypq−1


In the first line, integer coordinates of p1 and p2 are given. Then, q queries are given for integer coordinates of p.

Output

For each query, print the coordinate of the projection point x. The output values should be in a decimal fraction with an error less than 0.00000001.

Examples

Input

0 0 2 0
3
-1 1
0 1
1 1


Output

-1.0000000000 0.0000000000
0.0000000000 0.0000000000
1.0000000000 0.0000000000


Input

0 0 3 4
1
2 5


Output

3.1200000000 4.1600000000

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