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