Vào ngày sinh nhật của Nobita, Doraemon quyết định tặng cho cậu một trò chơi thực tế ảo và cậu rất thích với trò chơi này. Trong trò chơi Nobita sẽ được hoá thân thành một siêu anh hùng giải cứu trái đất. Có \(n\) chiếc UFO (Unidentified Flying Object - vật thể bay không xác định) đang lần lượt tấn công vào trái đất theo thứ tự từ \(1 \dots n\), và nhiệm vụ của Nobita là tiêu diệt toàn bộ các UFO trên để đảm bảo sự bình yên của trái đất. Nobita phải tiêu diệt lần lượt các UFO vì nếu nó đã vượt qua cậu ấy thì cậu ấy sẽ bị mất bình tĩnh và không bắn được nữa.

Trò chơi có \(t\) màn và phải chơi lần lượt theo thứ tự tăng dần. Ban đầu Nobita được trang bị duy nhất một khẩu súng thường, loại này có tầm ngắm bằng \(1\) với không giới hạn số lần sử dụng và mỗi lần bắn tốn chi phí là \(a\).

Trước mỗi màn thứ \(i\) (\(1 \le i \le t\)) sẽ có thêm một khẩu súng đặc biệt có tầm ngắm \(d_i\) và tốn chi phí \(c_i\) xuất hiện ngay sau khi UFO thứ \(u_i\) được tiêu diệt, và nếu không dùng ngay thì nó sẽ biến mất khi UFO thứ \(u_i+1\) được tiêu diệt.

Giả sử đã tiêu diệt được \(i\) UFO và sử dụng một khẩu súng có tầm ngắm \(X\) thì nó có thể tiêu diệt tất cả các UFO từ \(i + 1\) đến vị trí \(j\) bất kì sao cho \(j - i \le X\). Nobita là một tay súng thiện xạ nên tỉ lệ bắn trúng của cậu ta là \(100\%\). Việc tiêu diệt hết các UFO đối với Nobita là quá đơn giản, tuy nhiên cậu khá lười biếng nên cậu có \(q\) câu hỏi sau:

Với câu hỏi thứ \(i\) (\(1 \le i \le q\)), nếu cậu đã chơi được tới màn thứ \(x_i\) và đã tiêu diệt được \(y_i\) UFO thì chi phí thấp nhất để cậu tiêu diệt \(z_i\) UFO tiếp theo là bao nhiêu.

Nobita tính toán không nhanh nên cậu ấy quyết định nhờ các bạn giúp đỡ.

Input

• Từ file văn bản CHIENDAU.INP:
  • Dòng đầu: \(n, a, t, q\) (\(1 \le n, t, q \le 5 \cdot 10^4\), \(1 \le a \le 10^9\)).
  • \(t\) dòng tiếp theo là các khẩu súng đặc biệt sẽ được thêm vào: Với màn thứ \(i\) có dạng \(u_i, d_i, c_i\) (\(1 \le u_i \le n\), \(1 \le d_i \le 5\), \(1 \le c_i \le 10^9\)).
  • Tiếp theo \(q\) câu hỏi: Câu hỏi thứ \(i\) có dạng \(x_i, y_i, z_i\) (\(1 \le x_i \le t\), \(0 \le y_i \le n\), \(0 \le z_i \le n - y_i\)).

Output

• Ghi ra file văn bản CHIENDAU.OUT là kết quả bài toán.

Example

8 10 5 4
3 4 4
1 5 2
5 3 1
2 5 3
6 2 3
5 0 8
5 5 3
3 2 5
4 3 4

13
1
14
4

Ràng buộc

• Subtask 1 (\(50\%\) số test đầu tiên): \(1 \le n, t, q \le 2000\).
• Subtask 2 (\(20\%\) số test tiếp theo): \(x_i = t\) với mọi \(1 \le i \le q\).
• Subtask 3 (\(30\%\) số test còn lại): Không có ràng buộc gì thêm.

ông có ràng buộc gì thêm.