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. 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 đ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. 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ứ ~i~ bị tiêu diệt, và nếu không dùng ngay thì nó sẽ biến mất khi UFO thứ ~i+1~ bị tiêu diệt. Giả sử đã tiêu diệt được ~j~ 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ừ ~j+1~ đến vị trí ~j+x~ bất kì sao cho ~j+x \le n~.

Yêu cầu: Với mỗi câu hỏi, tính chi phí thấp nhất để tiêu diệt ~z_i~ UFO tiếp theo nếu đã chơi được tới màn thứ ~x_i~ và đã tiêu diệt được ~y_i~ UFO.

Input

• Dòng đầu: ~n, a, t, q~ (~1 \le n, t, q \le 5 \times 10^4~, ~1 \le a \le 10^9~).
• ~t~ dòng tiếp theo là các khẩu súng đặc biệt: ~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: ~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 kết quả của các câu hỏi.

Sample Input 1

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

Sample Output 1

13
1
14
4