vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Peter is in charge of food service on a passenger train. The train has $n$ cars ordered sequentially starting from the locomotive. The $i$-th car has $p_ i$ passengers. There are $m$ food carts Peter may put into service. Each food cart serves a unique type of food. The $j$-th food cart can move between the $l_ j$-th car and the $r_ j$-th car (both inclusive) and serve the passengers in these cars.

The passengers on the train are not only hungry, but also adventurous: as long as a food cart is in service, they would love to try it! A passenger will be happy if he/she sits in a car that is served by all the food carts that are in service. Peter would like to design service plans that run one or more of the $m$ food carts so that at least $k$ of the passengers on the train are happy.

Peter wants to count the number of different service plans he may choose from (modulo $10^9 + 7$). Two service plans are different if one food cart is put into service in one plan but not in the other plan.

-----Input-----
The first line has three integers $n$, $m$, and $k$ ($1 \leq n, m \leq 2 \cdot 10^5, 1 \leq k \leq 10^{14}$). The next line has $n$ integers. The $i$-th integer is $p_ i$ ($1 \leq p_ i \leq 10^9 $), the number of passengers in the $i$-th car. Each of the next $m$ lines describes a food cart. The $j$-th of these lines has two integers $l_ j$ and $r_ j$ ($1 \leq l_ j \leq r_ j \leq n$), giving the service range of the $j$-th food cart.

-----Output-----
Output the number of different service plans, modulo $10^9 + 7$.

-----Examples-----
Sample Input 1:
4 3 3
1 2 3 4
1 2
2 3
3 4
Sample Output 1:
4

Sample Input 2:
5 4 6
1 2 3 4 5
1 4
2 3
3 5
4 5
Sample Output 2:
5

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

There is an arithmetic progression A with the number of terms N, the first term a, and the tolerance d. Since M statements that update the sequence are given in the following format, find the value of the K item when the sequence A is updated M times in the given order.

* The i-th statement is represented by the three integers xi, yi, zi (1 ≤ i ≤ M).

* If xi is 0, swap the value of yi item and the value of zi item.

* If xi is 1, rewrite the value of yi item to the value of zi item.

Constraints

* 1 ≤ N ≤ 108
* 1 ≤ a ≤ 5
* 1 ≤ d ≤ 5
* 1 ≤ M ≤ 10
* 0 ≤ xi ≤ 1 (1 ≤ i ≤ M)
* 1 ≤ yi ≤ N (1 ≤ i ≤ M)
* 1 ≤ zi ≤ N (1 ≤ i ≤ M)
* yi ≠ zi (1 ≤ i ≤ M)
* 1 ≤ K ≤ N

Input


N
a d
M
x1 y1 z1
x2 y2 z2
...
xM yM zM
K


The first line is given one integer N. On the second line, two integers a and d are given, separated by blanks. On the third line, one integer M is given. Of the M lines from the 4th line, the ith line is given three integers xi, yi, and zi representing the i-th statement, separated by blanks. The last line is given one integer K.

Output

Output the K item when the sequence A is updated M times in the order given by the input.

Examples

Input

5
2 3
3
0 2 5
0 3 5
1 2 4
2


Output

11


Input

6
5 5
4
0 1 2
1 1 2
0 4 1
1 1 6
3


Output

15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Sum of the k-th Powers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are well-known formulas: , , . Also mathematicians found similar formulas for higher degrees.

Find the value of the sum  modulo 109<=+<=7 (so you should find the remainder after dividing the answer by the value 109<=+<=7).

Input Specification:
The only line contains two integers *n*,<=*k* (1<=≤<=*n*<=≤<=109,<=0<=≤<=*k*<=≤<=106).

Output Specification:
Print the only integer *a* — the remainder after dividing the value of the sum by the value 109<=+<=7.

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

Demo Output:
['10\n', '30\n', '100\n', '4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of numbers, return the difference between the largest and smallest values. 

For example:

`[23, 3, 19, 21, 16]` should return `20` (i.e., `23 - 3`).

`[1, 434, 555, 34, 112]` should return `554` (i.e., `555 - 1`).

The array will contain a minimum of two elements. Input data range guarantees that `max-min` will cause no integer overflow.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given an array of integers whose elements have both a negative and a positive value, except for one integer that is either only negative or only positive. Your task will be to find that integer. 

Examples:

`[1, -1, 2, -2, 3] => 3`

`3` has no matching negative appearance

`[-3, 1, 2, 3, -1, -4, -2] => -4`

`-4` has no matching positive appearance

`[1, -1, 2, -2, 3, 3] => 3`

(the only-positive or only-negative integer may appear more than once)

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a non-negative integer n, its decimal representation consists of at most 100 digits and doesn't contain leading zeroes.

Your task is to determine if it is possible in this case to remove some of the digits (possibly not remove any digit at all) so that the result contains at least one digit, forms a non-negative integer, doesn't have leading zeroes and is divisible by 8. After the removing, it is forbidden to rearrange the digits.

If a solution exists, you should print it.


-----Input-----

The single line of the input contains a non-negative integer n. The representation of number n doesn't contain any leading zeroes and its length doesn't exceed 100 digits. 


-----Output-----

Print "NO" (without quotes), if there is no such way to remove some digits from number n. 

Otherwise, print "YES" in the first line and the resulting number after removing digits from number n in the second line. The printed number must be divisible by 8.

If there are multiple possible answers, you may print any of them.


-----Examples-----
Input
3454

Output
YES
344

Input
10

Output
YES
0

Input
111111

Output
NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Many students live in a dormitory. A dormitory is a whole new world of funny amusements and possibilities but it does have its drawbacks. 

There is only one shower and there are multiple students who wish to have a shower in the morning. That's why every morning there is a line of five people in front of the dormitory shower door. As soon as the shower opens, the first person from the line enters the shower. After a while the first person leaves the shower and the next person enters the shower. The process continues until everybody in the line has a shower.

Having a shower takes some time, so the students in the line talk as they wait. At each moment of time the students talk in pairs: the (2*i*<=-<=1)-th man in the line (for the current moment) talks with the (2*i*)-th one. 

Let's look at this process in more detail. Let's number the people from 1 to 5. Let's assume that the line initially looks as 23154 (person number 2 stands at the beginning of the line). Then, before the shower opens, 2 talks with 3, 1 talks with 5, 4 doesn't talk with anyone. Then 2 enters the shower. While 2 has a shower, 3 and 1 talk, 5 and 4 talk too. Then, 3 enters the shower. While 3 has a shower, 1 and 5 talk, 4 doesn't talk to anyone. Then 1 enters the shower and while he is there, 5 and 4 talk. Then 5 enters the shower, and then 4 enters the shower.

We know that if students *i* and *j* talk, then the *i*-th student's happiness increases by *g**ij* and the *j*-th student's happiness increases by *g**ji*. Your task is to find such initial order of students in the line that the total happiness of all students will be maximum in the end. Please note that some pair of students may have a talk several times. In the example above students 1 and 5 talk while they wait for the shower to open and while 3 has a shower.

Input Specification:
The input consists of five lines, each line contains five space-separated integers: the *j*-th number in the *i*-th line shows *g**ij* (0<=≤<=*g**ij*<=≤<=105). It is guaranteed that *g**ii*<==<=0 for all *i*.

Assume that the students are numbered from 1 to 5.

Output Specification:
Print a single integer — the maximum possible total happiness of the students.

Demo Input:
['0 0 0 0 9\n0 0 0 0 0\n0 0 0 0 0\n0 0 0 0 0\n7 0 0 0 0\n', '0 43 21 18 2\n3 0 21 11 65\n5 2 0 1 4\n54 62 12 0 99\n87 64 81 33 0\n']

Demo Output:
['32\n', '620\n']

Note:
In the first sample, the optimal arrangement of the line is 23154. In this case, the total happiness equals:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Elephant has an integer a, written in the binary notation. He wants to write this number on a piece of paper.

To make sure that the number a fits on the piece of paper, the Little Elephant ought to delete exactly one any digit from number a in the binary record. At that a new number appears. It consists of the remaining binary digits, written in the corresponding order (possible, with leading zeroes).

The Little Elephant wants the number he is going to write on the paper to be as large as possible. Help him find the maximum number that he can obtain after deleting exactly one binary digit and print it in the binary notation.


-----Input-----

The single line contains integer a, written in the binary notation without leading zeroes. This number contains more than 1 and at most 10^5 digits.


-----Output-----

In the single line print the number that is written without leading zeroes in the binary notation — the answer to the problem.


-----Examples-----
Input
101

Output
11

Input
110010

Output
11010



-----Note-----

In the first sample the best strategy is to delete the second digit. That results in number 11_2 = 3_10.

In the second sample the best strategy is to delete the third or fourth digits — that results in number 11010_2 = 26_10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has four cookies with deliciousness A, B, C, and D. He will choose one or more from those cookies and eat them. Is it possible that the sum of the deliciousness of the eaten cookies is equal to that of the remaining cookies?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A,B,C,D \leq 10^{8}

-----Input-----
Input is given from Standard Input in the following format:
A B C D

-----Output-----
If it is possible that the sum of the deliciousness of the eaten cookies is equal to that of the remaining cookies, print Yes; otherwise, print No.

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

-----Sample Output-----
Yes

 - If he eats the cookies with deliciousness 1 and 4, the sum of the deliciousness of the eaten cookies will be equal to that of the remaining cookies.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of n distinct sorted numbers. You are also given m queries of the form x. Your task is to output the index of the number x within the array. If x is not within the array output -1. 

Constraints
The values in the array will range from -10^9 to 10^9.
1 ≤ n ≤ 10^5
1 ≤ m ≤ 10^5

Input and Output
The input consists of n on the first line followed by the array on the next. After that m on the next line followed by m queries. For each of the m queries, print on a seperate line, the index of the number in the array or -1 if the number is not in the array.

SAMPLE INPUT
5
1 2 3 7 10
3
1
2
4

SAMPLE OUTPUT
0
1
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nick is a bird watcher and often visits the forum “CrowFinders” to discuss his hobby with like-minded people. CrowFinders has a voting system where users can upvote or downvote comments, which increases or decreases their score by $1$. This means that each comment can end up with any integer score (including negative scores). Once when Nick was browsing a heated discussion about the classification of jackdaws as crows, he found something very pleasing: a chain of comments that alternated between positive and negative scores. But a few days later, he found that the comment chain was no longer alternating. Now Nick wants to make it alternating again. 

A comment chain is alternating if the scores $s_1, s_2, \ldots , s_ n$ of the comments all are non-zero, and every pair of adjacent scores $s_ i$, $s_{i+1}$ have opposite signs. In particular, a single comment with a non-zero score or even a comment chain without any comment is an alternating comment chain.

There are two operations Nick can do to make the comment chain alternating:
 - Create a fake account and upvote/downvote some of the comments. This increases/decreases their respective scores by $1$. Each fake account can only upvote/downvote each comment at most once, but it can vote on any subset of the comments. It takes $c$ seconds to create an account and use it to vote (regardless of how many comments are upvoted/downvoted).
 - Report one specific comment to remove it from the chain. Thinking of convincing reasons for the report takes $r$ seconds. (Nick is an excellent arguer, so once the report is filed, the comment is guaranteed to be removed.)

Nick can apply these operations in any order, any number of times. How fast can he make the comment chain alternating?

For example, consider Sample Input 1 below, where the scores in the comment chain are $8, 8, 2, -2$, and it takes Nick $10$ seconds to create an account and $50$ seconds to file a report for one comment. In this case it is optimal to first create $3$ fake accounts and use them to upvote the fourth comment and downvote the third, followed by reporting the first comment. This results in the scores $8, -1, 1$, which is an alternating chain. The time used for this is $80$ seconds.

-----Input-----
The input consists of:
 - One line with three integers $n$, $c$, and $r$ ($1 \leq n \leq 5\cdot 10^5$, $1 \leq c,r \leq 10^9$), the number of comments in the chain, the time it takes to create a fake account and the time it takes to report one comment respectively.
 - One line with $n$ integers $s_1, \ldots , s_ n$ ($-10^9 \leq s_ i \leq 10^9$ for all $i$), the current score of each comment in the chain.

-----Output-----
Output the smallest time to make the comment chain alternating by applying the operations above.

-----Examples-----
Sample Input:
4 10 50
8 8 2 -2
Sample Output:
80

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Natasha is planning an expedition to Mars for $n$ people. One of the important tasks is to provide food for each participant.

The warehouse has $m$ daily food packages. Each package has some food type $a_i$.

Each participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.

Formally, for each participant $j$ Natasha should select his food type $b_j$ and each day $j$-th participant will eat one food package of type $b_j$. The values $b_j$ for different participants may be different.

What is the maximum possible number of days the expedition can last, following the requirements above?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 100$) — the number of the expedition participants and the number of the daily food packages available.

The second line contains sequence of integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le 100$), where $a_i$ is the type of $i$-th food package.


-----Output-----

Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print 0.


-----Examples-----
Input
4 10
1 5 2 1 1 1 2 5 7 2

Output
2

Input
100 1
1

Output
0

Input
2 5
5 4 3 2 1

Output
1

Input
3 9
42 42 42 42 42 42 42 42 42

Output
3



-----Note-----

In the first example, Natasha can assign type $1$ food to the first participant, the same type $1$ to the second, type $5$ to the third and type $2$ to the fourth. In this case, the expedition can last for $2$ days, since each participant can get two food packages of his food type (there will be used $4$ packages of type $1$, two packages of type $2$ and two packages of type $5$).

In the second example, there are $100$ participants and only $1$ food package. In this case, the expedition can't last even $1$ day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n robots driving along an OX axis. There are also two walls: one is at coordinate 0 and one is at coordinate m.

The i-th robot starts at an integer coordinate x_i~(0 < x_i < m) and moves either left (towards the 0) or right with the speed of 1 unit per second. No two robots start at the same coordinate.

Whenever a robot reaches a wall, it turns around instantly and continues his ride in the opposite direction with the same speed.

Whenever several robots meet at the same integer coordinate, they collide and explode into dust. Once a robot has exploded, it doesn't collide with any other robot. Note that if several robots meet at a non-integer coordinate, nothing happens.

For each robot find out if it ever explodes and print the time of explosion if it happens and -1 otherwise.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Then the descriptions of t testcases follow.

The first line of each testcase contains two integers n and m (1 ≤ n ≤ 3 ⋅ 10^5; 2 ≤ m ≤ 10^8) — the number of robots and the coordinate of the right wall.

The second line of each testcase contains n integers x_1, x_2, ..., x_n (0 < x_i < m) — the starting coordinates of the robots.

The third line of each testcase contains n space-separated characters 'L' or 'R' — the starting directions of the robots ('L' stands for left and 'R' stands for right).

All coordinates x_i in the testcase are distinct.

The sum of n over all testcases doesn't exceed 3 ⋅ 10^5.

Output

For each testcase print n integers — for the i-th robot output the time it explodes at if it does and -1 otherwise.

Example

Input


5
7 12
1 2 3 4 9 10 11
R R L L R R R
2 10
1 6
R R
2 10
1 3
L L
1 10
5
R
7 8
6 1 7 2 3 5 4
R L R L L L L


Output


1 1 1 1 2 -1 2 
-1 -1 
2 2 
-1 
-1 2 7 3 2 7 3 

Note

Here is the picture for the seconds 0, 1, 2 and 3 of the first testcase: 

<image>

Notice that robots 2 and 3 don't collide because they meet at the same point 2.5, which is not integer.

After second 3 robot 6 just drive infinitely because there's no robot to collide with.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob play a game. Alice has got n treasure chests (the i-th of which contains a_i coins) and m keys (the j-th of which she can sell Bob for b_j coins).

Firstly, Alice puts some locks on the chests. There are m types of locks, the locks of the j-th type can only be opened with the j-th key. To put a lock of type j on the i-th chest, Alice has to pay c_{i,j} dollars. Alice can put any number of different types of locks on each chest (possibly, zero).

Then, Bob buys some of the keys from Alice (possibly none, possibly all of them) and opens each chest he can (he can open a chest if he has the keys for all of the locks on this chest). Bob's profit is the difference between the total number of coins in the opened chests and the total number of coins he spends buying keys from Alice. If Bob's profit is strictly positive (greater than zero), he wins the game. Otherwise, Alice wins the game.

Alice wants to put some locks on some chests so no matter which keys Bob buys, she always wins (Bob cannot get positive profit). Of course, she wants to spend the minimum possible number of dollars on buying the locks. Help her to determine whether she can win the game at all, and if she can, how many dollars she has to spend on the locks.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 6) — the number of chests and the number of keys, respectively.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 4), where a_i is the number of coins in the i-th chest.

The third line contains m integers b_1, b_2, ..., b_m (1 ≤ b_j ≤ 4), where b_j is the number of coins Bob has to spend to buy the j-th key from Alice.

Then n lines follow. The i-th of them contains m integers c_{i,1}, c_{i,2}, ..., c_{i,m} (1 ≤ c_{i,j} ≤ 10^7), where c_{i,j} is the number of dollars Alice has to spend to put a lock of the j-th type on the i-th chest.

Output

If Alice cannot ensure her victory (no matter which locks she puts on which chests, Bob always has a way to gain positive profit), print -1.

Otherwise, print one integer — the minimum number of dollars Alice has to spend to win the game regardless of Bob's actions.

Examples

Input


2 3
3 3
1 1 4
10 20 100
20 15 80


Output


205


Input


2 3
3 3
2 1 4
10 20 100
20 15 80


Output


110


Input


2 3
3 4
1 1 4
10 20 100
20 15 80


Output


-1

Note

In the first example, Alice should put locks of types 1 and 3 on the first chest, and locks of type 2 and 3 on the second chest.

In the second example, Alice should put locks of types 1 and 2 on the first chest, and a lock of type 3 on the second chest.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya wants to minimize a tree. He can perform the following operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length a_0 = v, a_1, ..., a_{k}, and b_0 = v, b_1, ..., b_{k}. Additionally, vertices a_1, ..., a_{k}, b_1, ..., b_{k} must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices b_1, ..., b_{k} can be effectively erased: [Image] 

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.


-----Input-----

The first line of input contains the number of vertices n (2 ≤ n ≤ 2·10^5).

Next n - 1 lines describe edges of the tree. Each of these lines contains two space-separated integers u and v (1 ≤ u, v ≤ n, u ≠ v) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.


-----Output-----

If it is impossible to obtain a path, print -1. Otherwise, print the minimum number of edges in a possible path.


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

Output
3

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

Output
-1



-----Note-----

In the first sample case, a path of three edges is obtained after merging paths 2 - 1 - 6 and 2 - 4 - 5.

It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1 - 3 - 4 and 1 - 5 - 6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.

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