Learning Klingon P99729

From now on it will be mandatory to study Klingon at the University, as it is the language of the future. Klingon’s grammar is easy to learn, but the real challenge comes when dealing with the vocabulary. Therefore, you have decided to write a simple program to help you, which has a list of pairs of English/Klingon words. The program keeps a weight (a positive number, initially equal to one) associated to each English word. Let s be the current sum of weights. Repeatedly, the program arbitrarily chooses an integer x in the range [0, s), and shows you the first English word w such that the sum of all the weights from the first word to w is bigger than x. After you write your Klingon translation of w, if your answer is correct the weight of w is decreased by one; otherwise it is increased by one. As you want to avoid weights equal to zero, when this happens the program adds one to the weight of every word. Similarly, when the smallest weight becomes two, the program substracts one from every weight.

For example, let us consider the words “yes”, “no”, “thanks” and “sir” in this order. Let us imagine that the first x is 1, so the first w is “no”. If you correctly answer “qhobe”, then the weights are changed to 1 0 1 1 and, after normalizing, to 2 1 2 2. Otherwise, the weights are updated to 1 2 1 1.

Input

Input consists of several cases. Every case begins with the number of words n, followed by the number of queries q, followed by q queries, each one with x and a 1 or a 0 depending on if your answer is right or wrong. Assume 1 ≤ n ≤ 3 · 10⁴ and 1 ≤ q ≤ 3 · 10⁴.

Output

For every case, print the final weight of every word divided by the final sum of weights, with no common factors. Print an empty line after every case.