using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("6");
WillReturn.Add("1 3 5 6 4 2");
WillReturn.Add("3 5 1 4 6 2");
//3 6
//0 0
//0 5
//0 0
//0 0
//4 2
}
else if (InputPattern == "Input2") {
WillReturn.Add("2");
WillReturn.Add("2 1");
WillReturn.Add("1 2");
//-1
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] PreArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long[] InArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long UB = PreArr.GetUpperBound(0);
if (PreArr[0] != 1) {
Console.WriteLine(-1);
return;
}
// InArrのInd[InArrの値]なDict
var IndDict = new long[InArr.Max() + 1];
for (long I = 0; I <= UB; I++) {
IndDict[InArr[I]] = I;
}
long[] ChangedIndArr = new long[UB + 1];
for (long I = 0; I <= UB; I++) {
ChangedIndArr[I] = IndDict[PreArr[I]];
}
var InsMinSparseTable = new SparseTable<long>(ChangedIndArr, true);
var InsMaxSparseTable = new SparseTable<long>(ChangedIndArr, false);
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.StaInd = 0;
WillPush.EndInd = UB;
Stk.Push(WillPush);
var AnswerDict = new Dictionary<long, AnswerDef>();
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
// 区間長さが1の場合
if (Popped.StaInd == Popped.EndInd) {
//Console.WriteLine("{0}は葉ノードです", PreArr[Popped.StaInd]);
AnswerDict[PreArr[Popped.StaInd]] = new AnswerDef() { LeftNode = 0, RightNode = 0 };
continue;
}
var LeftIndList = new List<long>();
var RightIndList = new List<long>();
long RootInd = IndDict[PreArr[Popped.StaInd]];
long Left = Popped.StaInd + 1;
long Right = Popped.EndInd;
if (RootInd < IndDict[PreArr[Left]]) { // 全て右部分木の場合
RightIndList.Add(Popped.StaInd + 1);
RightIndList.Add(Popped.EndInd);
long RangeMin = InsMinSparseTable.Query(Popped.StaInd + 1, Popped.EndInd);
if (RangeMin < RootInd) {
Console.WriteLine(-1);
return;
}
}
else if (IndDict[PreArr[Right]] < RootInd) { // 全て左部分木の場合
LeftIndList.Add(Popped.StaInd + 1);
LeftIndList.Add(Popped.EndInd);
long RangeMax = InsMaxSparseTable.Query(Popped.StaInd + 1, Popped.EndInd);
if (RootInd < RangeMax) {
Console.WriteLine(-1);
return;
}
}
else {
while (Left + 1 < Right) {
long Mid = (Left + Right) / 2;
long RangeMax = InsMaxSparseTable.Query(Popped.StaInd + 1, Mid);
if (RangeMax < RootInd) {
Left = Mid;
}
else {
Right = Mid;
}
}
LeftIndList.Add(Popped.StaInd + 1);
LeftIndList.Add(Left);
RightIndList.Add(Right);
RightIndList.Add(Popped.EndInd);
}
// 左部分木がある場合
if (LeftIndList.Count > 0) {
WillPush.StaInd = LeftIndList[0];
WillPush.EndInd = LeftIndList[1];
long RangeMax = InsMaxSparseTable.Query(WillPush.StaInd, WillPush.EndInd);
if (RootInd < RangeMax) {
Console.WriteLine(-1);
return;
}
Stk.Push(WillPush);
}
// 右部分木がある場合
if (RightIndList.Count > 0) {
WillPush.StaInd = RightIndList[0];
WillPush.EndInd = RightIndList[1];
long RangeMin = InsMinSparseTable.Query(WillPush.StaInd, WillPush.EndInd);
if (RangeMin < RootInd) {
Console.WriteLine(-1);
return;
}
Stk.Push(WillPush);
}
AnswerDef WillAdd;
WillAdd.LeftNode = 0;
WillAdd.RightNode = 0;
if (LeftIndList.Count > 0) {
WillAdd.LeftNode = PreArr[LeftIndList[0]];
}
if (RightIndList.Count > 0) {
WillAdd.RightNode = PreArr[RightIndList[0]];
}
AnswerDict[PreArr[Popped.StaInd]] = WillAdd;
}
var sb = new System.Text.StringBuilder();
foreach (var EachPair in AnswerDict.OrderBy(pX => pX.Key)) {
sb.AppendFormat("{0} {1}", EachPair.Value.LeftNode, EachPair.Value.RightNode);
sb.AppendLine();
}
Console.Write(sb.ToString());
}
struct JyoutaiDef
{
internal long StaInd;
internal long EndInd;
}
struct AnswerDef
{
internal long LeftNode;
internal long RightNode;
}
}
#region SparseTable
// スパーステーブル
internal class SparseTable<Type>
{
private Type[] mInitArr;
private long UB_0;
private long UB_1;
// 最小値か最大値[開始Ind,2の指数]なArr
private Type[,] mMinOrMaxArr;
// Log2の値[2べきな値] なDict
static Dictionary<long, long> mLogDict = new Dictionary<long, long>();
// 最小値を取得するか？
private bool mIsMin = false;
// コンストラクタ
internal SparseTable(IEnumerable<Type> pInitEnum, bool pIsMin)
{
mIsMin = pIsMin;
mInitArr = pInitEnum.ToArray();
UB_0 = mInitArr.GetUpperBound(0);
long Sisuu = 0;
long Beki2 = 1;
while (true) {
mLogDict[Beki2] = Sisuu;
if (Beki2 > mInitArr.Length) {
break;
}
Beki2 *= 2;
Sisuu++;
}
UB_1 = Sisuu;
mMinOrMaxArr = new Type[UB_0 + 1, UB_1 + 1];
// 長さ1の分を初期化
for (long I = 0; I <= UB_0; I++) {
mMinOrMaxArr[I, 0] = mInitArr[I];
}
for (long LoopLength = 2; LoopLength < long.MaxValue; LoopLength *= 2) {
bool WillBreak = true;
long HalfRange = LoopLength / 2;
for (long I = 0; I <= UB_0; I++) {
long StaInd1 = I;
long EndInd1 = I + HalfRange - 1;
long StaInd2 = EndInd1 + 1;
long EndInd2 = StaInd2 + HalfRange - 1;
if (EndInd2 > UB_0) break;
var KouhoList = new List<Type>();
KouhoList.Add(mMinOrMaxArr[I, mLogDict[HalfRange]]);
KouhoList.Add(mMinOrMaxArr[StaInd2, mLogDict[HalfRange]]);
if (mIsMin) {
mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Min();
}
else {
mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Max();
}
WillBreak = false;
}
if (WillBreak) break;
}
}
// 閉区間 [L,R]の最小値または最大値を求める
internal Type Query(long pL, long pR)
{
// 区間を内包する2べきを返す
long Beki2 = 1;
long Sisuu = 0;
while (true) {
long LeftRangeMax = pL + Beki2 - 1;
long RightRangeMin = pR - Beki2 + 1;
if (LeftRangeMax + 1 >= RightRangeMin) {
break;
}
Beki2 *= 2;
Sisuu++;
}
var KouhoList = new List<Type>();
KouhoList.Add(mMinOrMaxArr[pL, Sisuu]);
KouhoList.Add(mMinOrMaxArr[pR - Beki2 + 1, Sisuu]);
if (mIsMin) {
return KouhoList.Min();
}
return KouhoList.Max();
}
}
#endregion