vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The battle of Thermopylae is between the Persians and Greeks during the Persian invasion. The Greek force is very small but determined to make a stand against the huge Persian army.

All of Greece is in fear, knowing that the army of the Persian king Xerxes has begun its invasion of Greece. Already the Thessalians had gone over to the Persian side, but some Greek cities has come together and forgotten their usual rivalries, determining to stop the Persian invasion. These cities agreed that Sparta would lead the Greek army, as its reputation in war was unmatched by any other Greek state. 

The Spartans has chosen to defend a narrow pass,between the mountains of central Greece and the sea, called Thermopylae. Greek force now waiting, made up of only 300 Spartans under their king, Leonidas.

King Xerxes has huge Persian army of 'N' soldiers.They are standing in straight line and each i^th  soldiers has power Pi . King Xerxes knows that collaboration between adjacent soldiers is more,So Xerxes want to send longest continuous chain of his soldiers among 'N' soldiers such that their power is strictly increasing.

As King Xerxes knows black magic,He can increase or decrease the power of i^th soldier.You are the advisor of King Xerxes,He asked you to tell the length of longest continuous increasing chain of soldiers of current army.

At any time, King Xerxes will do two operations : 

1 x y : Increase the power of x^th soldier by 'y' - (if negative, it means decrease.)

0 x y : Ask you the length of longest continuous increasing chain of soldiers in range [x , y] inclusive

Input :

First Line contains an integer indicating number of test cases 't'
For each case,there are two integers separated by a space in a line 'N' , 'Q' indicating number of soldiers in Persian army and number of queries.
Next Line contains 'N' space separated integers Pi indicating power of i^th soldier.
Next 'Q' lines contains three integers 'T' , 'x' and 'y' where T can be 0 or 1 indicating type of query.

Output :

For Each query of type 0,Print the answer as asked in the problem.

Constraints :

1 ≤ t ≤ 10 
1 ≤ N,Q ≤ 10^5 
1 ≤ Pi ≤ 10^9 
For type 1 query: 1 ≤ x ≤ N , |y| ≤ 10^9 
For type 0 query: 1 ≤ x ≤ y ≤ N 

SAMPLE INPUT
1
5 6
5 1 2 3 2 
0 1 5
1 5 4
0 1 5
0 3 5
1 3 10
0 3 5

SAMPLE OUTPUT
3
4
3
2

Explanation

Initial Power of soldiers : 5 1 2 3 2 
1) 0 1 5 : length of longest increasing chain in range [1,5] = 3 i.e {1,2,3}
2) 1 5 4 : update power of 5th solder by 4 : 5 1 2 3 6
3) 0 1 5 : length of longest increasing chain in range [1,5] = 4 i.e {1,2,3,6}
4) 0 3 5 : length of longest increasing chain in range [3,5] = 3 i.e {2,3,6}
5) 1 3 10 : update power of 3rd solder by 10 : 5 1 12 3 6
6) 0 3 5 : length of longest increasing chain in range [3,5] = 2 i.e {3,6}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A little boy Laurenty has been playing his favourite game Nota for quite a while and is now very hungry. The boy wants to make sausage and cheese sandwiches, but first, he needs to buy a sausage and some cheese.

The town where Laurenty lives in is not large. The houses in it are located in two rows, *n* houses in each row. Laurenty lives in the very last house of the second row. The only shop in town is placed in the first house of the first row.

The first and second rows are separated with the main avenue of the city. The adjacent houses of one row are separated by streets.

Each crosswalk of a street or an avenue has some traffic lights. In order to cross the street, you need to press a button on the traffic light, wait for a while for the green light and cross the street. Different traffic lights can have different waiting time.

The traffic light on the crosswalk from the *j*-th house of the *i*-th row to the (*j*<=+<=1)-th house of the same row has waiting time equal to *a**ij* (1<=≤<=*i*<=≤<=2,<=1<=≤<=*j*<=≤<=*n*<=-<=1). For the traffic light on the crossing from the *j*-th house of one row to the *j*-th house of another row the waiting time equals *b**j* (1<=≤<=*j*<=≤<=*n*). The city doesn't have any other crossings.

The boy wants to get to the store, buy the products and go back. The main avenue of the city is wide enough, so the boy wants to cross it exactly once on the way to the store and exactly once on the way back home. The boy would get bored if he had to walk the same way again, so he wants the way home to be different from the way to the store in at least one crossing.

Help Laurenty determine the minimum total time he needs to wait at the crossroads.

Input Specification:
The first line of the input contains integer *n* (2<=≤<=*n*<=≤<=50) — the number of houses in each row. 

Each of the next two lines contains *n*<=-<=1 space-separated integer — values *a**ij* (1<=≤<=*a**ij*<=≤<=100). 

The last line contains *n* space-separated integers *b**j* (1<=≤<=*b**j*<=≤<=100).

Output Specification:
Print a single integer — the least total time Laurenty needs to wait at the crossroads, given that he crosses the avenue only once both on his way to the store and on his way back home.

Demo Input:
['4\n1 2 3\n3 2 1\n3 2 2 3\n', '3\n1 2\n3 3\n2 1 3\n', '2\n1\n1\n1 1\n']

Demo Output:
['12\n', '11\n', '4\n']

Note:
The first sample is shown on the figure above. 

In the second sample, Laurenty's path can look as follows: 
 -  Laurenty crosses the avenue, the waiting time is 3; -  Laurenty uses the second crossing in the first row, the waiting time is 2; -  Laurenty uses the first crossing in the first row, the waiting time is 1; -  Laurenty uses the first crossing in the first row, the waiting time is 1; -  Laurenty crosses the avenue, the waiting time is 1; -  Laurenty uses the second crossing in the second row, the waiting time is 3. 
In the last sample Laurenty visits all the crossings, so the answer is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jim runs a big burger restaurant and, to entertain his customers, he always tell them jokes. He is running out of jokes and he needs you to help him find new ones.

An often heard programmer joke goes like this:

"Why do programmers always mix up Christmas and Halloween? Because Dec 25 is Oct 31".

Got it? :-) It is because $25_{10}$ (25 in Decimal) is equal to ${31}_{8}$ (31 in Octal).

If we are talking about dates, then let $m$ be the month and ${d}$ be the date and the corresponding value be $f(m,d)=d_m$ (${d}$ in base $m$). Let's describe some slightly different jokes:

"Why do programmers always mix up event $\boldsymbol{x}$ and event $y$? Because $f(m_x,d_x)=f(m_y,d_y)$". 

Here $m_{x}$ means the month of event ${x}$ and $d_x$ the day of event ${x}$. Similar for $m_y$ and $d_y$.  

Jim knows that his customers love this kind of jokes. That's why he gives you a calendar with $N$ events in it and asks you to count the number of such jokes he can create using the given events.

Two jokes ($(x_1,x_2)$ and $(y_{1},y_{2})$) differ if they don't contain the same events.

Note: 

The given numbers are all represented with digits from 0-9, that's why for months like ${11}$ or $12$, we can't use additional characters to represent 10 or 11. 

It might happen, that a special event cannot be used for a joke because the base conversion is invalid. For example $25_2$ is not possible since base $2$ can only contain digits ${0}$ and ${1}$.  

Unary base is invalid.  

Two events can have the same date.

Input Format

On the first line you will get $N$. The following $N$ lines you will be given the dates $m_i$, $d_i$ of the special events, each separated by a single space. 

Output Format

Print the number of jokes Jim can make.

Constraints 

$1\leq N\leq10^5$
($m_i$, $d_i$) will be a valid date in the Gregorian Calendar without leap day. 

Sample Input #1

2
10 25
8 31

Sample Output #1

1

Sample Input #2

2
2 25
2 25

Sample Output #2

0

Sample Input #3

2
11 10
10 11

Sample Output #3

1

Explanation

There are two special events happening on $(10,25)$ and $(8,31)$. He can make one joke, namely the one described in the description.

In the second test case there are no valid dates we can use for our jokes since 25 is not defined for base 2.

In the third test case $f(11,10)=10_{11}=11_{10}=f(10,11)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n computers in a row, all originally off, and Phoenix wants to turn all of them on. He will manually turn on computers one at a time. At any point, if computer i-1 and computer i+1 are both on, computer i (2 ≤ i ≤ n-1) will turn on automatically if it is not already on. Note that Phoenix cannot manually turn on a computer that already turned on automatically.

If we only consider the sequence of computers that Phoenix turns on manually, how many ways can he turn on all the computers? Two sequences are distinct if either the set of computers turned on manually is distinct, or the order of computers turned on manually is distinct. Since this number may be large, please print it modulo M.

Input

The first line contains two integers n and M (3 ≤ n ≤ 400; 10^8 ≤ M ≤ 10^9) — the number of computers and the modulo. It is guaranteed that M is prime.

Output

Print one integer — the number of ways to turn on the computers modulo M.

Examples

Input


3 100000007


Output


6


Input


4 100000007


Output


20


Input


400 234567899


Output


20914007

Note

In the first example, these are the 6 orders in which Phoenix can turn on all computers: 

  * [1,3]. Turn on computer 1, then 3. Note that computer 2 turns on automatically after computer 3 is turned on manually, but we only consider the sequence of computers that are turned on manually. 
  * [3,1]. Turn on computer 3, then 1. 
  * [1,2,3]. Turn on computer 1, 2, then 3. 
  * [2,1,3] 
  * [2,3,1] 
  * [3,2,1] 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a galaxy far away, there is a constant battle between the republic and the droid army. The droid army decided to launch their final attack on the republic. They have N space-fighters. 

Initially the $i^{th}$ fighter is located at (x_{i}, y_{i}). All of the space-fighters move with constant velocity V units/sec in the positive X direction. 
i.e., fighter at (x_{i}, y_{i}) moves to (x_{i}+V, y_{i}) in 1 second. 
The $ i^{th} $ space-fighter broadcasts enemy information at a frequency f_{i}.

The republic is not scared of the artificially intelligent droid force as they have Yoda. Yoda has a special power, at any time T he can choose a region of the droid army and block one specific frequency F. This power has one constraint; it can be applied only in the form of a two sided unbounded axis parallel rectangular box open towards the both the directions across X axis (refer image below for clarity). If a frequency (F) is blocked all the space-fighters in the region having the frequency F can’t communicate.

Given the initial positions of the space-fighters, and their velocity, you are to answer queries of the following form:

YU YD T

where YU, YD are the bounds on y-axis inside which YODA can block a frequency at time T. 
In the region described by the query, after a time T seconds from the start, if Yoda can chose one frequency (F) he wishes to, what is the maximum number of communications he can block?

Input Format 

Each test case is described as follows; the first line contains 3 space separated integers N - the number of space-fighters, Q - the number of queries you have to answer, and V - the velocity of the space-fighters separated by a single space. 

N lines follow, each containing 3 space separated integers x_{i}, y_{i}, and f_{i}, denoting the x co-ordinate, y co-ordinate and the frequency at which the $ i^{th} $ ship broadcasts respectively. Each of the next Q lines contain 3 space separated integers representing YU, YD, T respectively. Refer the figure for more clarity

Note: Points on the boundaries should be counted as well.

Output Format 

For each query you are to output a single integer denoting the result.

Constraints 

1 <= N <= 50000

1 <= Q <= 30000

1 <= V <= 10000

 $-10^{9}  $<= x_{i} <=  $10^{9} $

 $-10^{9} $ <= y_{i} <=  $10^{9} $

1 <= f_{i} <=  $10^{9} $

 $-10^{9} $ <= YU <= $ 10^{9} $

 $-10^{9}  $<= YD <=  $10^{9} $

1 <= T <= 10000

YU >= YD

Sample Input

5 5 82
-4 1 4
-3 -2 2
-3 5 1
0 -5 2
1 -1 2
1 -1 57
-2 -5 11
5 -5 40
-1 -5 16
5 -1 93

Sample Output

1
2
3
3
1

Explanation
Consider the points ships in the Y-range 1 to -1, they are the (-4, 1) and (1, -1), and both operate on different frequencies, hence the most times a frequency is repeated is once.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given an array which lists the current inventory of stock in your store and another array which lists the new inventory being delivered to your store today.

Your task is to write a function that returns the updated list of your current inventory **in alphabetical order**.

## Example

```python
cur_stock = [(25, 'HTC'), (1000, 'Nokia'), (50, 'Samsung'), (33, 'Sony'), (10, 'Apple')]
new_stock = [(5, 'LG'), (10, 'Sony'), (4, 'Samsung'), (5, 'Apple')]

update_inventory(cur_stock, new_stock)  ==>
[(15, 'Apple'), (25, 'HTC'), (5, 'LG'), (1000, 'Nokia'), (54, 'Samsung'), (43, 'Sony')]
```

___

*Kata inspired by the FreeCodeCamp's 'Inventory Update' algorithm.*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Getting bored was never an option for Debu. So to keep himself occupied Debu asked his brother Biswa to find the sum of elements in a subarray of an array. But then it was too boring to begin with and hence Biswa asked Debu to find the Fibo-sum of a subarray. 

But Debu was able to find the Fibo-sum of any subarray very easily so Biswa from time to time changed some element of the array to some other value and then continued asking him the Fibo-sum for different subarrays. 

A Fibo-sum is defined for he subarray [L, R] is defined as  ( \sum_{i = L}^{R}{A[i]*F[i-L]} ) \% Mod.

Here, F[0] = F[1] = 1 and F[i] = F[i - 1] + F[i - 2]
Input

 The first line contains 3 space seperated integers having N M Mod
 Next line contains a N space separated integers which are the values of the array
 Next M lines have queries. Each query is of one of the following type:

 1 L X: Change the value of array element at index L to X.
 2 L R   : Find the Fibo-sum of the subarray L to R .
Constraints:
1 ≤ N ≤ 200000

1 ≤ M ≤ 100000

L ≤ R

2 ≤ mod ≤ 1000000000

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

SAMPLE OUTPUT
7
12
4
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is given three numbers A, B, and C.

He wants to find whether he can select exactly two numbers out of these such that the product of the selected numbers is negative.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of three integers A, B, and C, the given numbers.

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

For each test case, output YES if Chef can select exactly two numbers out of these such that the product of the selected numbers is negative, NO otherwise.

You may print each character in uppercase or lowercase. For example, the strings NO, no, No, and nO, are all considered identical.

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

$1 ≤ T ≤ 1000$
$-10 ≤ A, B, C ≤ 10$

----- Sample Input 1 ------ 
5
1 5 7
-5 0 4
6 -1 0
-3 -5 -2
0 0 -4

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

----- explanation 1 ------ 
Test case $1$: There exists no way to select two numbers such that their product is negative.

Test case $2$: The product of $-5$ and $4$ is $-5\cdot 4 = -20$ which is negative.

Test case $3$: The product of $6$ and $-1$ is $6\cdot (-1) = -6$ which is negative.

Test case $4$: There exists no way to select two numbers such that their product is negative.

Test case $5$: There exists no way to select two numbers such that their product is negative.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yash loves playing with trees and gets especially excited when they have something to do with prime numbers. On his 20th birthday he was granted with a rooted tree of n nodes to answer queries on. Hearing of prime numbers on trees, Yash gets too intoxicated with excitement and asks you to help out and answer queries on trees for him. Tree is rooted at node 1. Each node i has some value ai associated with it. Also, integer m is given.

There are queries of two types:

  1. for given node v and integer value x, increase all ai in the subtree of node v by value x
  2. for given node v, find the number of prime numbers p less than m, for which there exists a node u in the subtree of v and a non-negative integer value k, such that au = p + m·k.

Input

The first of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 1000) — the number of nodes in the tree and value m from the problem statement, respectively.

The second line consists of n integers ai (0 ≤ ai ≤ 109) — initial values of the nodes.

Then follow n - 1 lines that describe the tree. Each of them contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of nodes connected by the i-th edge.

Next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries to proceed.

Each of the last q lines is either 1 v x or 2 v (1 ≤ v ≤ n, 0 ≤ x ≤ 109), giving the query of the first or the second type, respectively. It's guaranteed that there will be at least one query of the second type.

Output

For each of the queries of the second type print the number of suitable prime numbers.

Examples

Input

8 20
3 7 9 8 4 11 7 3
1 2
1 3
3 4
4 5
4 6
4 7
5 8
4
2 1
1 1 1
2 5
2 4


Output

3
1
1


Input

5 10
8 7 5 1 0
1 2
2 3
1 5
2 4
3
1 1 0
1 1 2
2 2


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Like most of the demanding childs.Pratik don't stop until he gets that.He keep on repeating the name of that thing again and again.
For example if he want a computer,He will keep on repeating "computer" again and again.
His dad has decided to answer to his demand as "Yes" or "No" without any delay.Otherwise there would be a lot of repercussions.So, randomly at certain interval,He just answer with "Yes" or "No" by using following rule that he will select
two integers a and b, if the element at the position a is same as element at position b in the repeating chant pratik then he will speak "Yes", Otherwise he will say "No".
Your work is to find the answer of his dad given the name of the demand that pratik is asking for and the random integer his dad has picked.


Input


First line of the input contains a string S, the name of the item he is demanding.
Next line contains an integer T, the number of pairs of integer to answer "Yes" or "No".
For each next N lines, each line contains two space separated integers ai and bi.
Next T lines each contain 2 integers, a and b.



Output

For each query, print "Yes" or "No" as described above

Constraints


1 ≤ |S| ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ a,b ≤ 10^18

 

Example
Input:
computer
4
3 7
2 10
5 21
11 26



Output:

No
Yes
Yes
No


Explanation

In the first case the character at 3rd position is 'm' and the character at 7th position is 'e' so the answer is "No"
In the second case the character at the 2nd position is 'o' and if we repeat the string (like computercomputercomputer...)
the character at 10th position is 'o' so the answer is "Yes"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Greg and his friends were walking in the forest. Overall there were n people walking, including Greg. Soon he found himself in front of a river. The guys immediately decided to get across the river. Luckily, there was a boat by the river bank, just where the guys were standing. We know that the boat can hold people with the total weight of at most k kilograms.

Greg immediately took a piece of paper and listed there the weights of all people in his group (including himself). It turned out that each person weights either 50 or 100 kilograms. Now Greg wants to know what minimum number of times the boat needs to cross the river to transport the whole group to the other bank. The boat needs at least one person to navigate it from one bank to the other. As the boat crosses the river, it can have any non-zero number of passengers as long as their total weight doesn't exceed k.

Also Greg is wondering, how many ways there are to transport everybody to the other side in the minimum number of boat rides. Two ways are considered distinct if during some ride they have distinct sets of people on the boat.

Help Greg with this problem.

 


-----Input-----

The first line contains two integers n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ 5000) — the number of people, including Greg, and the boat's weight limit. The next line contains n integers — the people's weights. A person's weight is either 50 kilos or 100 kilos.

You can consider Greg and his friends indexed in some way.


-----Output-----

In the first line print an integer — the minimum number of rides. If transporting everyone to the other bank is impossible, print an integer -1.

In the second line print the remainder after dividing the number of ways to transport the people in the minimum number of rides by number 1000000007 (10^9 + 7). If transporting everyone to the other bank is impossible, print integer 0.


-----Examples-----
Input
1 50
50

Output
1
1

Input
3 100
50 50 100

Output
5
2

Input
2 50
50 50

Output
-1
0



-----Note-----

In the first test Greg walks alone and consequently, he needs only one ride across the river.

In the second test you should follow the plan:

  transport two 50 kg. people;  transport one 50 kg. person back;  transport one 100 kg. person;  transport one 50 kg. person back;  transport two 50 kg. people. 

That totals to 5 rides. Depending on which person to choose at step 2, we can get two distinct ways.

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