Recover the Hidden Password

ygg has discovered that the smart, self‐aware problem bank stores its administrator password in the form of a floating‐point array P of length n. According to the bank, if you take every number in P, round it precisely to 5 decimal places, and join them with a single space, you obtain the password. However, the smart bank refuses to reveal the actual contents of P.

The bank does reveal an interesting property about its secret array. In the bank’s mind, a number X is considered beautiful if and only if \[ \sum_{i=0}^{n-1}P_i\cdot X^i>0. \]

In an attempt to deduce the array P, ygg queries the bank with m real numbers. For each number, the bank replies with either "YES" (meaning the number is beautiful) or "NO" (meaning it is not beautiful). Using these evaluations, ygg hopes to reconstruct P so that the password can be recovered.

Note that the answer is not unique; you just need to output any array P of length n of floating‑point numbers (each printed to five decimal places) such that for every query number X, if the bank answered "YES" then \[ \sum_{i=0}^{n-1}P_i\cdot X^i>0, \] and if the bank answered "NO" then \[ \sum_{i=0}^{n-1}P_i\cdot X^i\le 0. \]

Hint: One possible approach is to construct a polynomial f(x) which changes its sign exactly at the points where the evaluations change, and then pad the polynomial with extra zero coefficients if its degree is less than n-1.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10, m ≥ 3), where n is the length of array P to be recovered and m is the number of queries. Each of the following m lines contains a real number X (with at most 5 digits after the decimal point) and a string which is either YES or NO, separated by space.

You may assume that the queries (when sorted in increasing order of X) are consistent with some polynomial of degree at most n-1 satisfying the corresponding inequalities.

outputFormat

Output n floating‑point numbers separated by a single space — the coefficients of the polynomial f(x) = P₀ + P₁x + P₂x² + … + P_n-1x^n-1. Each coefficient must be printed rounded to five decimal places. The output polynomial must satisfy that for every query X, if the corresponding answer is YES then f(X)>0, and if the answer is NO then f(X)≤0.

sample

1 2
0.50000 YES
2.50000 YES

1.00000