Cho mảng \(a\) gồm \(n\) phần tử \(a_1, a_2, ..., a_n\).

Có \(m\) thao tác, thao tác thứ \(i\) được biểu diễn bởi bốn số \(l_i\) \(r_i\) \(x_i\) \(y_i\): Với mọi \(j\) mà \(l_i \leq j \leq r_i\) và \(a_j = x_i\), gán \(a_j = x_i + y_i\).

Bạn cần trả lời \(q\) câu hỏi, câu hỏi thứ \(i\) tương ứng với ba số \(p_i\) \(u_i\) \(v_i\): Hãy cho biết giá trị của phần tử ở vị trí \(p_i\) sau khi thực hiện lần lượt các thao tác từ \(u_i\) đến \(v_i\).

Lưu ý: các câu hỏi độc lập với nhau, tức là trước mỗi câu hỏi, mảng \(a\) trở về trạng thái ban đầu.

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương \(n, m\) \((1 \leq n, m \leq 10^5)\) --- độ dài của mảng \(a\) và số lượng thao tác.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^5)\)~-- Giá trị ban đầu của mảng.
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo gồm bốn số \(l_i, r_i, x_i, y_i\) \((1 \leq l_i \leq r_i \leq m, 1 \leq x_i \leq x_i + y_i \leq 10^5)\) --- Mô tả thao tác thứ \(i\).
• Dòng tiếp theo chứa số nguyên duy nhất \(1 \leq q \leq 10^5\) --- số lượng câu hỏi.
• Dòng thứ \(i\) trong \(q\) dòng tiếp theo gồm ba số \(p_i, u_i, v_i (1 \leq p_i \leq n, 1 \leq u_i \leq v_i \leq m)\) --- mô tả câu hỏi thứ \(i\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là câu trả lời cho câu hỏi thứ \(i\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n,m,q \leq 5000\).
• Subtask \(2\) (\(20\%\) số điểm): \(l_i = 1, r_i = n\) với mọi thao tác và \(u_i = 1, v_i = m\) với mọi câu hỏi.
• Subtask \(3\) (\(23\%\) số điểm): \(n,m \leq 10000, q \leq 10^5\) và \(l_i = 1, r_i = n\) với mọi thao tác.
• Subtask \(4\) (\(17\%\) số điểm): \(n,m \leq 5 \times 10^4, a_i \leq 32\) và \(x_i \leq x_i + y_i \leq 32\).
• Subtask \(5\) (\(15\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

12
8

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

10
11
4
11
10
6
4
6
10
10