불평등을 줄여라

콤플렉시도니아가 오늘날처럼 평화롭고 평등한 나라였던 적은 없다. 부유한 콘스탄토네스 일족은 지역 언론을 장악하고 콤플렉시도니아를 잔혹한 경제 체제, 즉 Nlogonialism의 폭정에 빠뜨렸다. 이 체제는 극단적인 불공정을 조장했고, 이상하게도 언제나 콘스탄토네스에게만 이로웠다.

콘스탄토네스가 대부분의 부를 차지한 반면 쿠아드라도네스는 극심한 빈곤 속에 살았고, 불평등은 쿠아드라도네스를 게으르고 비효율적이라고 낙인찍어 정당화되었다. Nlogones는 쿠아드라도네스와 똑같이 일하면서도 자신들이 성실함과 약삭빠름을 겸비했기 때문에 더 잘 살고 있다고 믿으며 쿠아드라도네스를 깔보곤 했다. 쿠비오네스와 쿠아테르니오네스에게 상황은 더 나빴다. 이들은 이웃 나라 출신이라는 이유로 범죄자로 취급받았고, 동시에 콤플렉시도니아의 일자리를 빼앗는다는 비난을 받았다.

국제 집단주의 대중 의회(ICPC)가 콘스탄토네스를 전복하고 새로운 경제 체제를 세우면서 모든 것이 바뀌었다. 이 체제는 공정함을 추구하며, 각 주민이 살아가면서 경제적으로 좋은 시기와 나쁜 시기를 겪을 수 있다는 점을 고려한다.

새 체제에서는 개인이 축적할 수 있는 부의 상한 U와, 개인이 인간다운 생활을 유지하는 데 필요한 최소 부의 하한 L이 정해졌다. 매달 말에 모든 주민은 자신의 부를 평가한다. 상한을 넘는 부를 가진 사람은 초과분을 ICPC에 기부하고, 안타깝게도 하한보다 적은 부를 가진 사람은 ICPC에서 부족한 만큼 받아 정해진 하한에 도달한다.

농사에 능한 쿠아드라도네스는 재정 관리에 도움이 필요하다. 긴 Nlogonialism 시대로 환경이 심하게 훼손되어 콤플렉시도니아의 날씨는 매우 변덕스럽다. 이는 좋은 시기와 나쁜 시기를 오가는 농업에 큰 영향을 미친다.

한 농부가 N개월 동안의 순소득(소득에서 지출을 뺀 값) 기록 A1, A2, ..., AN을 가지고 있다. 농부는 이 데이터를 바탕으로 앞으로 ICPC에 짐이 되지 않도록 재산을 어떻게 운용할지 계획하려고 한다. 농부가 어떤 달 B의 시작에 초기 재산 X를 가지고 있을 때, 달 E의 끝에 얼마를 가지고 있을지 알고 싶어 한다. 매달 말에는 재산이 L 이상 U 이하가 되도록 기부하거나 기부를 받을 수 있다.

첫째 줄에는 세 정수 N (1 ≤ N ≤ 105), L, U (1 ≤ L ≤ U ≤ 2 × 106)가 주어진다. 이는 각각 농부가 순소득 기록을 가진 달의 수, 재산의 하한, 재산의 상한이다. 둘째 줄에는 N개의 정수 A1, A2, ..., AN (−106 ≤ Ai ≤ 106, i = 1, 2, ..., N)이 주어지며, Ai는 i번째 달의 순소득이다. 셋째 줄에는 농부가 관심을 가지는 시나리오의 수를 나타내는 정수 Q (1 ≤ Q ≤ 105)가 주어진다. 다음 Q개 줄에는 각각 하나의 시나리오를 나타내는 세 정수 B, E (1 ≤ B ≤ E ≤ N), X (L ≤ X ≤ U)가 주어진다. 이는 달 B의 시작에 재산 X를 가지고 시작하여 각 달 j = B, B + 1, ..., E의 순소득이 Aj일 때, 달 E의 끝에 얼마를 가지고 있는지 알고 싶다는 뜻이다.

Q개 줄에 걸쳐, 각 시나리오에서 설명한 기간이 끝났을 때 농부가 가진 재산을 나타내는 정수를 한 줄에 하나씩 출력한다.

첫 번째 시나리오에서 농부의 순소득은 [10, 1, −1, −70]이고 초기 재산은 31이다.

• 첫째 달이 끝나면 재산은 41이다. 1 ≤ 41 ≤ 41이므로 기부도 받지도 않는다.
• 둘째 달이 끝나면 재산은 42이다. 42 > 41이므로 1을 기부하고, 그 달을 재산 41로 마친다.
• 셋째 달이 끝나면 재산은 40이다. 다시 1 ≤ 40 ≤ 41이므로 기부도 받지도 않는다.
• 마지막으로 넷째 달이 끝나면 재산은 −30이다. −30 < 1이므로 ICPC에서 기부를 받아 그 달을 재산 1로 마친다.

따라서 이 시나리오에서 농부는 재산 1을 가지고 끝난다.