碱基配对（pair）

---

时间限制	空间限制
1000 ms	512 MB

---

题目背景

在普通高中教科书生物必修二【遗传与进化】中，我们学习了基因的本质，在 DNA 的结构一节中，我们学习了 DNA 的碱基互补配对原则，下面我们运用一下 DNA 的碱基互补配对原则解决一些问题。

题目描述

小 Z 会给你一串 DNA 单链，想请你输出 它遵循碱基互补配对原则的互补单链的碱基排列。从左往右看，小 Z 给你的 DNA 单链的碱基排列可能是 \(5'\sim3'\)，也可能是 \(3'\sim5'\)，同样，你输出的互补单链的碱基排列有可能需要是 \(5'\sim3'\)，也有可能需要是 \(3'\sim5'\)。

其中给出的 DNA 单链由且仅由集合 \(\{A,T,G,C\}\) 中的元素组成，其中 \(A\) 是腺嘌呤，\(T\) 是胸腺嘧啶，\(G\) 是鸟嘌呤，\(C\) 是胞嘧啶。

碱基互补配对原则为：

• \(A\) 与 \(T\) 相互配对。
• \(C\) 与 \(G\) 相互配对。

DNA 双链配对方式为：

• 首先，DNA 单链的一端为 \(3'\) 端，另一端为 \(5'\) 端。
• 从双链上看，双链的一端上存在一个单链的 \(3'\) 端和另一个单链的 \(5'\) 端，即 两个单链反方向配对结合，即 \(3'\sim5'\) 的方向结合 \(5'\sim3'\) 的方向。

形象化的，一个 DNA 双链结构可以表示为：

输入格式

本题包含多组测试数据

输入的第一行包含一个正整数 \(T\)，表示数据组数。

接下来包含 \(T\) 组数据，每组数据的格式如下：

• 第一行包含一个正整数和两个字符串 \(n,p,q\)，分别表示给出的单链碱基排列的数量，给出的单链的方向，和需要输出的互补单链的方向，其中 \(p,q\) 之间以一个空格隔开。
• 第二行包含一个字符串 \(s\)，表示给出的单链碱基排列。

其中，给出的方向均是 以从左到右为视角 的方向。

输出格式

对于每组测试数据，输出一个字符串 占据一行，为给出的单链碱基排列的互补单链的碱基排列， 需要按指定方向输出。

输入输出样例

输入样例 # 1

1
6 5'-3' 3'-5'
ATGCTC

输出样例 # 1

TACGAG

说明/提示

【样例解释 #1】

对于 样例 #1 中的第一组测试数据：

给出的 DNA 单链为 \(5'-ATGCTC-3'\)，则与之互补的单链为 \(3'-TACGAG-5'\)。

【样例 #2】

见选手目录下的 \(pair/pair2.in\) 和 \(pair/pair2.ans\)。

该样例满足测试点 \(1\sim5\) 的约束条件。

【样例 #3】

见选手目录下的 \(pair/pair3.in\) 和 \(pair/pair3.ans\)。

该样例满足测试点 \(6\sim10\) 的约束条件。

【样例 #4】

见选手目录下的 \(pair/pair4.in\) 和 \(pair/pair4.ans\)。

该样例满足测试点 \(11\sim15\) 的约束条件。

【样例 #5】

见选手目录下的 \(pair/pair5.in\) 和 \(pair/pair5.ans\)。

该样例满足测试点 \(16\sim20\) 的约束条件。

【样例 #6】

见选手目录下的 \(pair/pair6.in\) 和 \(pair/pair6.ans\)。

该样例满足测试点 \(21\sim25\) 的约束条件。

数据范围

对于 \(100\%\) 的数据保证：

• \(1\le T\le 10,1\le n\le 10^5\)。
• \(p,q\in\{5'-3',3'-5'\},s_i\in\{A,T,G,C\},i\in[1,n]\)。

测试点编号	\(T\le\)	\(n\le\)	\(p,q\)	\(s_i\in\)
\(1\sim 5\)	\(1\)	\(10\)	\(p=q,p\ne q\)	\(\{A,T,G,C\}\)
\(6\sim10\)	\(5\)	\(100\)	\(p=q,p\ne q\)	\(\{A,T,G,C\}\)
\(11\sim 15\)	\(5\)	\(10^3\)	\(p\ne q\)	\(\{A,T,G,C\}\)
\(16\sim 20\)	\(10\)	\(10^5\)	\(p=q\)	\(\{A,T,G,C\}\)
\(21\sim 25\)	\(10\)	\(10^5\)	\(p=q,p\ne q\)	\(\{A,T,G,C\}\)

时空限制

• 时间限制：1000 ms
• 空间限制：512 MB

题目分值

本题测试点分值等分，共计 \(25\) 个测试点，总分 \(100\) 分，每个测试点 \(4\) 分。

\(100\hspace{0.5mm}\text{pts in total},4\hspace{0.5mm}\text{pts for each test point.}\)