Functions On The Segments

n개의 함수로 이루어진 배열 f가 있다. 함수 fi(x) (1 ≤ i ≤ n)는 매개변수 x1, x2, y1, a, b, y2에 의해 다음과 같은 값을 갖는다:

• y1, x ≤ x1인 경우.
• a·x + b, x1 < x ≤ x2인 경우.
• y2, x > x2인 경우.

쿼리가 m개 있다. 각 쿼리는 수 l, r와 x로 정해진다. 번호가 i인 쿼리 (1 ≤ i ≤ m)에 대해, l ≤ j ≤ r인 모든 fj(xi)의 합을 계산해야 한다. xi의 값은 다음과 같이 계산된다: xi = (x + last) mod 109이며, 여기서 last는 번호가 i - 1인 쿼리의 답이다. i = 1이면 last의 값은 0이다.

첫 번째 줄에 정수 하나 n가 주어진다 (1 ≤ n ≤ 75000).

이어서 주어지는 n개의 각 줄에는 여섯 정수 x1, x2, y1, a, b, y2가 주어진다 (0 ≤ x1 < x2 ≤ 2·105, 0 ≤ y1, y2 ≤ 109, 0 ≤ a, b ≤ 104).

다음 줄에 정수 하나 m가 주어진다 (1 ≤ m ≤ 500000).

이어서 주어지는 m개의 각 줄에는 세 정수 l, r, x가 주어진다 (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109).

예제

입력

1 1 2 1 4 5 10 1 1 1 2

13

입력

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

출력

19 17 11