Giá Trị Nổi Bật Trên Đoạn

Bạn được cho một mảng số nguyên $a$ và nhiều truy vấn. Mỗi truy vấn chọn một đoạn chỉ số $[l,r]$, trong đó cả hai đầu đều thuộc đoạn.

Đặt $len=r-l+1$. Một giá trị được gọi là nổi bật trong truy vấn nếu nó xuất hiện nhiều hơn $\lfloor len/3\rfloor$ lần trong đoạn $a_l,\dots ,a_r$.

Với mỗi truy vấn, hãy tìm tất cả các giá trị nổi bật.

Input

• Dòng đầu chứa số nguyên $t$ - số bộ test.
• Với mỗi bộ test:
• Dòng đầu chứa hai số nguyên $n$ và $q$ - độ dài mảng và số truy vấn.
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Mỗi dòng trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$, mô tả đoạn cần xét theo chỉ số $1$-based.

Output

• Với mỗi truy vấn:
• In trên một dòng tất cả các giá trị nổi bật theo thứ tự tăng dần, cách nhau bởi một dấu cách.
• Nếu không có giá trị nào nổi bật, in $-1$.

Constraints

• $1\le t\le 10^4$.
• $1\le n,q\le 2\cdot 10^5$ trong mỗi bộ test.
• $1\le a_i\le 10^9$.
• $1\le l\le r\le n$.
• Tổng $n$ qua mọi bộ test không vượt quá $2\cdot 10^5$.
• Tổng $q$ qua mọi bộ test không vượt quá $2\cdot 10^5$.

Scoring

• Subtask $1$ ($50\%$ số điểm): Trong mỗi bộ test, $n,q\le 200$; đồng thời tổng $n$ và tổng $q$ của cả input đều không vượt quá $1000$.

• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

1
9 5
4 7 4 9 7 4 7 8 10
1 9
1 7
2 6
4 9
8 8

-1
4 7
4 7
-1
8