JU Flash Contest
A. N integers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An integer reserves 4 bytes in the memory.

Your program needs to define $$$n$$$ integers, print how many bytes in the memory in total will be reserved.

Input

The input will contain only one integer $$$n$$$ $$$(1 \leq n \leq 100)$$$, the number of defined integers in your program.

Output

You should print how many bytes will $$$n$$$ integers reserve in memory.

Examples
Input
4
Output
16
Input
2
Output
8

B. Mahmoud the Thief
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As Ayoub was going home from Mahmoud's house, he remembered that he forgot his hard disk, which contains the solutions to $$$n$$$ problems from the JU Flash contest. The $$$i^{th}$$$ problem has size $$$a_i$$$.

While panicking, he remembered that he installed a software that prevented the user from copying any files and only allowed the files to be cut from the hard disk in any order the user wants.

As a security measure, the software will stop the transfer if the number of remaining files is 1, or the absolute difference between the sizes of every pair of problems left on the hard disk is divisible by $$$m$$$.

Ayoub knows the permutation $$$b$$$, which represents the order of the problems Mahmoud will attempt to cut from the hard disk.

Since Ayoub is a bad programmer, he asks for your help to tell him how many problems Mahmoud will steal until the transfer stops.

Input

The first line contains two integer $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^{5})$$$ $$$(1 \leq m \leq 10^{9})$$$

The second line contains integers $$$a_1$$$,$$$a_2$$$,...,$$$a_n$$$ $$$(1 \leq a_i \leq 10^{9})$$$

The third line contains a permutation $$$b$$$ , $$$b_1$$$,$$$b_2$$$,...,$$$b_n$$$ $$$(1 \leq b_i \leq 10^{5})$$$

Output

print exactly one integer $$$-$$$ the number of codes Mahmoud can steal

Examples
Input
3 2
2 1 4
2 1 3
Output
1
Input
3 2
2 1 4
3 2 1
Output
2
Input
5 2
7 9 5 33 77
5 3 4 2 1
Output
0
Note

In The first sample :

At first Mahmoud will try to cut the file with index $$$2$$$, and he can do it since there exists two files, the absolute difference between their sizes is not divisible by $$$m$$$(for example file $$$2$$$ and file $$$1$$$ ($$$a_1 - a_2 = 1$$$) and $$$1$$$ is not divisible by $$$2$$$).

After cutting The first file, the remaining files will be the files with indices $$$1$$$ and $$$3$$$, Mahmoud can't cut The next file, because the absolute difference between any pair is divisible by $$$m$$$.

So Mahmoud will steal only one file.

C. Apple Shops
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ayoub wants to buy k boxes of apples, and there are n shops where he can buy apples from. The price of one box of apples in the ith shop equals to pi.

It is obvious that Ayoub should go to the shop with the minimal price per box. When the government saw everyone buying from the same shop, they made a special rule so that people will buy from different shops.

The cost of buying the jth apple box from the ith shop is equal to pi + (j - 1)  ×  x

For example, if the price of one box from a specific shop is 5 and x = 3. If you want to buy 3 boxes, you will pay 5 money on the first box and 5 + x on the second box, and 5 + 2 × x on the third box, in total paying 5 + 8 + 11 = 24.

Now you should tell Ayoub how many boxes he should buy from every shop so that the total money he will pay is minimized.

Input

First line contains 3 integers n k x (1 ≤ n ≤ 105) (1 ≤ k, x ≤ 109) which are the number of shops and the number of box Ayoub wants to buy and the amount of money you should pay more after buying a box from a specific shop.

Second line contains n integers, the ith one is pi (1 ≤ pi ≤ 109) which is the price of a box of apples from the ith shop.

Output

You should print n integers, the ith one should be the number of box Ayoub should buy from the ith shop.

Make sure that the amount of money will be payed will be minimized as possible.

If there are more than one answer you can print any of them.

Examples
Input
3 2 5
2 2 2
Output
1 1 0
Input
4 4 3
1 5 2 3
Output
2 0 1 1
Note

In the second sample Ayoub will pay 1 and 4 to the first shop and will pay 2 to the third shop and will pay 3 to the fourth shop, in total he will buy 10 money.

D. Coach Ayoub
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ayoub is a basketball coach where he has $$$n$$$ students, he told Kilani that the minimum height between his students is equal to $$$a$$$, and the maximum height between his students is equal to $$$b$$$, and the sum of heights of his students is equal to $$$s$$$.

Kilani thinks that the description that Ayoub gave him is wrong, and it is impossible to have such students with that description.

Kilani is not sure about that, so he asked you for help.

Given 4 integer numbers $$$n,a,b,s$$$, you should tell him if Ayoub's description is wrong for sure, or if it is possible to have $$$n$$$ students with that description.

Input

The input will contain 4 integers $$$n,a,b,s$$$ $$$(1 \leq n \leq 100)$$$ $$$(1 \leq a \leq b \leq 250)$$$ , $$$(1 \leq s \leq 25000)$$$.

Output

If it is possible to have $$$n$$$ students with that description print "YES" .

Otherwise print "NO".

Examples
Input
5 2 4 13
Output
YES
Input
5 2 3 30
Output
NO

E. New Max
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kamal 'D has an array of size $$$N$$$.

He can do at most $$$K$$$ operations on it, in each operation he can choose any element in the array and change its value to any other value $$$X$$$, $$$(1\leq x \leq 400)$$$.

Kamal 'D wants to know if he can make the maximum element in the new array equal to $$$M$$$.

Input

The first line of input will contain 3 integers $$$N$$$, $$$M$$$ and $$$K$$$ $$$(1 \leq N \leq 400)$$$ $$$(0 \leq K \leq 400)$$$ $$$(1 \leq M \leq 400)$$$ which are the size of the array, the new maximum value and the number of operations.

The second line will contain $$$n$$$ integers, the $$$i_{th}$$$ one is $$$a_i$$$ which is the $$$i_th$$$ element in array $$$a$$$, $$$(1\leq a_i \leq 400)$$$

Output

For each test case, print "YES" if Kamal 'D can make the maximum element equals to M, print "NO" otherwise .

Examples
Input
6 4 3
1 5 3 4 2 6
Output
YES
Input
6 4 2
5 5 5 5 1 2
Output
NO

F. Who has a better strategy ?
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Da'san and Abu Tahun are playing a video game, in that video game there are n monsters, the strength of the ith monster is si, (1 ≤ si ≤ n), where each monster has a unique strength.

They both can defeat all monsters, Da'san needs ai seconds to defeat the ith monster and Abu Tahun needs bi seconds to defeat the ith monster.

Now they will play together at the same time, Abu Tahun will start killing monsters from the strongest one and Da'san will start killing monsters from the weakest one. The one who reaches a specific monster first will be the one to kill that monster. But if they came to kill the same monster at the same time, Abu Tahun will leave that monster to Da'san.

Now you are given q queries, for each query you are given a subarray from l to r, you should print the number of monsters each one of them will kill, if they both started playing the game with the monsters in the subarray from l to r.

Input

The first line contains 2 integers n and q (1 ≤ n, q ≤ 2 × 105) which are the number of monsters and the number of queries.

The second line will contain n distinct integers, the ith one is si (1 ≤ si ≤ n) which is the strength of the ith monster.

The Third line will contain n integers, the ith one is ai (1 ≤ ai ≤ 109), which is the time needed to kill the ith monster by Da'san.

The Fourth line will contain n integers, the ith one is bi (1 ≤ bi ≤ 109), which is the time needed to kill the ith monster by Abu Tahun.

The next q lines will contain 2 integers for each line, l and r (1 ≤ l ≤ r ≤ n), which is the sub-array that was given for the current query.

Output

For each query print 2 integers, the number of monsters killed by Da'san and the number of monsters killed by Abu Tahun.

Example
Input
3 3
1 3 2
1 1 2
1 1 1
1 3
2 3
1 2
Output
2 1
1 1
1 1
Note

In the sample, for the first query at minute 0, Da'san will start with monster at index 1, and Abu Tahun will start with monster at index 2,

at minute 1 they will both go to kill the monster at index 3, and since they both came to kill the same monster at the same time Abu Tahun will leave that monster to Da'san.

So Da'san will kill 2 monsters and Abu Tahun will kill 1 monster.

G. ABC
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bashar was learning the alphabets, in the last class he learned letters A,B,C. After that he decided to go home. On his way home, he was thinking of how many strings of length $$$n$$$ that are made up of letters A,B,C are beautiful. Beautiful strings are strings such that for all substrings of length $$$k$$$, the number of A's + number of B's is equal to the number of C's.

Bashar couldn't solve the problem and fell asleep, can you solve them for him before he wakes up!!

Input

First line contains one integer $$$t$$$ $$$(1 \leq t \leq 10 ^ {5})$$$ which is the number of test cases.

For every test case you are given two integers $$$n$$$ and $$$k$$$ on a line $$$(1 \leq n \leq 10^{9})$$$ $$$(1 \leq k \leq min(n,10^{5}))$$$.

Sum of $$$k$$$ between all test cases will not exceed $$$10^{6}$$$

Output

For every test case print the answer on a line, since the answer can be very large print it modulo $$$1000000007$$$.

Example
Input
3
2 1
2 2
3 2
Output
0
4
6

H. Zuhair and the Dag
time limit per test
1 second
memory limit per test
4 megabytes
input
standard input
output
standard output
it's easy to be Expert
Mohammad Zuhair

Memory limit is set to 4 mb.

Kilani has a directed graph with $$$n$$$ nodes and $$$m$$$ edges, where there could be at most one edge between any pair of nodes, and it contains no self loops. It doesn't have to be a connected graph.

Kilani thinks that Zuhair is a very smart person so he decided to give him a problem on that graph.

Zuhair should choose a sub-set of edges and flip them, so if the edges were going from node $$$u$$$ to node $$$v$$$, it becomes from node $$$v$$$ to $$$u$$$.

He should choose a sub-set of edges in order to make the graph a DAG.

D$$$_{iricted}$$$A$$$_{cyclic}$$$G$$$_{raph}$$$ is a directed graph without any cycles.

Input

First line contains 2 integers $$$n$$$ and $$$m$$$, which are the number of nodes and the number of edges $$$(2 \leq n \leq 10 ^{6})$$$ $$$(1 \leq m \leq 10 ^{6})$$$. The next $$$m$$$ lines , will contains 2 integers for each, $$$u$$$ and $$$v$$$ $$$(1 \leq u , v \leq n)$$$ $$$(u \neq v)$$$, which means that there is a one way edge goes from node $$$u$$$ to node $$$v$$$.

Output

you should print a string with length $$$m$$$, the $$$i_{th}$$$ character should be '0' if you want the $$$i_{th}$$$ edge to go from node $$$u$$$ to $$$v$$$, and '1' to go from $$$v$$$ to $$$u$$$.

Example
Input
4 4
1 2
2 3
3 4
4 1
Output
0100
Note

First Sample :

Before flipping

After flipping

I. Abu Tahun Mod problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abu Tahun loves palindromes.

An array is palindrome if it reads the same backwards and forwards, for example arrays $$$\{1\}$$$, $$$\{1,1,1\}$$$, $$$\{1,2,1\}$$$ , $$$\{1,3,2,3,1\}$$$ are palindrome, but arrays $$$\{11,3,5,11\}$$$, $$$\{1,12\}$$$ are not.

Abu Tahun has an array of $$$n$$$ integers $$$A$$$. He wants his array to be palindrome. He can choose an integer $$$m$$$, then change the value of all $$$A_i$$$ $$$(1 \leq i \leq n)$$$ to ($$$A_i\mod m$$$).

what is the maximum value of $$$m$$$ he can choose, such that the array becomes palindrome?

Input

The first line of input contains a single integer $$$n$$$ $$$( 1 \leq n \leq 10^{5})$$$

The second line contains integers $$$A_1$$$,$$$A_2$$$,...,$$$A_n$$$ $$$(1 \leq A_i \leq 10^{9})$$$

Output

Print the maximum value of $$$m$$$ Abu Tahun can choose, if $$$m$$$ is arbitrarily large print -1.

Examples
Input
4
1 1 1 1
Output
-1
Input
4
1 2 3 4
Output
1
Input
3
8 12 16
Output
8

J. Negative effect
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abu tahun has an array $$$a$$$ of $$$n$$$ positive integers, and a negative integer $$$m$$$.

Abu Tahun defines the beauty of the array as the maximum summation of a sub-array in that array.

A sub-array of an array is a sequence of consecutive integers in the array.

For example :

The beauty of array $$$\{1 , -5 , 7\}$$$ equals to $$$7$$$.

And the beauty of array $$$\{6 , -5 , 7\}$$$ equals to $$$8$$$.

in the second example we have the sub-arrays :

$$$\{6\}$$$ sum = 6, $$$\{-5\}$$$ sum = -5, $$$\{7\}$$$ sum = 7, $$$\{6,-5\}$$$ sum = 1, $$$\{-5,7\}$$$ sum = 2, $$$\{6,-5,7\}$$$ sum = 8.

You should tell Abu Tahun, for every index if he replaced the number in that index with $$$m$$$, what is the beauty of the resulting array.

Input

First line of input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^{5})$$$ $$$(-10^{9} \leq m \lt 0)$$$

The second line will contain $$$n$$$ integers, the $$$i_{th}$$$ one is $$$a_i$$$, which is the $$$i_{th}$$$ element in the array, $$$(1 \leq a_i \leq 10^{9})$$$.

Output

You should print $$$n$$$ integers, the $$$i_{th}$$$ one should be the beauty of the given array after replacing the $$$i_{th}$$$ integer with $$$m$$$.

Example
Input
4 -3
1 2 3 4
Output
9 7 4 6
Note

In the first sample

after replacing the first index the array will become :

$$$\{-3,2,3,4\}$$$

the beauty equals to 9.

after replacing the second index the array will become :

$$$\{1,-3,3,4\}$$$

the beauty equals to 7.

after replacing the third index the array will become :

$$$\{1,2,-3,4\}$$$

the beauty equals to 4.

after replacing the fourth index the array will become :

$$$\{1,2,3,-3\}$$$

the beauty equals to 6.

K. Scientest Ayoub (A)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ayoub is a very famous scientist, he spends all his time and money doing research, today he is working on some new research with his assistant Kilani.

In this research Ayoub has $$$n$$$ rabbits. In order to test these rabbits, he has to take every subset of rabbits and test them alone. After that, he will write down the result for each test, Ayoub wants to give every subset a unique number so he can know for each result is for which subset.

Kilani told Ayoub that he can give every rabbit a value, and the number of every subset will be the sum of the values of the rabbits in that subset.

Ayoub liked this idea very much and asked Kilani to do it. Unfortunately Kilani couldn't do it and he asked you for help.

Given the number of rabbits $$$n$$$, you should give every rabbit a number, so that every subset has a unique sum, and the numbers are between $$$1$$$ and $$$10^{7}$$$

Input

The input will contain one integer $$$n$$$ $$$(1 \leq n \leq 22)$$$ which is the number of rabbits.

Output

You should print $$$n$$$ integers, the $$$i_{th}$$$ one should be the number given to the $$$i_{th}$$$ rabbit.

The numbers should be between $$$1$$$ and $$$10^{7}$$$, and every subset should have a unique sum.

Examples
Input
4
Output
2 90 21 3
Input
2
Output
1 2
Note

A subset of rabbits is a set that can be obtained by removing zero or more rabbits from the set of rabbits.

L. Scientist Ayoub (B)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After long researches on rabbits Ayoub got very tired, dealing with rabbits is really hard, also testing every subset of rabbits takes lots of time.

After some tests Ayoub saw that he doesn't need to test every subset of rabbits, but he need only to test every subarray of rabbits, this way he can test even more rabbits right?

Anyway, Ayoub needs also to give every subarray of rabbits a unique number. He will do the same thing, which is giving every rabbit a value and the number of the subarray will be the sum of values of rabbits in the subarray.

Once again, Ayoub asked Kilani to do it and he couldn't, so he gave the problem to you.

Given the number of rabbits $$$n$$$, you should give every rabbit a number so that every sub-array has a unique sum, and the numbers are between $$$1$$$ and $$$10^{9}$$$.

Input

the input will contain only one integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$ which is the number of rabbits.

Output

You should print $$$n$$$ separated integers, the $$$i_{th}$$$ one should be the number given to the $$$i_{th}$$$ rabbit.

Every number should be between $$$1$$$ and $$$10^{9}$$$, and every subarray should have a unique sum.

Examples
Input
4
Output
10 15 50 345
Input
2
Output
1000 3000
Note

Alert!!! This problem is related to the previous problem.

M. Ahmad Jaber Rectangles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad has two rectangles, both of them are above $$$x-axis$$$ and the height of each one is $$$h$$$ $$$(1 \leq h \leq 10^{9})$$$.

The first rectangle's sides are $$$(x_1,0)$$$ $$$(x_2,0)$$$ $$$(x_1,h)$$$ $$$(x_2,h)$$$

The second rectangle's sides are $$$(x_3,0)$$$ $$$(x_4,0)$$$ $$$(x_3,h)$$$ $$$(x_4,h)$$$

Ahmad wants to know what is the area of the intersection between these two rectangles.

Input

The first and the only line of input contains 5 integers $$$x_1$$$,$$$x_2$$$,$$$x_3$$$,$$$x_4$$$ and $$$h$$$

$$$(1 \leq x_1 \lt x_2 \leq 10^{9})$$$ $$$(1 \leq x_3 \lt x_4 \leq 10^{9})$$$ $$$(1 \leq h \leq 10^{9})$$$.

Output

Print the area of intersection.

Example
Input
1 4 2 3 5
Output
5