TopCoder

Thumb fhvirus
FHVirus
$\Huge{焼鶏}$

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

15.3% (9/59)

Description

好多寶石啊,終於遇到傳說中的隱藏關卡的你,看著面前一堆七彩的寶石,內心無比的興奮。
寶石從上到下總共 $N, (1 \leq N \leq 6666)$ 個排成一堆,其中從上面數來第 $i$ 個的顏色編號為 $A_i, (1 \leq A_i \leq N)$
不同顏色的寶石各自有不同的功能,像是綠色的可以掌握時間,紅色的可以掌握現實。
有個不成文的規則是這樣的,寶石必須從最上面拿,不然它可能會不平衡(假設你旁邊有個能裝無限顆寶石的無限手套,好讓你裝拿下來的寶石)
還有,每次如果要使用一顆寶石,我們必須先將它拿到手上,再用力的彈指頭,之後寶石就會散發出他的魔力(他不會消失,接下來還是可以用),重點在後頭,在寶石散發魔力後,為了保持宇宙的平衡,你必須把你持有的所有寶石一一放回去(從最上面一個一個疊回去),你可以按照任意順序放。

這時牆壁忽然裂了一個大縫,邪惡的復仇者們找上你了,因為你有太多寶石,他們也想要分一些,於是你想要拿寶石對付他們。
$N$ 位復仇者們一一上前攻擊你。要在一個復仇者受傷後,下一個復仇者才會上前。
已知第 $i$ 個前來攻擊你的復仇者害怕顏色編號為 $B_i, (1 \leq B_i \leq N)$ 的寶石所散發出的魔力,所以你決定拿寶石對抗他們。
唯一可惜的是,每當一顆寶石被拿起來一次,就會製造 $1$ 單位的不平衡,脆弱的宇宙最多只能承受 $10^ 5$ 單位的不平衡,所以聰明的你,決定先擬定好拿寶石放寶石的順序,好讓宇宙保持完美平衡

Input Format

第一行一個正整數 $N$ 代表寶石數量
第二行共有 $N$ 個正整數 $A_i$ 之間用一個空白隔開,第 $i$ 個數字代表從上到下第 $i$ 個寶石的顏色
第三行共有 $N$ 個正整數 $B_i$ 之間用一個空白隔開,第 $i$ 個數字代表第 $i$ 位襲擊你的復仇者所害怕的寶石

保證至少存在一種方法 使得你可以打敗所有敵人 又保持宇宙平衡

Output Format

先輸出一個正整數 $K$ 代表你製造了多少不平衡
接下來請按照操作順序輸出 $2K + N$ 行個操作。
如果你拿了寶石堆的一個寶石,請輸出一個字元T
如果你使用了手上的一個寶石,請輸出一個字元U
如果你放回了手上的一個寶石,請輸出一個字元P和一個數字$x$ (中間以一個空白隔開)代表你放回的是顏色編號為 $x$ 的寶石
如果有任何不合理的操作,像是
* 寶石堆空了卻拿寶石
* 手上沒有可以擊退前來的復仇者的寶石時使用寶石
* 放回一個你手上沒有的寶石
* 使用寶石後沒有將寶石歸位
* 等各種不符合題目規範的操作
那你將會拿到一個 WA

Sample Input

2
1 2
2 1

Sample Output

3
T
T
U
P 2
P 1
T
U
P 1

Hints

用完記得放回去喔

關於範測 output
接下來會這樣表示
S : { ... } 代表寶石堆的寶石們
G : { ... } 代表手上的寶石們
F : X 代表目前對手是 X (X == -1 代表對手都輸了)

順序是這樣的:

Round 0--
S : {1, 2}
G : {}
F : 2

Round 1 -- T
S : {2}
G : {1}

F : 2

Round 2 -- T
S : {}
G : {1, 2}

F : 2

Round 3-- U
S : {}
G :{1, 2}
F : 1

Round 4-- P 2 (因為上一輪使用了寶石 所以接下來要先把寶石歸位)
S : {2}
G : {1}

F : 1

Round 5-- P 1
S : {1, 2}
G :{}

F : 1

Round 6-- T (因為上一回合有把寶石全部歸位,所以這回合才能作其他事情
S : {2}
G : {1}

F : 1

Round 7-- U
S : {2}
G : {1}
F : -1

Round 8-- P 1 (這次也是因為上次使用了寶石,所以這回合只能把寶石放回去
S : {1, 2}
G :{}

F : -1

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0 $N = 1$ 1
2 0~10 $N \leq 100, \forall 1 \leq i < j \leq N, A_i \neq A_j, B_i \neq B_j$ 9
3 0~20 $N \leq 1500, \forall 1 \leq i < j \leq N, A_i \neq A_j, B_i \neq B_j$ 30
4 0~30 $N \leq 2000$ 20
5 0~40 $N \leq 4000$ 25
6 0~50 $N \leq 6666$ 15

Testdata and Limits

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