주차장 구역 순찰표

문제

주차장 관리실에서는 하루의 순찰 구역을 정하기 위해 주차면을 확인한다. 주차면에는 통로를 따라 1번부터 N번까지 번호가 붙어 있다. 각 주차면에는 차량 한 대가 있거나 아무 차량도 없다. 관리실은 특정 시각에 모든 주차면의 상태를 기록했으며, 이번 순찰표를 만드는 동안에는 이 기록이 바뀌지 않는다고 가정한다. 담당자는 서로 다른 순찰 계획 Q개를 검토한다. 각 계획은 시작 번호 L과 끝 번호 R로 주어지며, 번호가 L 이상 R 이하인 모든 주차면을 확인하는 계획이다. 양 끝 번호에 해당하는 주차면도 확인 대상에 포함된다. 주차면의 번호는 원형으로 이어지지 않으므로, 구간이 마지막 번호를 지나 처음 번호로 돌아가는 일은 없다. 모든 계획에서 L은 R 이하로 주어진다. 차량이 있는 주차면에서는 주차 표시를 대조하는 데 3분이 걸린다. 빈 주차면에서는 바닥 표시만 확인하므로 1분이 걸린다. 또한 계획에 포함된 서로 이웃한 주차면 사이를 이동할 때마다 1분이 더 걸린다. 따라서 주차면을 한 곳만 확인하는 계획에는 이동 시간이 없다. 시작 주차면까지 가는 시간과 마지막 주차면에서 관리실로 돌아오는 시간은 계산하지 않는다. 관리실은 각 계획에 대해 차량이 있는 주차면의 수와 필요한 총시간을 알고 싶다. 총시간은 각 주차면에서 확인하는 시간의 합에 구간 내부의 이동 시간을 더한 값이다. 같은 주차면이 여러 계획에 포함되더라도 계획들은 각각 독립적으로 평가한다. 앞선 계획에서 확인했다는 이유로 다음 계획의 시간이 줄어들지 않는다. 같은 구간이 여러 번 입력될 수도 있다. 주차 상태 기록과 순찰 계획들이 주어질 때, 입력된 순서대로 각 계획의 결과를 구한다. 계획들 사이에서 최적의 계획을 고르거나 순서를 바꾸는 작업은 하지 않는다. 모든 시간은 분 단위의 정수이며, 별도의 준비 시간이나 휴식 시간은 없다. 차량 수가 0인 구간도 빈 주차면을 확인하고 이동하는 데 필요한 시간을 계산해야 한다.

입력

첫째 줄에 두 정수 N과 Q가 주어진다. 1 ≤ N ≤ 40,000이고 1 ≤ Q ≤ 12,000이다.
둘째 줄에 N개의 정수 a_1, a_2, …, a_N이 공백으로 구분되어 주어진다. a_i는 0 또는 1이며, 0은 i번 주차면이 비어 있음을, 1은 차량이 있음을 뜻한다.
다음 Q개 줄에 계획 하나를 나타내는 두 정수 L과 R이 주어진다. 1 ≤ L ≤ R ≤ N이다.

출력

각 계획마다 차량이 있는 주차면 수와 총 소요 시간을 공백으로 구분하여 한 줄에 출력한다. 시간의 단위는 분이며 단위 문자는 출력하지 않는다. 결과는 계획이 입력된 순서를 따른다.

6 4
1 0 1 1 0 0
1 3
2 5
4 4
5 6

2 9
2 11
1 3
0 3

1 2
0
1 1
1 1

0 1
0 1

출처: Devin.KR 자체 제작