[ACM 題目] 河道分界

contents

1. 1. Problem
2. 2. Input
3. 3. Output
4. 4. Sample Input
5. 5. Sample Output
6. 6. More
7. 7. Solution

Problem

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

Input

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

Output

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

Sample Input

8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

Sample Output

[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

More

Solution