Liên đoàn các câu lạc bộ lập trình sinh viên toàn quốc cuối cùng đã phóng tàu thăm dò vũ trụ UCPC 1! Con tàu này đang du hành trong vũ trụ với một bảng điện tử hiển thị dãy số và các truy vấn, vốn là biểu tượng của việc giải các bài toán thuật toán.

Bảng điện tử được chia thành $N$ ô, mỗi ô hiển thị một số nguyên. Dãy số này thay đổi thành một dãy số khác vào mỗi nửa đêm, trong đó ô thứ $i$ sẽ hiển thị giá trị lớn nhất trong các số được hiển thị ở các ô từ $l_i$ đến $r_i$ của ngày hôm trước.

Thật không may, tàu UCPC 1 đã không hoàn thành chuyến thám hiểm thành công mà đi qua chân trời sự kiện của một hố đen và đang bị hút vào điểm kỳ dị. Tại thời điểm chạm tới điểm kỳ dị, mỗi ô trên bảng điện tử sẽ hiển thị số lớn nhất trong số các giá trị xuất hiện vô hạn lần tại ô đó khi thời gian trôi qua vô hạn.

Hãy tìm trạng thái bảng điện tử của tàu UCPC 1 khi chạm tới điểm kỳ dị.

Dữ liệu vào

Dòng đầu tiên chứa số lượng ô $N$ ($1 \le N \le 300\,000$).

Dòng thứ hai chứa các số nguyên $a_1, \dots, a_N$ được hiển thị ban đầu trên mỗi ô, cách nhau bởi dấu cách ($1 \le a_i \le N$; tất cả $a_i$ đều là số nguyên).

Từ dòng thứ ba trở đi, trong $N$ dòng tiếp theo, mỗi dòng chứa $l_i, r_i$ cách nhau bởi dấu cách ($1 \le l_i \le r_i \le N$).

Dữ liệu ra

In ra các số hiển thị trên mỗi ô của bảng điện tử khi tàu UCPC 1 chạm tới điểm kỳ dị, cách nhau bởi dấu cách.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4 3 3 4

Ghi chú

Dãy số được hiển thị lần lượt là $[1, 2, 3, 4], [4, 3, 3, 2], [3, 3, 3, 4], [4, 3, 3, 3], [3, 3, 3, 4], [4, 3, 3, 3], \dots$