Cho một dãy \(N\) số nguyên dương \(A_1, A_2, . . . , A_N\) và một số nguyên \(K\). Một dãy con liên tiếp là một tập hợp các phần tử đứng cạnh nhau.

Yêu cầu: Tìm hai dãy con liên tiếp không giao nhau thỏa mãn:

• Với mỗi dãy con, hai phần tử bất kì trong dãy con chênh lệch giá trị không quá \(K\);
• Tổng số lượng phần tử trong cả hai dãy con là nhiều nhất.

Input

• Dòng đầu chứa hai số nguyên \(N, K(1 \le N \le 3 \times 10^5, 0 \le K \le 10^9)\);
• Dòng thứ hai chứa N số nguyên \(A_1, A_2, . . . , A_N (0 \le A_i \le 10^9)\).

Output

• In ra duy nhất một số là số lượng phần tử nhiều nhất của hai dãy con liên tiếp.

Example

5 2
1 3 2 5 4

5

5 2
1 3 5 2 4

4

Có \(n\) cái lỗ nằm dọc theo một đường thẳng đánh số \(1, 2, ..., n\) từ trái qua phải. Trong lỗi thứ \(i\) có đặt một lò xo có độ đàn hồi \(a_i\). Nếu như có một viên bi rơi vào lỗ \(i\) thì nó sẽ nảy lên rơi vào lỗ \(i + a_i\) nếu như \(i + a_i \le n\) còn nếu không sẽ ra khỏi hàng (nhảy vượt qua lỗ \(n\)), quá trình này lại tiếp tục như vậy... cho đến khi viên bi nhảy vượt qua lỗ \(n\). Có \(m\) thao tác được người chơi bi thực hiện lần lượt thuộc một trong hai loại sau:

• Thay lò xo có độ đàn hồi \(b\) vào lỗ \(a\)
• Bắn một viên bi vào lỗ \(a\) và đếm xem nó nhảy qua bao nhiêu lỗ trước khi vượt qua lỗ \(n\) ?.
  In ra giá trị này.

Yêu cầu: Viết chương trình thực hiện \(m\) thao tác nói trên

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m (1 \le n, m \le 105 )\)

• Dòng thứ hai chứa n số nguyên dương không vượt quá n là độ đàn hồi ban đầu của các
  lò xo đặt ở các lỗ \(1, 2, ..., n\)

• m dòng cuối, mỗi dòng mô tả một thao tác thuộc một trong hai dạng:

• \(0\) \(a\) \(b\): Đặt lại độ đàn hồi của lò xo ở lỗ \(a\) thành \(b\) \((1 \le a, b \le n)\)

• \(1\) \(a\): Tính số lỗ mà viên bi nhảy vào nếu bắn vào lỗ \(a\) \((1 \le a \le n)\)

Output

• Với các thao tác dạng \(1\) \(a\) in ra trên một dòng hai số nguyên, số thứ nhất là số hiệu của lỗ cuối cùng trong hàng mà viên bi nhảy đến, số thứ hai là số lỗ mà viên bi nhảy vào trước khi vượt qua lỗ \(n\)

Example

8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2

8 7
8 5
7 3

Nông dân John đang dự định mở một trường đại học mới cho các chú bò!

Có tổng cộng \(N (1 \le N \le 10^5)\) chú bò có thể dự định nhập học vào trường này. Mỗi chú bò sẵn sàng trả một mức học phí tối đa là \(c_i (1 \le c_i \le 10^6)\). Nông dân John có thể điều chỉnh học phí sao cho mọi chú bò phải trả để nhập học. Nếu mức học phí vượt mức tối đa mà một chú bò sẵn sàng chi, chú bò này sẽ không nhập học. Nông dân John muốn kiếm thật nhiều tiền để có thể trả lương cho các giảng viên một cách công bằng nhất. Hãy cho biết lượng tiền mà bác John có thể kiếm được, và lượng học phí mà bác John cần điều chỉnh.

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là \(N\) số \(c_1, c_2, \dots, c_N\), trong đó \(c_i\).

Output

• Lượng tiền tối đa mà bác John có thể kiếm được, và lượng học phí mà bác John cần điều chỉnh.

Scoring

• Subtask \(1\): \(c_i \le 1000\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Không có thêm ràng buộc.

4
1 6 4 6

12 4