Bài hát All I Want For Christmas Is You của Mariah Carey trên sóng phát thanh hàng năm chính là báo hiệu một mùa Giáng sinh đang cận kề. Khi ngày kỷ niệm Chúa giáng trần tới gần, cũng là lúc mà Ông già Noel bận bịu nhất.

Năm nay, để tự động hóa quá trình đóng gói quà cho các em thiếu nhi trên khắp thế giới, Ông già Noel đã kết hợp công nghệ 4.0 với sức mạnh phép thuật để cho ra đời một dây chuyền sản xuất và đóng gói quà. Băng chuyền có độ dài là \(10^9 + 1\) ô, được đánh số từ \(0\) tới \(10^9\) từ trái sang phải. Ban đầu, trên băng chuyền sẽ có \(10^9 + 1\) món quà, cũng được đánh số từ \(0\) tới \(10^9\), và mỗi quà \(i\) sẽ nằm trên ô \(i\). Lúc này, cứ mỗi giây, một chiếc cần cẩu siêu to khổng lồ sẽ gắp một số món quà trên băng chuyền chuyển qua hệ thống đóng gói. Cụ thể hơn, cứ mỗi giây, hệ thống hoạt động như sau:

• Cần cẩu gắp đúng \(k\) món quà ở các ô \(a_1, a_2, \ldots, a_k\) đi.
• Băng chuyền sẽ đẩy các món quà về bên trái cho tới khi không còn ô trống nào trừ \(k\) ô ở bên phải ngoài cùng băng chuyền.
• Hệ thống sẽ sản xuất thêm \(k\) món quà mới, được đánh số bằng \(k\) số tự nhiên nhỏ nhất sao cho chưa từng có món quà nào được đánh số bởi các số này.
• Băng chuyền sẽ đặt \(k\) món quà vừa sản xuất vào \(k\) ô trống nêu trên của băng chuyền theo thứ tự tăng dần từ trái sang phải.

Giả định bạn đảm nhiệm trọng trách vận hành hệ thống này. Cho trước danh sách các ô \(a_1, a_2, \ldots, a_k\), bạn được yêu cầu thiết kế một chương trình quản lý để trả lời được các câu hỏi sau:

• Câu hỏi loại \(1\): Món quà \(x\) sẽ được gắp đi sau tối thiểu bao nhiêu giây?
• Câu hỏi loại \(2\): Sau \(y\) giây, món quà ở ô thứ \(x\) của băng chuyền là món quà nào?

Input

• Dòng đầu tiên chứa hai số nguyên \(k\) và \(q\) (\(1 \leq k, q \leq 5 \times 10^4\)) lần lượt là số lượng món quà sẽ được gắp mỗi giây và số lượng truy vấn.
• Dòng tiếp theo chứa \(k\) số nguyên \(a_1, a_2, \ldots, a_k\) (\(0 \leq a_1 < a_2 < \ldots < a_k \leq 10^9\)) cho biết vị trí các ô sẽ được gắp quà đi mỗi giây.
• Dòng thứ \(i\) trong số \(q\) dòng tiếp theo mô tả câu hỏi thứ \(i\), cụ thể như sau:
  • 1 x: là câu hỏi loại \(1\), yêu cầu cho biết món quà \(x\) (\(0 \leq x \leq 10^9\)) sẽ được gắp đi sau tối thiểu bao nhiêu giây, in ra -1 nếu món quà không thể được gắp đi.
  • 2 x y: là câu hỏi loại \(2\), yêu cầu cho biết sau \(y\) giây, món quà ở ô thứ \(x\) của băng chuyền là món quà nào. Dữ liệu đảm bảo \(0 \leq x, y \leq 10^9\) với mọi truy vấn loại này.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) gồm một số nguyên duy nhất là câu trả lời cho câu hỏi thứ \(i\), cụ thể như sau:
  • Với câu hỏi loại \(1\), in ra số giây tối thiểu để món quà \(x\) được gắp đi.
  • Với câu hỏi loại \(2\), in ra số thứ tự của món quà đang ở ô thứ \(x\) sau \(y\) giây.

Ví dụ

Input

3 2
1 3 5
1 6
2 4 2

Output

2
10

Giải thích

• Quá trình vận chuyển quà sẽ như sau:
  • Ban đầu, các món quà trên băng chuyền sẽ lần lượt là \(0\), \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), \(10\), \(11\), \(12\), \(13\), \(14\), \(\ldots\), \(10^9\).
  • Sau \(1\) giây, các món quà trên băng chuyền sẽ lần lượt là \(0\), \(2\), \(4\), \(6\), \(7\), \(8\), \(9\), \(10\), \(11\), \(12\), \(13\), \(14\), \(\ldots\), \(10^9\), \(10^9 + 1\), \(10^9 + 2\), \(10^9 + 3\).
  • Sau \(2\) giây, các món quà trên băng chuyền sẽ lần lượt là \(0\), \(4\), \(7\), \(9\) , \(10\), \(11\), \(12\), \(13\), \(14\), \(\ldots\), \(10^9\), \(10^9 + 1\), \(10^9 + 2\), \(10^9 + 3\), \(10^9+4\), \(10^9 + 5\), \(10^9 + 6\).
• Do vậy, đáp án cho các câu hỏi sẽ là:
  • Câu hỏi đầu tiên yêu cầu cho biết sau tối thiểu bao nhiêu giây thì món quà \(6\) sẽ bị gắp đi. Ta thấy ở giây thứ 2, các món quà \(2, 6, 8\) bị gắp đi. Do đó, sau tối thiểu \(2\) giây, món quà \(6\) sẽ bị gắp đi.
  • Câu hỏi thứ hai yêu cầu cho biết sau \(2\) giây thì món quà ở ô thứ \(4\) là món quà nào. Ta thấy sau \(2\) giây, món quà ở ô thứ \(4\) sẽ là món quà \(10\). Do đó đáp án là \(10\).

Ràng buộc

• Subtask \(1\) (\(33\%\) số điểm): \(k, q \leq 2000\);
• Subtask \(2\) (\(18\%\) số điểm): \(q \leq 30\);
• Subtask \(3\) (\(27\%\) số điểm): Không có câu hỏi loại \(2\);
• Subtask \(4\) (\(22\%\) số điểm): Không có ràng buộc gì thêm.