Xiao Q loves shopping. With the Double 11 festival approaching, an e-commerce platform has introduced a "discount + full reduction" combined promotion scheme.

For each item, the merchant provides a minimum acceptable discount. The buyer can choose a discounted price and then apply one of the platform's "full reduction" schemes for further savings.

Specifically, the platform offers $m$ full reduction schemes. The $i$-th scheme is "for every $a_i$ yuan, reduce $b_i$ yuan." Formally, if the price before applying the scheme is $x$ yuan, the price after applying the scheme is $x - \lfloor \frac{x}{a_i} \rfloor b_i$ yuan.

Xiao Q has $n$ items in her shopping cart. The original price of the $i$-th item is $w_i$ yuan, and the minimum discount provided by the merchant is $\frac{p_i}{q_i}$. In other words, Xiao Q can choose any real number discount $k$ from the range $[\frac{p_i}{q_i}, 1]$ such that the price of the item becomes $x = w_i k$ (where $x$ is a real number). After this, Xiao Q can choose one of the $m$ full reduction schemes to apply to the discounted price.

Xiao Q wants you to help her determine a shopping plan. For each item, choose an optimal combination of discount and full reduction to make the final price of the item as low as possible.

Input

The first line contains two integers $n, m$ ($1 \le n, m \le 5 \times 10^5$), representing the number of items in Xiao Q's shopping cart and the number of full reduction schemes provided by the platform.

The next $m$ lines each contain two integers $a_i, b_i$ ($1 \le b_i < a_i \le 10^6$), representing a full reduction scheme.

The next $n$ lines each contain three integers $w_i, p_i, q_i$ ($1 \le w_i \le 10^6, 1 \le p_i \le q_i \le 10^6$), representing the original price of an item and the minimum discount provided by the merchant.

Output

Output $n$ lines. The $i$-th line should output two coprime positive integers $u_i, v_i$, representing that the minimum price for the $i$-th item under the optimal strategy is $\frac{u_i}{v_i}$ yuan.

Examples

Input 1

3 2
10 5
15 8
9 7 10
26 8 10
35 7 10

Output 1

63 10
54 5
14 1