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

Add Tag

Discuss