Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas accidentally found an undiscovered tomb. He successfully sneaked in without triggering any traps. When he finally got into the treasure room, he found a note that warns tomb raiders about the trap in the treasure room. Osas arranged the note and concluded some rules:

 - The treasure room has n treasure crates, each crate has its value. The values are sorted in descending order.

 - There are several intervals [l,r] on the note.

 - Tomb raiders must loot less than or equal to m treasure crates in the correct interval, where m is a number that Osas have to guess.

 - If any tomb raider loot more than m treasure crates or loot any crate that not in the interval, the trap would trigger and kill that tomb raider! Osas doesn't want to die here.

Osas wants these treasures, but he doesn't want to die. Osas wants to know if he pick one interval and guess a number as "m", what is the maximum value he could loot? Osas asks you for help!

Osas will give you the value of every treasure crate and the number he would like to guess, you need to write a program to help him.

Input

The input contains exactly one testcase.

The first line contains two integers n, q. q indicates the amount of queries of (l,r,m).

The next line is the sequence of values of n treasure crates, each seperated by a space. 

The next q lines, each line contains exactly three integers l, r, m.

1<=m<=n<=10⁶, 1<=q<=10⁶, 1<=l<=r<=n, m<=r-l+1, the value of every treasure crate won't larger than 10⁵ or smaller than -10⁵. All of the values are integers. Notice that the value could be negative, and Osas can choose nothing.

Note that the sequence index starts from 1. For example: for a sequence "a": "3 4 5 6 7", a[4]=6, a[1]=3.

Output

For each query, output the maximum value Osas could get. Each query holds exactly one line.

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

We will give you the "inorder" and "postorder" of a tree.

You need to print the "preorder" of this tree we give you.

Notice that the the final testcase has small memory limit. If you don't free your tree you will get memory limit exceeded

 

 

 

 

(The tree for sample input 1)

(The tree for sample input 2)

Input

Output

For each testcase output the "preorder" of the tree.

You have to output in this form:

testcase<id>: <preorder sequence>

Replace <id> and <preorder sequence> into the i-th testcase and the correct preorder sequence.

Each number in preorder sequence should be followed by a single blank(even the last number).

If you have further questions, please refer to sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 

"Go Down Chicken is a vicious monster, it will hit you until you have cerebral concussion(腦震盪)." ~from an anonymous bestiary.

To avoid from being attacked by Go Down Chicken, you need to solve the following problem.

This question has multiple input in each testcase. The input end with EOF.

Each input contain n numbers a_i(1 <= i <= n) and q queries x_j(1 <= j <= q).

Each number a_i represents a game.

The game is that you need to fill a 3 * a_i tiles with the shape(The left one) described in the picture below.

The shape can't overlap and no empty space allow. For each a_i you need to calculate how many ways you can fill the tiles.

The number of ways may be very large, therefore you need to mod the answer with 1000000007.

For example:

The picture above present a 3*6 tiles, you will have 8 ways to fill the tiles with the shape.

 

Once you finish those n games, you need to answer q queries.

Each query will give you one integer x_j means the ways to fill the tiles.

You need to answer x_j is in which round of the games?

If there're multiple answers, answer the earliest round.

If you can't find the answer, print "Go Down Chicken 404"

 

Sample input explain:

You have n = 5, q = 3

Then you have 5 integer: 6, 9, 13, 4, 3

If the tiles is 3*6: you have 8 ways to fill it.

If the tiles is 3*9: you have 0 ways to fill it.

If the tiles is 3*13: you have 0 ways to fill it.

If the tiles is 3*4: you have 4 ways to fill it.

If the tiles is 3*3: you have 0 ways to fill it.

 

Then you have 3 queries: 0, 4, 1024

There are multiple rounds turn out have 0 ways, but you need to answer the earliest round. The earliest round is second round.

Therefore the answer is 2.

The round that turns out have 4 ways is the forth round.

Therefore the answer is 4.

The round that turns out have 1024 ways can't be found.

Therefore the answer is "Go Down Chicken 404".

 

Input

The input is end with EOF

Each input contains several lines.

First line contains two integer n(1 <= n <= 1000000), q( 1 <= q <= 1000000).

Second line contain n integer a_i( 1 <= a_i <= 1000000).

Each a_i is followed by a symbol "(/`A`)/ ~I__I" and separated by a blank from the next integer.

The following q lines each line contains one integer x_j .

Output

For each query print that x_j is the result of which round of the games(start from 1).

If there're multiple answers, answer the earliest round.

If you can't find the answer, print "Go Down Chicken 404"

Sample Input  Download

Sample Output  Download

Tags

Discuss