Description

有三个宝石商，它们每人都拥有 $n$ 种不同的宝石，每种无限个。对于一个宝石商，他自身对 $n$ 种宝石有一个喜爱排名。我们记三个宝石商的喜爱排名为排列 $p,q,r$. 排列中越靠后的宝石其越喜欢。

Arahc 拥有一个 $1$ 种宝石，他希望得到价值更高的宝石。Arahc 也有一个喜爱排名：$a_i=i$. 即 Arahc 更喜欢种类编号更高的宝石。

每一轮，Arahc 可以选择一个宝石商，用他拥有的宝石去和这个宝石商的喜爱排名中排名比这种宝石更低的一种宝石交换（即用他更喜欢的去换他更不喜欢的）。

Arahc 希望在交易中保证每次交易都能得到在自己的喜爱排名中更高的宝石（即用自己更不喜欢的换到更喜欢的）。在此基础上，Arahc 希望得到一个 $n$ 种宝石，也就是他最喜欢的宝石。

按照惯例，他要你帮他，但是他只给 1s。而且他不仅要求你判断是否可行，还要你给出一种方案（若这样的方案存在），不然打死。

Format

Input

本题含有多组数据，第一行一个正整数 $T\,(1\leq T\leq 10^4)$ 表示数据组数。

对于每组数据，输入有四行。第一行输入一个正整数 $n\,(2\leq n\leq 10^5)$，表示宝石的种数。

随后三行，每行一个大小为 $n$ 的排列，分别表示 $p,q,r$.

保证所有数据的 $n$ 的和满足 $1\leq\sum n\leq 5\times10^5$.

Output

对于每组数据，若不可能实现，仅输出一个数 $-1$.

若可能实现，第一行输出一个正整数 $k$ 表示交换的次数。

随后 $k$ 行，每行输出 p,q,r 中的一个字符和一个正整数 $x$，以空格隔开。表示和喜爱排名为排列 $p$/$q$/$r$ 的那个宝石商交换得到一个 $x$ 种宝石。

Samples

2
4
1 3 2 4
1 2 4 3
2 1 3 4
4
1 2 4 3
1 2 3 4
2 1 4 3

3
r 2
p 3
q 4
-1

Limitation

1s, 256MiB.