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

Add Tag

Discuss