Có N con châu chấu đứng xếp thành một hàng chờ xem một buổi biểu diễn. Việc xếp hàng chờ đợi thật là buồn chán nên chúng thực hiện một số bước nhảy cho đỡ buồn có dạng như sau:

• Con châu chấu ở vị trí A nhảy qua đầu B con châu chấu khác về phía trái

• Con châu chấu ở vị trí A nhảy qua đầu B con châu chấu khác về phía phải

Tất nhiên các con châu chấu không có cùng độ cao, do vậy khi nhảy con châu chấu phải hết sức cẩn thận để chân của nó không va phải con châu chấu khác. Chính xác hơn nó cần phải nhảy với độ cao ít nhất bằng chiều cao con châu chấu cao nhất cần phải nhảy qua. Cho dãy các bước nhảy theo trình tự, hãy xác định chiều cao tối thiểu mỗi bước nhảy.

Dữ liệu: File NOGA.INP

• Dòng đầu tiên chứa hai số nguyên N, J (2≤N≤~10^5~, 1≤J≤~10^5~) là số lượng châu chấu và số lượng bước nhảy.

• Dòng thứ hai chứa N số nguyên nhỏ hơn 105 là chiều cao của các con châu chấu ở vị trí ban đầu. Độ cao được liệt kê từ trái qua phải.

• J dòng tiếp theo, mỗi dòng mô tả một cú nhảy theo trình tự nhảy. Với mỗi dòng, đầu tiên là số nguyên A (1≤A≤N) là vị trí của con châu chấu bắt đầu nhảy, tiếp theo là ký tự 'L' hoặc 'D' tùy theo là nhảy sang trái hoặc sang phải và cuối cùng là số nguyên B (1≤B≤N) là số lượng con châu chấu cần phải nhảy qua. Các bước nhảy luôn là hợp lệ (tức là B nhỏ hơn hoặc bằng số lượng con châu chấu ở bên trái (nếu 'L') hoặc bên phải (nếu 'D') của vị trí A)

Kết quả: File NOGA.OUT

Ghi ra J dòng, mỗi dòng là chiều cao tối thiểu của một cú nhảy theo trình tự trong file input.

Sample Input

9 3
5 3 8 4 9 3 7 4 2
2 D 3
8 L 2
5 D 2

Sample Output

9
7
4