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

There're different kinds of Knuckles in this world. According to the research, there're 26 different kinds of Knuckles.

---

Let's denote different kind of Knuckles as 'a' ~ 'z'.

Knuckles is a magic creature.

If you have at least 2 same kind of Knuckles, you can transform these Knuckles into any kind of Knuckles with same number of them.

For example：

if you have n=3 Knuckles representing as "aab" you can transform 'a' Knuckles into 'b' Knuckles. In the end you will get "bbb" Knuckles.

Because you're a deadly Ethnic nationalism, you want all Knuckles to be the same.

You can do the transformation many times.

Find out whether you can do that.

NOTE: Case 6 limits the memory to 1 MB, so try not to declare a large array.

Input

Input contains two lines.

First line contains only one integer n( 1 <= n <= 10⁷ ), representing the number of Knuckles.

Second line contains one string, the length of n.

 

Output

If you can make all Knuckles the same, output "I'm the god of Knuckles!"

Otherwise,  output "Different makes perfect"

Remember to print \n at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This bamboo rat seems to have heatstroke, we might as well ......

── Brothers HuaNong

Brothers HuaNong feed a lot of bamboo rats. They do love to eat bamboo rats! However, some of the rats seems to have heatstroke. Brothers HuaNong couldn't bear to watch them suffer, and we all know how Brothers HuaNong treat those heatstroke rats...

---

Every bamboo rat has its level of heatstroke(中暑程度), Brother HuaNong would randomly choose a number $x$. If there's a rat with level of heatstroke equals to $x$, Brother HuaNong would think that the rat has heatstroke and eat it.

You are hired by Brothers HuaNong. Brothers HuaNong will give you the level of heatstroke of every bamboo rats and several numbers $x$. Your task is to help them find out if there's rats that have heatstroke.

Hint: construct a binary search tree.

---

This problem is partial judge. You are going to implement the following functions:

1. void build_tree(Node **now, int *arr, int l, int r)

   When this function is called, you should build a binary search tree by the array arr.

2. int query_heatstroke(Node *now, int x)

   This function is used to ask if there exists a node with level equals to $x$.

3. void eat_rat(Node **root, int x)

   This function will delete one node with level equals to $x$.

---

Take sample as an example, initially, the level of heatstroke of the rats would be $(1,2,3,6,8,10,10,309)$.

Firstly, $x=8$, they will eat a rat with level equals 8. The sequence becomes $(1,2,3,6,10,10,309)$.

$x=10$: eat a rat with level equals to 10. The sequence becomes $(1,2,3,6,10,309)$.

$x=10$: eat a rat with level equals to 10. The sequence becomes $(1,2,3,6,309)$.

$x=200$: no rat with level equals to 200.

$x=10$: no rat with level equals to 10(since all rats with level 10 are eaten).

Input

The first line is an integer $n$, which indicates the number of bamboo rats.

The next line contains $n$ integers, indicate the level of heatstroke of every bamboo rat sorted in ascending order.

The third line is an integer $q$, which means there are $q$ queries below.

There are $q$ lines below. Each line contains exactly one integer $x$.

$1\le n\le 10^6$, $1\le q\le 10^6$, $1\le x\le 10^9$, the level of bamboo rats have the same range as $x$.

Output

For each query $x$, output "We might as well eat it." if there's a rat with level of heatstroke $x$, otherwise output "No dinner tonight."

Sample Input  Download

Sample Output  Download

Partial Judge Code

12388.c

Partial Judge Header

12388.h

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

Description

1. C language is the only allowed programming language. Solving problems with other languages (e.g. C++) are forbidden, otherwise you'll get zero point.

2. Paper references, electronic devices, or other items that may contain any information relative to this exam are not allowed.

3. Before leaving, please tell TAs, we'll check if your accepted / partially accepted submissions are all written in C. After you pass the check, you may sign your name as a record and leave.

4. The score of each problem is shown below:

   • 12145: 6 points

   • 12138: 4 points

   • 12388: 6 points

   • 12435: 4 points

If you get partially correct in a problem, your score of the problem will be

• score of the problem * number of testcases you passed / number of testcases

For example, if score of a problem is 10, which contains 6 testcases, and you pass the 3 testcases, you'll get 10*3/6=5 points on this problem.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss