Statement
당신은 주어진 스케이트 코스에서 번의 스케이트 연습을 하려고 한다. 전체 코스는 총 개의 지점으로 이루어져 있으며, 각 지점은 고유한 번호가 부여되어 있다. 지점의 번호는 번부터 시작하여 번까지, 즉 순서로 붙어 있다.
번째 연습에서는 번 지점에서 연습을 시작하여 번 지점부터 번 지점까지를 순서대로 거친 뒤, 번 지점에서 연습을 끝낸다. 따라서 번째 연습 경로는 와 같다. 매 연습 경로는 다를 수 있다.
이 연습은 번 지점에서 의 속력으로 출발하여, 번 지점에 의 속력으로 도착한다. 번 지점에는 속력 제한 가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 만큼만 낮출 수 있다.
단, 시작 지점 번과 도착 지점 번을 제외한 위치에서 속력은 이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다. 지점별 속도 제한 는 모든 연습에서 동일하다.
연습의 성과는 각 지점에서의 속력의 합과 같다. 스케이트 코스의 속력 제한이 주어졌을 때, 각 연습마다 얻을 수 있는 최대 연습 성과를 구해보자. 단 성과가 너무 커질 수 있으므로, 최대 성과를 으로 나눈 나머지를 출력하여라.
Input
첫째 줄에 두 정수 가 공백으로 구분되어 주어진다.
둘째 줄에 개의 정수 이 공백으로 구분되어 주어진다.
다음 개의 줄 중 번째 줄에는 두 정수 가 공백으로 구분되어 주어진다.
Output
각 연습마다 한 줄에 하나씩, 해당 연습에서 얻을 수 있는 최대 연습 성과를 으로 나눈 나머지를 출력한다.