25553번 - 단짠단짠 피자

$N$개의 조각으로 이루어진 원형의 피자가 있다. 각 조각은 시계방향으로 $1$번부터 $N$번까지의 번호를 가지고 있으며, 피자가 원형이기 때문에 $N$번 조각 다음에는 $1$번 조각이 있다. 각 조각은 번호별로 종류가 다른데, 홀수 번호에 해당하는 조각은 파인애플 피자, 짝수 번호에 해당하는 조각은 페퍼로니 피자이다. 초기에 $i$번째 조각은 $A_i$만큼의 맛 수치를 가지고 있다. 포닉스는 지금 배가 매우 고프기 때문에 연속된 $K$개의 조각을 집어 한번에 먹으려 한다. 특정 조각에서 시작해 시계방향으로 연속된 $K$개의 조각을 먹었을 때 속한 조각의 맛의 합을 만족도라 하자. 포닉스는 만족도가 최대가 되게 하는 시작 조각을 선택하며, 만약 이러한 조각이 여럿일 경우 번호가 가장 작은 조각을 시작 조각으로 선택한다. 이때, $Q$개의 작업이 주어진다. 각 작업은 다음 세 가지 중 하나이다.

• 1 x : 모든 파인애플 피자 조각 (홀수 번째 조각)의 맛 수치를 $x$만큼 증가시킨다.
• 2 x : 모든 페퍼로니 피자 조각 (짝수 번째 조각)의 맛 수치를 $x$만큼 증가시킨다.
• 3 : 현재의 피자 상태에서 포닉스가 선택할 시작 조각의 번호와 해당 조각을 시작 조각으로 했을 때의 만족도를 공백으로 구분해 출력한다. 3번 작업으로 인해 피자의 상태가 변화하지는 않는다.

배가 고픈 포닉스를 위해 주어지는 작업을 올바르게 처리하는 프로그램을 작성하여라.

첫째 줄에 피자 조각의 수 $N$, 작업의 수 $Q$, 한번에 먹을 조각의 수 $K$가 주어진다. $(1 \leq K \leq N \leq 200\,000, 1 \leq Q \leq 200\,000)$

둘째 줄에는 각 조각의 초기 맛 $A_i$가 공백으로 구분되어 주어진다. $(-100\,000 \leq A_i \leq 100\,000)$

셋째 줄부터 $Q$줄에 걸쳐 처리해야 할 작업이 t x 또는 t 형식으로 주어진다. 3번 작업이 최소 한 번 주어짐이 보장된다. $(t \in \{1,2,3\}, -100\,000 \leq x \leq 100\,000)$

주어지는 수는 모두 정수이다.

각 3번 작업에 대한 답을 입력된 순서대로 한 줄에 하나씩 출력한다.