ในปี 2077 การออกโจทย์กลายเป็นเรื่องง่าย หุ่นยนต์จะสร้างโจทย์ขึ้นมาโดยการกำหนดการดำเนินการแบบสุ่มบางอย่างแล้วแก้โจทย์นั้นเอง ผู้ออกโจทย์เพียงแค่ต้องตรวจสอบว่าโจทย์นั้นถูกต้องหรือไม่

นี่คือโจทย์จากปี 2077:

กำหนดการเรียงสับเปลี่ยน $p_1, p_2, \dots, p_n$ โดยรับประกันว่า $n$ เป็นจำนวนคู่ คุณต้องการเรียงลำดับการเรียงสับเปลี่ยนนี้โดยใช้การดำเนินการเพียงชนิดเดียว:

• FakeSort(l,r): คุณต้องรับประกันว่า $r - l + 1$ เป็นจำนวนคู่ ให้ $k = r - l + 1$ แล้วสมาชิกที่มากที่สุด $k/2$ ตัว และสมาชิกที่น้อยที่สุด $k/2$ ตัวในลำดับย่อยต่อเนื่อง $p_l, p_{l+1}, \dots, p_r$ จะถูกเรียงลำดับแยกกันอย่างเป็นอิสระ กล่าวคือ ให้ $L_1, L_2, \dots, L_{k/2}$ เป็นดัชนีของจำนวนที่มากที่สุด $k/2$ ตัว และ $S_1, S_2, \dots, S_{k/2}$ เป็นดัชนีของจำนวนที่น้อยที่สุด $k/2$ ตัว เราจะเรียงลำดับจำนวนที่อยู่ในดัชนี $L_1 \sim L_{k/2}$ ก่อน จากนั้นจึงเรียงลำดับจำนวนที่อยู่ในดัชนี $S_1 \sim S_{k/2}$

นี่คือตัวอย่างที่เป็นรูปธรรม สมมติว่าการเรียงสับเปลี่ยนคือ $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ หากเราเรียก FakeSort(2,7):

• $k = r - l + 1 = 6$ ลำดับย่อยต่อเนื่อง $p_l, p_{l+1}, \dots, p_r$ คือ $\{5, 7, 1, 8, 6, 4\}$ เราจะเรียงลำดับจำนวนที่มากที่สุด $3$ ตัว และจำนวนที่น้อยที่สุด $3$ ตัวของลำดับนี้แยกกันอย่างเป็นอิสระ
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; จำนวนที่มากที่สุด $3$ ตัวแสดงด้วยตัวหนา หลังจากเรียงลำดับแล้ว พวกมันจะกลายเป็น $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; จำนวนที่น้อยที่สุด $3$ ตัวแสดงด้วยตัวหนา หลังจากเรียงลำดับแล้ว พวกมันจะกลายเป็น $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$

ดังนั้น $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ หลังจากทำ FakeSort(2,7) จะกลายเป็น $\{2, 1, 6, 4, 7, 8, 5, 3\}$

โปรดใช้การดำเนินการไม่เกิน $114$ ครั้งเพื่อเรียงลำดับการเรียงสับเปลี่ยนนี้ หรือระบุว่าเป็นไปไม่ได้ สามารถพิสูจน์ได้ว่าหากการเรียงสับเปลี่ยนสามารถเรียงลำดับด้วยการ์ดำเนินการนี้ได้ จะมีวิธีที่ใช้การดำเนินการไม่เกิน $114$ ครั้งเสมอ

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยหลายชุดทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^3$) แทนจำนวนชุดทดสอบ

สำหรับแต่ละชุดทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มคู่ $n$ ($4 \le n \le 10^5$) แทนความยาวของการเรียงสับเปลี่ยน

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน คือ $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) แทนการเรียงสับเปลี่ยนที่คุณต้องเรียงลำดับ รับประกันว่า $p$ เป็นการเรียงสับเปลี่ยน

รับประกันว่าผลรวมของ $n$ จากทุกชุดทดสอบจะไม่เกิน $2 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ หากไม่สามารถเรียงลำดับการเรียงสับเปลี่ยนได้ ให้พิมพ์ $-1$

มิฉะนั้น ให้พิมพ์จำนวนเต็ม $k$ ($0 \le k \le 114$) แทนจำนวนครั้งของการดำเนินการที่ใช้

ในอีก $k$ บรรทัดถัดมา ให้พิมพ์ $l, r$ ($1 \le l \le r \le n$, โดยที่ $r - l + 1$ เป็นจำนวนคู่) ในแต่ละบรรทัด แทนการดำเนินการ FakeSort(l,r)

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

3
4
2 1 4 3
6
3 6 5 1 2 4
8
3 2 1 7 5 4 6 8

ข้อมูลส่งออกตัวอย่าง 1

1
1 4
-1
2
4 7
1 6