Description

Uncle Huang wants to find a tutor. He has n students to choose from. 

Students are indexed 1, 2, . . . , n and standing in a circle. 

Uncle Huang will count every k-th students in clock-wise.  

The k-th student is going to be chosen but the student will disappear(Nobody knows why!) therefore Uncle Huang will continue his counting and start from the next student.

The last remaining student will be his tutor.

Tell Uncle Huang the index of the student who will be his tutor.

example: If n = 5, k = 7

Hint: 約瑟夫斯問題(https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)

This problem is partial judge.

Note: k might be very large, if you just count k students you will get TLE. Try to count less by using mod.

 

Input

The input will end by EOF

Every testcase only contains two integer n(1<= n <= 1000) and k(1 <= k <= 10⁹)

Output

For each testcase print the index of the student who last remaining.

remember to print \n at the end of every output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12301.c

Partial Judge Header

12301.h

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

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