Cho bảng số \(A\) gồm \(m\) hàng và \(n\) cột, các hàng được đánh số từ \(1\) đến \(m\) từ trên xuống, các cột được đánh số từ \(1\) đến \(n\) từ trái sang. Ô nằm giao giữa hàng \(i\) và cột \(j\) gọi là ô \((i, j)\) và chứa số nguyên không âm \(a(i, j)\) có giá trị không vượt quá \(10^5\).

Thao tác \(sort(j)\) sẽ sắp xếp các hàng trong bảng theo giá trị không giảm của các số ở cột \(j\) (\(j = 1, 2, \dots, n\)), nếu số ở hai hàng tại cột \(j\) có giá trị bằng nhau thì hàng nào đang xếp trước sẽ được ưu tiên xếp trước. Cụ thể, với hai hàng \(i_1, i_2\) (hàng \(i_1\) đang xếp trước hàng \(i_2\)), sau khi thực hiện thao tác \(sort(j)\) thì hàng \(i_2\) sẽ chỉ được xếp trước hàng \(i_1\) nếu \(a(i_2, j) < a(i_1, j)\).

Xét dãy gồm \(s\) thao tác sắp xếp \(sort(j_1), sort(j_2), \dots, sort(j_s)\) và \(q\) truy vấn, truy vấn thứ \(t\) (\(1 \le t \le q\)) mô tả bằng ba số nguyên \(d_t, u_t, v_t\) (\(1 \le d_t \le s; 1 \le u_t \le m; 1 \le v_t \le n\)) có nghĩa là khi thực hiện lần lượt dãy thao tác sắp xếp ngoại trừ thao tác thứ \(d_t\) thì ô \((u_t, v_t)\) của bảng có giá trị là bao nhiêu.

Yêu cầu: Cho bảng số \(A\), dãy \(s\) và \(q\) truy vấn, với truy vấn thứ \(t\) hãy xác định ô \((u_t, v_t)\) trong bảng sau khi thực hiện \(s - 1\) thao tác sắp xếp (bỏ thao tác thứ \(d_t\)).

Input

• Dòng đầu gồm bốn số nguyên dương \(m, n, s, q\) (\(m \cdot n \le 10^5; s \le 10^5; q \le 10^5\)).
• Dòng thứ \(i\) (\(1 \le i \le m\)) trong số \(m\) dòng tiếp theo chứa \(n\) số nguyên không âm mô tả dòng thứ \(i\) của bảng \(A\).
• Dòng tiếp theo chứa \(s\) số nguyên (mỗi số có giá trị thuộc \([1, n]\)), mô tả dãy gồm \(s\) thao tác.
• Dòng thứ \(t\) (\(1 \le t \le q\)) trong \(q\) dòng tiếp theo chứa ba số nguyên \(d_t, u_t, v_t\) mô tả truy vấn thứ \(t\).

Output

• Gồm \(q\) dòng, dòng thứ \(t\) (\(1 \le t \le q\)) chứa một số nguyên là câu trả lời cho truy vấn thứ \(t\).

Example

3 3 4 3
1 1 3
1 1 2
1 1 1
1 2 3 1
4 1 1
4 1 3
1 3 3

1
1
3

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 100; s \le 100\) và tất cả các truy vấn giá trị \(d_t\) đều bằng \(1\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 100\) và tất cả các truy vấn giá trị \(d_t\) đều bằng \(1\).
• Subtask \(3\) (\(20\%\) số điểm): \(m \le 100\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(5\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.