Description

In "Avengers 3", we know that Thanos wants to eliminate half of the world to keep the world in a good balance. But, have you ever wondered about how he choose "1/2" ? Why don't he choose "1/3", "1/4", or "253/502" ? 

He knows that the population of this world would just keep growing, so he calculated the formula of population of this world:

On the i-th year from the start of the world, the population of this world P(i) would be: P(i-1) + 2 * P(i-2) + P(i-3).

From this formula, he concluded that P(1)=1, P(2)=12, P(3)=13.

According to this formula, he could estimate the populations of the world on every year, so that he could choose the percentage of the population he would like to eliminate. (We don't know how he choose)

Because Thanos has a lot of planets to conquer, he asks you to calculate P(x), while x is given by him.

The world has lived for so many years, so he might ask you P(x) where x would be very large. And in case of P(x) is super large, the number should mod 10⁹+7.

"Thanos Thinking About This Problem"

If you click on this picture, something might happen...

• Given t, indicates the number of testcases.
• P(i) = P(i-1) + 2*P(i-2) + P(i-3)
• P(1)=1, P(2)=12, P(3)=13
• Given x, you are going to calculate P(x)%(10⁹+7) of every testcase.

Hint: use fpw(快速冪) to solve this problem!

If we rewrite the equation into matrix form, we could get the following formula:

With this formula, we can do something more:

Now, we can implement fpw(快速冪) method on the matrix power part. For those n<=3, just output the answer.
Note that you are encouraged to implement a "matrix" struct to solve this easier.

Input

The first line contains one integer t, indicates the number of testcases.

There are t lines below, each line contains one integer x.

1 <= t <= 20, 1 <= x <= 10¹⁸.

Output

For each testcase, output exactly one integer P(x)%(10⁹+7).

Remember to output a '\n' at the end of every testcase.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I got a young body.

~by anonymous coroner

You are a coroner, and you need to buy some Formalin to keep your body in good condition. There're n kinds of Formalin, and you have p dollars. Luckily the Formalin is on sale. If you buy exactly k kinds of Formalin, you only need to pay the most expensive one of them.

You got n products and p dollars.

Everytime you buy exactly k products at once, you only need to pay the most expensive product among the k products.

For the i-th product, the price equals to ai.

Find the maximum number of products you can buy with p dollars.

Example:

If n=5 and you got p=6 dollars.

If you buy exactly k=2 products, you only need to pay the most expensive one of them.

Products' price: 2, 4, 3, 5, 7.

In this case, you can buy products of price 4, 3 then you only need to pay 4 dollars.

You left with 2 dollars, then you can buy products of price 2.

The maximum number of products you can buy in this case is 3.

Input

The input start with t(1<= t <=10) means number of testcases.

Each testcase contains two lines.

First line contains three numbers n(2<=n<=3*10^5), p(1<= p <= 10^9), k(2 <= k <= n).

Second line contains n integer ai(1 <= ai <= 10000).

Output

For each testcase print the maximum number of products you can buy with p dollars.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Recently, Gilgamesh found that he's almost lack of swords in his vault, so he wants to forge a lot of swords with different shapes. He command you to forge for him!

Gilgamesh's sword can only be forged by triangle. Different triangle can be forged into a unique sword. He will give you the intervals of the edges of triangles, you have to calculate how many swords with different shape can he get?

Gilgamesh threats you with his "Gate of Babylon".

You are given four positive integer $A\le B\le C\le D$, you're going to count how many triangle that can be build by edges with length $x,\ y,\ z$, where $A\le x\le B,\ B\le y\le C,\ C\le z\le D$.

For example: $A=1,\ B=2,\ C=3,\ D=4$

You can build triangles with edges : $(x,y,z)\in \{(1,3,3),\ (2,2,3),\ (2,3,3),\ (2,3,4)\}$.

So the answer is 4.

Input

The first line contains one integer $T$, there are $T$ testcases below.

For each testcase, the four integer $A,\ B,\ C,\ D$ is given respectively.

$1\le T\le 100$.

$1\le A\le B\le C\le D\le 5\times 10^4$.

Output

For each testcase, output its answer, followed by a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A program a day keep girls away.

~by anonymous programmer

You are a programmer, you need to write code day and night.

In order to keep you in a sharp mind, you drink a lot of coffee.

Given n cups of coffee, the ith cup of coffee has the effect that make

you write ai lines of code and ai will be decreasing order.

Each cup of coffee can only be drunk for once.

You can drink coffee in arbitary order!!!!

You need to write m lines of code.

In a day when you drink a cup of coffee,

the second cup of coffee will loss it's effect by 1

and the third cup of coffee will loss it's effect by 2

..... and so on

You need to find out what's the minimum number of days

that you can finish m lines of code.

Example:

Given n = 5 cups of coffee, you need to finish m=16 lines of code.

The effect of coffee = a1 = 5, a2 = 5, a3 = 5, a4 = 5, a5 = 5

If you drink a1~a4 at the first day, you finish 5 + (5-1) + (5-2) + (5-3) = 14 lines of code.

If you drink a5 at the second day, you finish 5 lines of code.

14+5 >= 16 therefore you can finish your code by 2 days,

and it's the minimum number of days that you can achieve.

Input

First line contains one integer t(1 <= t <= 10) which means the number of testcases.

Each testcases contains two lines.

First line contains two integer n(1 <= n <= 2*10^5), m(1 <= m <= 10^9)

Second line contains n numbers ai(1 <= ai <= 10^9)

Output

For each testcase print only one number which means the minimum number of days

that you can finish m lines of code.

If you can't finish your code in any way, print -1.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Previous episode: 12155

After the "blackhole" incident, scientists accidentally found the potential energy of blackholes that created by the collision of multiple cat-toasts: the energy productivity of cat-toast blackhole is far more larger than cat-toasts.

By observing the cat-toast blackhole near the event horizon, they found that the collided cat-toasts weren't teared into slices but spinning around the blackhole. The scientists decided to call it "Nyan Cat". The Nyan Cat blackhole soon be wildly spread to the whole world.

Nyan Cat spinning around the blackhole

Recently, the scientists found that if there are too many Nyan Cat spinning around one blackhole, the huge angular momentum will form an unstable energy field, which would cause the Nyan Cat blackhole system crash, then all the nearby substance will be inhaled.

They soon set up a team to deal with the potential threat. If a cat-toast blackhole contains too many Nyan Cat spinning around it, they'll use catnip(貓薄荷) to lure it out.

You are in a power plant, whose energy source is the cat-toast blackhole. The power plant engineer gives you the original cat-toast location before they collide into a blackhole. You need to figure out the number of blackholes that is safety, and the number of blackholes that contains too many Nyan Cat.

There are $n$ nodes on an 2D-plane. If the distance of two nodes are equal to or closer than $r$, they are in the same group.

You are given a number $k$. You have to find out:

1. The number of groups with size less than $k$.
2. The number of groups with size equal to or greater than $k$.

• Note that the distance between two nodes $i$ and $j$ is:

  $$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$

  where $(x_i,y_i)$ and $(x_j,y_j)$ are the coordinate of the two nodes, respectively.

Input

The first line contains an integer $t$, indicates the number of testcases.

In each testcase:

• The first line contains $n$, $r$, and $k$.
• There are $n$ lines below. The $i$-th line of the $n$ lines contains the coordinate of $i$-th node: $(x_i,y_i)$.

$1\le t\le 100, 1\le k\le n\le 500, 1\le r\le 10^4$.

$-10^4\le x_i,y_i\le 10^4\ \forall\ i$.

Output

Output two numbers:

The number of groups with size less than $k$ ,and the number of groups with size equal to or greater than $k$, seperate with a space.

Remember to print a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss