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

 

A famous streamer once said: "I will definitely hit you! I will definitely break your bridge!". The streamer asked you to remember those who annoyed him. They are represented as numbers. When the streamer ask you, you should answer the position of the one the streamer wants to hit.

---

You will got n distinct numbers in increasing order and q for the number of queries.

Suppose the n numbers are stored in an array whose index start from 1.

Each query will give you an integer a_i , then you need to answer the position of a_i in the array.

If you can't find the number in the array, you need to output "Break your bridge!".

example:

6 3 // n = 6, q = 3
4 7 9 20 31 34 // n numbers
4 // answer the position of 4
1 // answer the position of 1
20 // answer the position of 20

In this example you can find "4" in the first place, therefore you should answer "1".

You can't find "1" in the array, therefore you should answer "Break your bridge!".

You can find "20" in the forth place, therefore you should answer "4".

 

You can use the following sample code to solve the problem. It's better you write your own code:

typedef struct _NODE {
	int num, id;
	struct _NODE *left, *right;
} Node;
void build_tree(Node **now, Num *arr, int l, int r) {
	if(l>r) return;
	(*now) = (Node*)malloc(sizeof(Node));
	if(l==r) {
		/*do it your self*/
	}
	else {
		/*do it your self*/
	}
}
int search(Node *now, int x) {
    if(now==NULL) return 0;
	/*do it your self*/
}
void insert(Node **root, int x) {
	/*do it your self*/
}
void freeBST(Node *root){
    if(root == NULL) return;
	/*do it your self*/
}

 

 

Input

Input end with EOF.

Each testcase contains several lines.

First line contains two integer n(1<= n <= 2*10⁶) and q(1<= q<= 2*10⁶)

Second line contains n integer. Each integer range in 1~1000000000

The following are q lines. Each line contains one integer a_i(1<= a_i <= 10⁹)

 

Output

For each query print the position of a_i.

If you can't find a_i in the array, print "Break your bridge!"

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

An fandom anime opening of Area51 Raid event.

If we naruto run, we can move faster than their bullets.

── Unknown naruto runner

"Storm Area 51, They Can't Stop All of Us" is an event that invites everyone to intrude into the famous America military base "Area 51" on Sep. 20, 2019. In this event, participants are asked to use naruto run to intrude Area 51 so that they can move faster than their bullets.

However, performing naruto run challenges the control of Chakra(查克拉) of the runner. They have to control the flow of Chakra and distribute it appropriately so that they could be able to run steadily.

A runner run over the camera. Shot in 1/1000 sec. The original report is here.

---

On every step, a pre-order binary expression and some values would cross runners' mind. Runners needs to rearrange the binary expression into in-order and calculate the answer of this expression, so that they can naruto run steadily and dodge those bullets.

You are an adviser of this event. Somehow you can read the runners' mind and tell them the answers of these expressions. You're going to write a program to help them, otherwise they will be hit by bullets.

Because naruto run is a simple ninjutsu(忍術), the expression won't be too complicated, so the variables in an expression won't exceed 3($x,y,z$). And we don't care about the parentheses.

---

Take the sample as example:

We use the pre-order binary expression the build a syntax tree, the tree should look like the following graph:

Now, we can write down the in-order: x+3*y/4. Note that we don't add spaces or parentheses.

And we know that $x=3, y=1, z=9$, then calculate the answer: $(3+3*1)/4=6/4=1$.

Note that we only pick the integer part to calculate.

Input

The first line contains the whole expression in pre-order. The length of the input string wouldn't exceed 100.

The input expression would contain:

• variable $(x,y,z)$
• operator $(+,-,*,/)$
• integers in range $[1,100]$

The second line contains three integers represent $x$, $y$, $z$, respectively.

$1 \le x,y,z \le 100$. You don't have to worry about overflow or underflow.

Note that there will be a space after every operator, number, and variable. Please refer to the sample.

Output

On the first line, output the expression in in-order. There should be no space between every operator, number, and variable.

On the second line, output the result of this expression.

Sample Input  Download

Sample Output  Download

Tags

Discuss