여행하는 상인

동서 방향으로 뻗은 긴 도로가 있고, 도로를 따라 서쪽에서 동쪽으로 1번부터 n번까지 번호가 붙은 n개의 마을이 있다. 모든 마을은 같은 종류의 물건을 사고판다. 물건의 가치는 주간 일정에 따라 변한다. 마을에서는 그날 그 마을의 가치로 물건을 사고판다. 마을 i에서 물건의 가치는 한 주의 전반부에는 매일 di만큼 변하고, 후반부에는 매일 −di만큼 변한다. 다시 말해 마을 i에서 물건의 가치는 월요일과 일요일에 vi, 화요일과 토요일에 vi + di, 수요일과 금요일에 vi + 2di, 목요일에 vi + 3di이다.

한 상인이 사업차 여행 계획을 세우고 있다. 여행은 출발 마을 s에서 시작해 도착 마을 t에서 끝나며, s부터 t까지(양 끝 포함)의 각 마을을 정확히 한 번씩 방문한다. 상인은 월요일에 여행을 시작한다. 인접한 두 마을 사이를 이동하는 데는 정확히 하루가 걸리고, 상인은 목적지로 가는 길에 있는 다음 마을로 매일 이동한다. 상인은 여행 중 한 마을에서 물건을 정확히 하나 사고, 나중에 방문하는 마을에서 그 물건을 팔 수 있다. 사고 파는 것은 각각 한 번씩만 할 수 있다. 상인은 출발 마을 s와 도착 마을 t의 선택이 서로 다른 q개의 여행 계획 각각에 대해 얻을 수 있는 최대 이익을 알고 싶어 한다.

첫째 줄에 정수 n (2 ≤ n ≤ 105)이 주어진다. 다음 n개 줄에는 각각 정수 두 개가 주어진다. i번째 줄에는 vi (1 ≤ vi ≤ 109)와 di (1 ≤ vi + 3di ≤ 109)가 주어진다. 다음 줄에는 정수 q (1 ≤ q ≤ 105)가 주어진다. 그다음 q개 줄에는 각각 정수 두 개 s와 t (1 ≤ s, t ≤ n, s ≠ t)가 주어지며, 마을 s에서 마을 t로 가는 여행 계획 하나를 나타낸다. s < t이면 상인은 서쪽에서 동쪽으로 이동하고, 그렇지 않으면 동쪽에서 서쪽으로 이동한다.

각 여행 계획마다 상인이 얻을 수 있는 최대 이익을 한 줄에 하나씩 출력한다. 이익을 낼 수 없다면 0을 출력한다.