Bạn được cho một mảng \(a\) gồm \(n\) số nguyên. Giá trị của phần tử thứ \(i\) trong mảng là \(a_i\).

Bạn cũng được cho một tập hợp gồm \(m\) đoạn. Đoạn thứ \(j\) là \([l_j, r_j]\), trong đó \(1 \le l_j \le r_j \le n\).

Bạn có thể chọn một tập con bất kỳ từ tập hợp các đoạn đã cho và giảm giá trị trên mỗi đoạn được chọn đi một đơn vị (một cách độc lập). Ví dụ, nếu mảng ban đầu \(a = [0, 0, 0, 0, 0]\) và các đoạn được cho là \([1, 3]\) và \([2, 4]\), thì bạn có thể chọn cả hai đoạn đó và mảng sẽ trở thành \(b = [-1, -2, -2, -1, 0]\).

Bạn phải chọn một tập con của các đoạn đã cho (mỗi đoạn có thể được chọn tối đa một lần) sao cho nếu bạn áp dụng tập con các đoạn này vào mảng \(a\) và thu được mảng \(b\), thì giá trị \(\max(b) - \min(b)\) sẽ là lớn nhất có thể.

Lưu ý rằng bạn có thể chọn tập con rỗng.

Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^5, 0 \le m \le 300\)) — lần lượt là độ dài của mảng \(a\) và số lượng đoạn.

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^6 \le a_i \le 10^6\)), trong đó \(a_i\) là giá trị của phần tử thứ \(i\) của mảng \(a\).

\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên. Dòng thứ \(j\) trong số đó chứa hai số nguyên \(l_j\) và \(r_j\) (\(1 \le l_j \le r_j \le n\)), trong đó \(l_j\) và \(r_j\) là các điểm mút của đoạn thứ \(j\).

Dữ liệu ra

Trong dòng đầu tiên, in ra một số nguyên — giá trị lớn nhất có thể của \(\max(b) - \min(b)\).

Trong dòng thứ hai, in ra một số nguyên \(q\) — số lượng đoạn mà bạn chọn.

Trong dòng thứ ba, in ra \(q\) số nguyên phân biệt từ \(1\) đến \(m\) theo thứ tự bất kỳ — chỉ số của các đoạn mà bạn chọn. Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.

Ví dụ

5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3

6
2
1 4

5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5

7
2
2 3

1 0
1000000

0
0

Chú thích

Trong ví dụ đầu tiên, nếu chúng ta chọn các đoạn \(1\) và \(4\), mảng \(b\) sẽ trở thành \([0, -4, 1, 1, 2]\) và \(\max(b) - \min(b) = 2 - (-4) = 6\).

Trong ví dụ thứ hai, nếu chúng ta chọn các đoạn \(2\) và \(3\), mảng \(b\) sẽ trở thành \([2, -3, 1, -1, 4]\) và \(\max(b) - \min(b) = 4 - (-3) = 7\).

Trong ví dụ thứ ba, mảng \(a\) chỉ có một phần tử nên \(\max(a) - \min(a) = 0\) và bất kể chúng ta chọn các đoạn nào đi nữa thì đáp án vẫn sẽ là \(0\).