vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Kekoland is a country with n beautiful cities numbered from left to right and connected by n - 1 roads. The i-th road connects cities i and i + 1 and length of this road is wi kilometers. 

When you drive in Kekoland, each time you arrive in city i by car you immediately receive gi liters of gas. There is no other way to get gas in Kekoland.

You were hired by the Kekoland president Keko to organize the most beautiful race Kekoland has ever seen. Let race be between cities l and r (l ≤ r). Race will consist of two stages. On the first stage cars will go from city l to city r. After completing first stage, next day second stage will be held, now racers will go from r to l with their cars. Of course, as it is a race, racers drive directly from start city to finish city. It means that at the first stage they will go only right, and at the second stage they go only left. Beauty of the race between l and r is equal to r - l + 1 since racers will see r - l + 1 beautiful cities of Kekoland. Cars have infinite tank so racers will take all the gas given to them.

At the beginning of each stage racers start the race with empty tank (0 liters of gasoline). They will immediately take their gasoline in start cities (l for the first stage and r for the second stage) right after the race starts. 

It may not be possible to organize a race between l and r if cars will run out of gas before they reach finish.

You have k presents. Each time you give a present to city i its value gi increases by 1. You may distribute presents among cities in any way (also give many presents to one city, each time increasing gi by 1). What is the most beautiful race you can organize?

Each car consumes 1 liter of gas per one kilometer.

Input

The first line of the input contains two integers n and k (2 ≤ n ≤ 100 000, 0 ≤ k ≤ 109) — the number of cities in Kekoland and the number of presents you have, respectively.

Next line contains n - 1 integers. The i-th of them is wi (1 ≤ wi ≤ 109) — the length of the road between city i and i + 1. 

Next line contains n integers. The i-th of them is gi (0 ≤ gi ≤ 109) — the amount of gas you receive every time you enter city i.

Output

Print a single line — the beauty of the most beautiful race you can organize.

Examples

Input

4 4
2 2 2
1 1 1 1


Output

4


Input

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


Output

7

Note

In first sample if you give one present to each city then it will be possible to make a race between city 1 and city 4.

In second sample you should add 1 to g5 and 4 to g6, then it will be possible to make a race between cities 2 and 8. 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Carl is a beginner magician. He has *a* blue, *b* violet and *c* orange magic spheres. In one move he can transform two spheres of the same color into one sphere of any other color. To make a spell that has never been seen before, he needs at least *x* blue, *y* violet and *z* orange spheres. Can he get them (possible, in multiple actions)?

Input Specification:
The first line of the input contains three integers *a*, *b* and *c* (0<=≤<=*a*,<=*b*,<=*c*<=≤<=1<=000<=000) — the number of blue, violet and orange spheres that are in the magician's disposal.

The second line of the input contains three integers, *x*, *y* and *z* (0<=≤<=*x*,<=*y*,<=*z*<=≤<=1<=000<=000) — the number of blue, violet and orange spheres that he needs to get.

Output Specification:
If the wizard is able to obtain the required numbers of spheres, print "Yes". Otherwise, print "No".

Demo Input:
['4 4 0\n2 1 2\n', '5 6 1\n2 7 2\n', '3 3 3\n2 2 2\n']

Demo Output:
['Yes\n', 'No\n', 'Yes\n']

Note:
In the first sample the wizard has 4 blue and 4 violet spheres. In his first action he can turn two blue spheres into one violet one. After that he will have 2 blue and 5 violet spheres. Then he turns 4 violet spheres into 2 orange spheres and he ends up with 2 blue, 1 violet and 2 orange spheres, which is exactly what he needs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Bipartite Graph is an undirected graph whose vertices can be partitioned into $2$ sets such that, for each edge $(u, v)$, $u$ and $v$ belong to different sets.

Socket has challenged Bash to a Bipartite Battle. In the Bipartite Battle, Bash and Socket play a game with Bipartite Graphs.

The Bipartite Battle happens as follows:
 - Socket draws $N$ bipartite graphs. The $i$-th graph has $2$ sets of vertices, one with $a_ i$ vertices, and the other with $b_ i$ vertices.
 - Then the $2$ players, Bash and Socket alternatively take turns. In each turn, a player must choose exactly one non-empty graph, then delete exactly one edge or exactly one vertex of the chosen graph. If the player deletes one vertex, all edges adjacent to it are also deleted.
 - The player who cannot move loses. Note that this can only happen when all edges and all vertices of all graphs have been deleted.
 - Bash plays first.

Of course, Socket does not want to play fair. Socket plans to draw bipartite graphs such that he always wins.

How many ways can Socket draw $N$ bipartite graphs, so that he always wins, assuming both players play optimally?

-----Notes-----
For the $i$-th bipartite graph, let’s number the vertices in first set from $1$ to $a_ i$, and the vertices in second set from $1$ to $b_ i$.

An edge connecting vertex $u$ in first set and vertex $v$ in second set is denoted as $(u, v)$.

Two drawings of bipartite graphs are considered different iff there exists an index $j$ and a pair of integers $(u, v)$, such that:
 - $(u, v)$ is an edge of $j$-th graph in one drawing.
 - $(u, v)$ is NOT an edge of $j$-th graph in the other drawing.

-----Input-----
The first line of input contains the integer $N$ $(1 \le N \le 10^5)$.

$N$ lines follow, each line contains exactly $2$ space-separated integers $a_ i$ and $b_ i$$(1 \le a_ i, b_ i \le 10^9)$.

-----Output-----
Print exactly one integer — the number of ways Socket can draw $N$ bipartite graphs, modulo $10^9 + 7$.

-----Examples-----
Sample Input:
1
1 1
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya is doing his maths homework. He has an expression of form <image>, where x1, x2, ..., xn are digits from 1 to 9, and sign <image> represents either a plus '+' or the multiplication sign '*'. Vanya needs to add one pair of brackets in this expression so that to maximize the value of the resulting expression.

Input

The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs  +  and  * . 

The number of signs  *  doesn't exceed 15.

Output

In the first line print the maximum possible value of an expression.

Examples

Input

3+5*7+8*4


Output

303


Input

2+3*5


Output

25


Input

3*4*5


Output

60

Note

Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.

Note to the second sample test. (2 + 3) * 5 = 25.

Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that this is a bit harder version of the problem foodreview.

Frida is a writer for Cosmopolitan who writes restaurant reviews. She enjoys it a lot, but it seems that, throughout the years, she has reviewed all the restaurants on Earth. It’s now time to move one level up; she is going to review the food served by the airlines, so that the readers can make better decisions on which flights to take.

Her boss gave her a list of flight connections that she needs to review for the upcoming issue of Cosmopolitan. She knows that they serve the same food in both directions of every flight, so she only needs to take it once. She realized that she will need to take some additional flights, because she can not make all reviews using only flights in the list from her boss. Therefore she did some quick research and made a list of additional flights which she might take. She will not review the food on these flights; they will only be used so that she can make all the reviews.

Frida’s goal is to make all the reviews while spending the least money on flight tickets. Her office is in Stockholm, so she starts and ends her journey there. Each flight is both ways between two cities and has a fixed price in both directions. You can assume that it is possible to make all the reviews using some of the additional flights.

For the purposes of this problem we ignore the price Frida has to pay for accommodation and we also ignore the departure and arrival times of flights by assuming that every flight is very often and reasonably short. We only focus on the total price of the flights.

-----Input-----
The first line contains $2$ space separated integers $N, R, (2\leq N\leq 15, 0\leq R\leq 105)$, where $N$ is the number of airports mentioned in the input and $R$ is the number of flights to review. The airports are numbered $1, \dots , N$ and Stockholm has number $1$.

The next $R$ lines describe the $R$ flights to review. Each line contains 3 space separated integers $a, b, c, (1\leq a, b\leq N, 1\leq c\leq 10000)$, where $a, b$ denote 2 distinct airports and $c$ is the cost of the flight in Swedish kronor in both directions. No pair of $2$ cities is listed twice.

The next line contains an integer $F$, $(0\leq F\leq 250)$, the number of additional flights available. The next $F$ lines contain descriptions of flights in the same format as above. There may be more flights between a pair of cities. You may assume that it is possible to make all the reviews using some of these additional flights.

-----Output-----
Output one line with one integer – the lowest total cost of flight tickets, such that Frida can make all the reviews and return back to Stockholm.

-----Examples-----
Sample Input:
5 3
1 2 1000
2 3 1000
4 5 500
2
1 4 300
3 5 300
Sample Output:
3100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Marie invented a Time Machine and wants to test it by time-traveling to visit Russia on the Day of the Programmer (the 256th day of the year) during a year in the inclusive range from 1700 to 2700. 

From 1700 to 1917, Russia's official calendar was the Julian calendar; since 1919 they used the Gregorian calendar system. The transition from the Julian to Gregorian calendar system occurred in 1918, when the next day after January 31st was February 14th. This means that in 1918, February 14th was the 32nd day of the year in Russia.

In both calendar systems, February is the only month with a variable amount of days; it has 29 days during a leap year, and 28 days during all other years. In the Julian calendar, leap years are divisible by 4; in the Gregorian calendar, leap years are either of the following:

Divisible by 400.
Divisible by 4 and not divisible by 100.

Given a year, $y$, find the date of the 256th day of that year according to the official Russian calendar during that year. Then print it in the format dd.mm.yyyy, where dd is the two-digit day, mm is the two-digit month, and yyyy is $y$.

For example, the given $year$ = 1984.  1984 is divisible by 4, so it is a leap year.  The 256th day of a leap year after 1918 is September 12, so the answer is $12.09.1984$.  

Function Description  

Complete the dayOfProgrammer function in the editor below.  It should return a string representing the date of the 256th day of the year given.  

dayOfProgrammer has the following parameter(s):  

year: an integer  

Input Format

A single integer denoting year $y$.

Constraints

1700 \le y \le 2700

Output Format

Print the full date of Day of the Programmer during year $y$ in the format dd.mm.yyyy, where dd is the two-digit day, mm is the two-digit month, and yyyy is $y$.

Sample Input 0
2017

Sample Output 0
13.09.2017

Explanation 0

In the year $y$ = 2017, January has 31 days, February has 28 days, March has 31 days, April has 30 days, May has 31 days, June has 30 days, July has 31 days, and August has 31 days. When we sum the total number of days in the first eight months, we get 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 = 243. Day of the Programmer is the 256th day, so then calculate 256 - 243 = 13 to determine that it falls on day 13 of the 9th month (September). We then print the full date in the specified format, which is 13.09.2017.

Sample Input 1
2016

Sample Output 1
12.09.2016

Explanation 1

Year $y$ = 2016 is a leap year, so February has 29 days but all the other months have the same number of days as in 2017. When we sum the total number of days in the first eight months, we get 31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 = 244. Day of the Programmer is the 256th day, so then calculate 256 - 244 = 12 to determine that it falls on day 12 of the 9th month (September). We then print the full date in the specified format, which is 12.09.2016.

Sample Input 2
1800

Sample Output 2
12.09.1800

Explanation 2

Since 1800 is leap year as per Julian calendar. Day lies on 12 September.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers n (1 ≤ n ≤ 10^9) and k (1 ≤ k ≤ 100). Represent the number n as the sum of k positive integers of the same parity (have the same remainder when divided by 2).

In other words, find a_1, a_2, …, a_k such that all a_i>0, n = a_1 + a_2 + … + a_k and either all a_i are even or all a_i are odd at the same time.

If such a representation does not exist, then report it.

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases in the input. Next, t test cases are given, one per line.

Each test case is two positive integers n (1 ≤ n ≤ 10^9) and k (1 ≤ k ≤ 100).

Output

For each test case print:

  * YES and the required values a_i, if the answer exists (if there are several answers, print any of them); 
  * NO if the answer does not exist. 



The letters in the words YES and NO can be printed in any case.

Example

Input


8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9


Output


YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120

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

When compressing sequences of symbols, it is useful to have many equal symbols follow each other, because then they can be encoded with a run length encoding. For example, RLE encoding of `"aaaabbbbbbbbbbbcccccc"` would give something like `4a 11b 6c`.

(Look [here](http://www.codewars.com/kata/run-length-encoding/) for learning more about the run-length-encoding.)

Of course, RLE is interesting only if the string contains many identical consecutive characters. But what bout human readable text? Here comes the Burrows-Wheeler-Transformation.

Transformation
-------------
There even exists a transformation, which brings equal symbols closer together, it is called the **Burrows-Wheeler-Transformation**. The forward transformation works as follows: Let's say we have a sequence with length n, first write every shift of that string into a *n x n* matrix:
```
Input: "bananabar"

b a n a n a b a r
r b a n a n a b a
a r b a n a n a b
b a r b a n a n a
a b a r b a n a n
n a b a r b a n a
a n a b a r b a n
n a n a b a r b a
a n a n a b a r b
```
Then we sort that matrix by its rows. The output of the transformation then is the **last column** and the **row index** in which the original string is in:
```
               .-.
a b a r b a n a n
a n a b a r b a n
a n a n a b a r b
a r b a n a n a b
b a n a n a b a r <- 4
b a r b a n a n a
n a b a r b a n a
n a n a b a r b a
r b a n a n a b a
               '-'

Output: ("nnbbraaaa", 4)
```

```if:java
To handle the two kinds of output data, we will use the preloaded class `BWT`, whose contract is the following:

    public class BWT {
        
        public String s;
        public int n;
        
        public BWT(String s, int n)
        
        @Override public String  toString()
        @Override public boolean equals(Object o)
        @Override public int     hashCode()
    }

```

Of course we want to restore the original input, therefore you get the following hints:

1. The output contains the last matrix column.
2. The first column can be acquired by sorting the last column.
3. **For every row of the table:** Symbols in the first column follow on symbols in the last column, in the same way they do in the input string.
4. You don't need to reconstruct the whole table to get the input back.

Goal
----

The goal of this Kata is to write both, the `encode` and `decode` functions. Together they should work as the identity function on lists. (*Note:* For the empty input, the row number is ignored.)

Further studies
--------------
You may have noticed that symbols are not always consecutive, but just in proximity, after the transformation. If you're interested in how to deal with that, you should have a look at [this Kata](http://www.codewars.com/kata/move-to-front-encoding/).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shubham recently learned the lexicographical order in strings.

Now, he has two strings s1  and  s2  of the equal size and Shubham wants to compare those two strings lexicographically.

Help Shubham with the strings comparison.

Note:

Letters are case insensitive. 


-----Input-----

First line contains a integer T denoting the number of test cases. Each test case contains two strings of equal size in two separate lines.

-----Output-----

For each test case,

If s1 < s2, print "first".

If s1 > s2, print "second".

If s1=s2, print "equal".


in separate lines.

-----Constraints-----

- 1 ≤ T ≤ 10^2
- 1 ≤ Length of the string ≤ 500

-----Example-----
Input:
2
abc
acb
AB
ba

Output:
first
first

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer m, we say that a sequence x_1, x_2, ..., x_n of positive integers is m-cute if for every index i such that 2 ≤ i ≤ n it holds that x_i = x_{i - 1} + x_{i - 2} + ... + x_1 + r_i for some positive integer r_i satisfying 1 ≤ r_i ≤ m.

You will be given q queries consisting of three positive integers a, b and m. For each query you must determine whether or not there exists an m-cute sequence whose first term is a and whose last term is b. If such a sequence exists, you must additionally find an example of it.

Input

The first line contains an integer number q (1 ≤ q ≤ 10^3) — the number of queries.

Each of the following q lines contains three integers a, b, and m (1 ≤ a, b, m ≤ 10^{14}, a ≤ b), describing a single query.

Output

For each query, if no m-cute sequence whose first term is a and whose last term is b exists, print -1.

Otherwise print an integer k (1 ≤ k ≤ 50), followed by k integers x_1, x_2, ..., x_k (1 ≤ x_i ≤ 10^{14}). These integers must satisfy x_1 = a, x_k = b, and that the sequence x_1, x_2, ..., x_k is m-cute.

It can be shown that under the problem constraints, for each query either no m-cute sequence exists, or there exists one with at most 50 terms.

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

Example

Input


2
5 26 2
3 9 1


Output


4 5 6 13 26
-1

Note

Consider the sample. In the first query, the sequence 5, 6, 13, 26 is valid since 6 = 5 + \bf{\color{blue} 1}, 13 = 6 + 5 + {\bf\color{blue} 2} and 26 = 13 + 6 + 5 + {\bf\color{blue} 2} have the bold values all between 1 and 2, so the sequence is 2-cute. Other valid sequences, such as 5, 7, 13, 26 are also accepted.

In the second query, the only possible 1-cute sequence starting at 3 is 3, 4, 8, 16, ..., which does not contain 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Mirko spends his free time painting. For this hobby, he likes to use brushes and a palette containing $K$ colors overall. His friend Slavko decided to use Mirko’s talent and gave him his new coloring book for Mirko to color. The coloring book contains $N$ images numbered $1, 2, \ldots , N$.

Mirko has decided to paint each image in exactly one color of the possible $K$ colors from his palette. However, he really likes colorful things. He chose $N$ numbers $f_ i$ and decided to paint the image numbered $i$ differently than the images numbered $f_ i$, except when $f_ i = i$. If $f_ i = i$, that means he can paint the image numbered $f_ i$ whichever color he likes, as long as all other conditions have been met.

Mirko wants to know the number of possible ways to color Slavko’s coloring book and he desperately needs your help! Calculate the number of possible ways to color the book. Given the fact that the output can be very large, print the answer modulo $1000000007$.

-----Input-----
The first line of input contains positive integers $N$, $K$ ($1 \leq N, K \leq 1000000$). The following line contains N numbers $f_ i$ ($1 \leq f_ i \leq N$), as stated in the text.

-----Output-----
The first and only line must contain the number of possible ways to color Slavko’s book.

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

Sample Input 2:
3 4
2 3 1
Sample Output 2:
24

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Caesar cipher is one of the simplest encryption techniques. To transform the original message into encrypted one using key k, one has to replace each letter with a letter which is k positions later in the alphabet (if this takes the position beyond Z, the rest of it is counted from the start of the alphabet). In a more formal way, if letters of the alphabet are enumerated starting with 0, the result of encryption for character x will be <image> (26 is the number of letters in the Latin alphabet).

You are given the original message and the encryption key k. Output the result of encryption.

Input

The first line of input contains an integer k (0 ≤ k ≤ 25) — the encryption key.

The second line contains the original message — a sequence of uppercase Latin letters ('A'-'Z'). The length of the message is from 1 to 10, inclusive.

Output

Output the result of encryption.

Examples

Input

5
CODEFORCES


Output

HTIJKTWHJX


Input

13
FALSERULEZ


Output

SNYFREHYRM

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