[zerojudge] f164: 萬球同心移位之章

'''
這一題我的解法 1  :  NA (score:91%)
因為測資 #11 的 n 值比較大，第一個寫法
使用了比較大的記憶體，解法 2 才 AC
請看說明。
'''

# 解法 1

from sys import *

n, m, q = map(int, stdin.readline().split())
N = {k: [k-1, k+1] for k in range(n)} 
# 建立一個 dict ，且預設每個 key 的逆鄰及順鄰。
# n 值太大時，記憶體會不夠用，題目只有開 64MB

N[0][0] = n-1  # 頭尾手牽手
N[n-1][1] = 0

for _ in range(m):
    d, a, b = stdin.readline().split()
    a, b = int(a), int(b)
    if(a == b): continue # a, b 相等時，不處理。
    afk = N[a][1]        # 因為 a 要抽走，先找出 a 的順鄰 afk 及逆鄰 ark
    ark = N[a][0]
    N[afk][0] = ark      # 讓 afk 和 ark 手牽手，修補這個缺口。
    N[ark][1] = afk
    if(d == 'F'):        # 如果指令是 F  a 要放在 b 的順鄰。
        bfk = N[b][1]    # 先找出 b 原本的順鄰 bfk
        N[bfk][0] = a    # 設定 bfk 的逆鄰為 a
        N[a][1] = bfk    # 設定 a 的順鄰為 bfk
        N[a][0] = b      # 設定 a 的逆鄰為 b
        N[b][1] = a      # 設定 b 的順鄰為 a

    else:                # 如果指令是 R  a 要放在 b 的逆鄰。
        brk = N[b][0]    # 先找出 b 原本的逆鄰 brk
        N[brk][1] = a    # 設定 bfk 的順鄰為 a
        N[a][0] = brk    # 設定 a 的逆鄰為 brk
        N[a][1] = b      # 設定 a 的順鄰為 b
        N[b][0] = a      # 設定 b 的逆鄰為 a

Q = [N[int(x)] for x in stdin.readline().split()]
r = ' '.join(['{} {}'.format(a, b) for a, b in Q])
print(r)

# 解法 2

from sys import *

n, m, q = map(int, stdin.readline().split())
N = {}
# 建立一個空的 dict ，不給初值，有用到的 key 才給值。
# 因為 m < 10^3 ，須建立的 key 不多，相信不會爆。

N[0] = [n-1,1]    # 先建立頭尾的 key，一樣是頭尾手牽手
N[n-1] = [n-2, 0]

def initX(x): # 如果這個 key 值沒有出現過，它的 value 肯定是 [[x-1, x+1]]
    global N
    if(not N.__contains__(x)):
        N[x] = [x-1, x+1]
    return

def gp(x):    # 這是要輸出的 string ，原理同 initX
    global N
    if(not N.__contains__(x)):
        return '{} {}'.format(x-1, x+1)
    else:
        return '{} {}'.format(*N[x])
        
for _ in range(m):
    d, a, b = stdin.readline().split()
    a, b = int(a), int(b)
    if(a == b): continue # a, b 相等時，不處理。
    initX(a) # 對沒出現過的 key 給初值，底下同。
    initX(b) #
    afk = N[a][1]
    ark = N[a][0]
    initX(afk) #
    initX(ark) #
    N[afk][0] = ark
    N[ark][1] = afk
    if(d == 'F'):
        bfk = N[b][1]
        initX(bfk) #
        N[bfk][0] = a
        N[a][1] = bfk
        N[a][0] = b
        N[b][1] = a
    else:
        brk = N[b][0]
        initX(brk) #
        N[brk][1] = a
        N[a][0] = brk
        N[a][1] = b
        N[b][0] = a
Q = [gp(int(x)) for x in stdin.readline().split()]
r = ' '.join(Q)
print(r)