Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hiệp đố Đức Anh tính số cách chọn ra một dãy con (không cần liên tiếp) có tổng bằng \(k\) trong dãy trên, Đức Anh khôn nên giải trong đúng \(36\) giây. Hiệp lại tăng độ khó, Hiệp hỏi \(q\) truy vấn \(l, r, k\) với ý nghĩa tính số cách chọn một dãy con có tổng bằng \(k\) trong dãy \(a_l, a_{l + 1}, \ldots, a_r\). Đức Anh gà nên nhờ bạn giúp, hãy giúp anh ấy.

Input

• Dòng đầu là hai số nguyên dương \(n\) và \(q\) \((1 \le n, q \le 10^5)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 100)\).
• \(q\) dòng tiếp theo, mỗi dòng là ba số nguyên dương \(l, r, k\) thể hiện một truy vấn \((1 \le l \le r \le n, k \le 100)\).

Output

• \(q\) dòng là đáp án cho \(q\) truy vấn, lấy dư cho \(10^9 + 7\).

Example

5 3
1 9 8 1 2
1 5 2
1 4 10
1 5 3

2
3
2

Cho một mảng 2 chiều (ma trận) \(A\) gồm \(n\) dòng và \(m\) cột. Có \(q\) truy vấn, mỗi truy vấn thuộc một trong 2 dạng sau:

• 1 i j: Đổi chỗ hàng \(i\) và hàng \(j\).
• 2 i j: Đổi chỗ cột \(i\) và cột \(j\).

In ra ma trận \(A\) sau khi thực hiện \(q\) thao tác. Các chỉ số hàng và cột được đánh số từ \(1\).

Input

• Dòng đầu tiên chứa 3 số nguyên \(n, m, q\) (\(1 \le n, m, q \le 100\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên, thể hiện ma trận \(A\) (\(|A_{i,j}| \le 100\)).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn có dạng 1 i j (đổi hàng) hoặc 2 i j (đổi cột). Các chỉ số \(i, j\) là hợp lệ.

Output

• In ra \(n\) dòng, mỗi dòng chứa \(m\) số nguyên, thể hiện ma trận \(A\) sau khi thực hiện \(q\) truy vấn. Các số trên cùng một dòng cách nhau bởi dấu cách.

Examples

3 3 1
1 2 3
4 5 6
7 8 9
1 1 3

7 8 9
4 5 6
1 2 3

1 2 3
4 5 6
7 8 9

7 8 9
4 5 6
1 2 3

2 3 2
1 2 3
4 5 6
2 1 3
1 1 2

6 5 4
3 2 1

1 2 3
4 5 6

3 2 1
6 5 4

6 5 4
3 2 1

Cho một bảng (ma trận) \(A\) kích thước \(n \times m\) (gồm \(n\) hàng và \(m\) cột) chứa các phần tử nguyên. Hãy xoay bảng này \(90\) độ theo chiều kim đồng hồ.

Lưu ý: Sau khi xoay, bảng mới sẽ có kích thước \(m \times n\) (\(m\) hàng và \(n\) cột).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n, m \le 50\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(A_{i,j}\) (\(1 \le A_{i,j} \le 100\)), là các phần tử của bảng.

Output

• In ra \(m\) dòng, mỗi dòng chứa \(n\) số nguyên, là bảng đã được xoay. Các số trên cùng một dòng cách nhau bởi dấu cách.

Examples

3 2
1 2
3 4
5 6

5 3 1
6 4 2

2 4
1 2 3 4
5 6 7 8

5 1
6 2
7 3
8 4

Cho một mảng \(A\) gồm \(N\) số nguyên.

Hãy tìm giá trị lớn thứ ba trong mảng.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(3 \le N \le 5.10^6\)), là số lượng phần tử của mảng.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)), là các phần tử của mảng.

Output

• In ra một số nguyên duy nhất là giá trị lớn thứ ba tìm được.

Examples

5
1 5 3 2 4

3