TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

50.0% (1/2)

Tags

Description

在一個座標平面上,原點有一座敵人的城堡,而我軍要在其他座標上部屬許多部隊。
精確來說,每個部隊是由一排排好的士兵組成,且我們稱一個部隊內排最前面的為前排士兵,排最後面的為後排士兵。
由於最近這個地區動盪不安,敵軍城堡頻有動作,因此需要不斷調度兵力以抵禦敵人。

總結來說依序共有 $N$ 個兵力調度事件,分成四類:

  1. 座標 $(x, y)$ 的部隊空降一名編號為 $i$ 的士兵成為前排士兵。
  2. 座標 $(x, y)$ 的部隊空降一名編號為 $i$ 的士兵成為後排士兵。
  3. 座標 $(x, y)$ 的部隊請求一名前排士兵,到該部隊前排支援。
  4. 座標 $(x, y)$ 的部隊請求一名後排士兵,到該部隊後排支援。

事件3、4中,前排士兵要由其他部隊的前排士兵來支援,後排士兵要由其他部隊的後排士兵來支援。且支援會由安全度最接近的部隊來派兵(安全度定義為與敵人城堡距離的平方。若安全度之差相同,則選擇 x 較小的部隊。若 x 仍相同,則選擇 y 較小的部隊。)。

最初,我軍在地圖上沒有任何士兵。求 $N$ 個事件後,每個編號的士兵待在哪個座標。

Input Format

輸入第一行有一個正整數 $N$,代表有多少事件。
接下來 $N$ 行每行都會是下列其中一種

  1. 1 x y i 座標 $(x, y)$ 的部隊空降一名編號為 $i$ 的士兵成為前排士兵
  2. 2 x y i 座標 $(x, y)$ 的部隊空降一名編號為 $i$ 的士兵成為後排士兵
  3. 3 x y 座標 $(x, y)$ 的部隊請求一名前排士兵
  4. 4 x y 座標 $(x, y)$ 的部隊請求一名後排士兵
  • $1 \leq N \leq 3 \cdot 10^ 5$
  • $-10^ 9 \leq x, y \leq 10^ 9$
  • 若 $x_a^ 2 + y_a^ 2 = x_b^ 2 + y_b^ 2$ 則 $(x_a, y_a) = (x_b, y_b)$
  • $i$ 兩兩不重複
  • $1 \le i \le N$
  • 在事件 3, 4中,保證請求得到支援。

Output Format

令 $M$ 為士兵的數量。
請輸出 $M$ 行,第 $j$ 行請輸出編號第 $j$ 小的士兵所在的座標,以一個空白隔開。

Sample Input 1

3
1 125083899 290965564 3
1 125083899 290965564 2
1 125083899 290965564 1

Sample Output 1

125083899 290965564
125083899 290965564
125083899 290965564

Sample Input 2

12
2 873458049 428337058 9
2 873458049 428337058 11
4 -481510690 29429158
2 -481510690 29429158 12
3 -861066800 -998324814
2 873458049 428337058 2
2 873458049 428337058 7
4 -861066800 -998324814
1 873458049 428337058 10
1 873458049 428337058 3
4 -861066800 -998324814
1 -861066800 -998324814 1

Sample Output 2

-861066800 -998324814
-861066800 -998324814
873458049 428337058
-861066800 -998324814
-861066800 -998324814
873458049 428337058
-481510690 29429158
-481510690 29429158

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~54 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
32 1000 524288 65536 2
33 1000 524288 65536 2
34 1000 524288 65536 2
35 1000 524288 65536 2
36 1000 524288 65536 2
37 1000 524288 65536 2
38 1000 524288 65536 2
39 1000 524288 65536 2
40 1000 524288 65536 2
41 1000 524288 65536 2
42 1000 524288 65536 2
43 1000 524288 65536 2
44 1000 524288 65536 2
45 1000 524288 65536 2
46 1000 524288 65536 2
47 1000 524288 65536 2
48 1000 524288 65536 2
49 1000 524288 65536 2
50 1000 524288 65536 2
51 1000 524288 65536 2
52 1000 524288 65536 2
53 1000 524288 65536 2
54 1000 524288 65536 2