모든 곳을 지키려 하면 모든 곳의 병력이 적어진다.
- 손자, 『손자병법』 「허실」
당신은 장군을 모시며 진군 계획을 세우는 유능한 군사(軍師)이다. 장군이 이끄는 군대는 여러 지역을 차례로 지나가려 한다. 군대가 지나간 지역에는 수비대를 남겨야 하지만 앞으로 이동할 병력도 부족해서는 안 된다. 다행히 각 지역에는 행군 대열에 합류할 병사들이 준비되어 있다.
지역에는 번부터 번까지 번호가 붙어 있다. 군대가 번 지역을 지날 때에는 먼저 병사 명을 그 지역의 수비대로 남긴다. 그 직후에도 행군 대열에는 병사가 최소 한 명 남아 있어야 한다. 이후 그 지역에서 준비한 병사 명이 행군 대열에 합류한다. 수비대로 남긴 병사는 다시 합류하지 않는다.
첫째 줄에 지역의 수 과 명령의 수 가 공백으로 구분되어 주어진다.
다음 개의 줄 중 번째 줄에 와 가 공백으로 구분되어 주어진다.
두 번째 명령마다 필요한 최소 병사 수를 한 줄에 하나씩 출력한다. 두 번째 명령이 없다면 아무것도 출력하지 않는다.
첫 번째 예제의 첫 질문에서 병사 명으로 출발하면 다음과 같이 이동할 수 있다.
각 지역에서 합류할 병사의 수와 수비대로 남겨야 할 병사의 수에 관한 정보는 시시각각 바뀐다. 당신은 새로운 정보가 들어올 때마다 계획표를 수정하고 장군이 지정한 지역들을 통과하는 데 필요한 병력을 알려 주어야 한다. 다음 두 종류의 명령을 처리하여라.
1 i a b: 번 지역에서 합류할 병사의 수 를 로 바꾸고 수비대로 남길 병사의 수 를 로 바꾼다.2 l r: 번 지역부터 번 지역까지 번호가 증가하는 순서대로 통과하려면 번 지역에 진입할 때 행군 대열에 병사가 최소 몇 명 있어야 하는지 구한다.두 번째 명령에서는 지정된 모든 지역에서 위의 규칙을 만족해야 한다. 마지막 지역에서 수비대를 남긴 직후에도 병사가 최소 한 명 남아 있어야 한다. 각 질문은 그때의 계획표를 바탕으로 독립적으로 판단하며 실제로 진군을 실행하는 것은 아니다. 계획표의 값은 첫 번째 명령으로만 바뀐다.
다음 개의 줄에 명령이 하나씩 주어진다.
병사 명으로 출발하면 번 지역에서 수비대를 남긴 직후 행군 대열에 아무도 남지 않으므로 조건을 만족하지 못한다.
두 번째 예제의 마지막 질문에서는 병사 명이 합류하기 전에 수비대 명을 남겨야 한다. 따라서 처음에 필요한 병사 수는 명이다.