강

플랫란디아에는 물고기가 풍부한 큰 플랫 강이 흐른다. 오래전 이 강은 n개의 어업 회사에 나뉘어, 각 회사가 강의 연속된 구간을 하나씩 받았다. 강의 발원지부터 순서대로 볼 때 i번째 회사는 처음에 길이 ai인 구간을 받았다.

그 후 플랫란디아의 어업 회사에는 k번의 사건이 일어났다. 각 사건은 어떤 회사의 파산 또는 어떤 회사의 분할 중 하나였다.

어떤 사건에서 그 사건이 일어난 회사가 가진 강 구간이 두 부분으로 나뉜다. 이렇게 나뉘는 구간의 길이는 항상 2 이상이다. 나누는 규칙은 다음과 같다. 구간의 길이가 짝수이면 두 개의 같은 길이로 나뉜다. 홀수이면 길이가 정확히 1만큼 차이나는 두 부분으로 나뉘며, 강의 발원지에 더 가까운 부분이 더 짧다.

회사가 파산하면 다음과 같이 된다. 파산한 회사가 가진 강 구간은 이웃 회사로 넘어간다. 파산한 회사에 이웃이 하나뿐이면 그 이웃이 파산한 회사의 구간 전체를 넘겨받는다. 이웃이 둘이면 구간이 위에서 설명한 방식으로 두 부분으로 나뉘고, 각 이웃이 자기에게 가까운 부분을 자기 구간에 이어 붙인다.

회사가 분할되면 그 회사가 가진 강 구간은 항상 위에서 설명한 방식으로 두 부분으로 나뉜다. 분할된 회사는 없어지고 두 개의 새 회사가 생긴다.

따라서 각 사건이 일어난 뒤에는 모든 회사가 강의 어떤 구간을 하나씩 가진다.

플랫란디아 재무부는 어업 회사에 세금을 매기려 하는데, 그 액수는 회사가 가진 강 구간 길이의 제곱에 비례한다. 이 세금이 어떻게 작동할지 분석하려는 장관은 주어진 자료로, 각 사건이 일어난 뒤 회사들이 가진 강 구간 길이의 제곱의 합이 어떻게 변했는지 알고 싶어 한다.

주어진 강의 초기 분할과 회사에 일어난 사건 목록으로부터, 초기 시점과 각 사건이 일어난 뒤의 회사들이 가진 강 구간 길이의 제곱의 합을 구하는 프로그램을 작성해야 한다.

첫째 줄에는 두 정수 n과 p가 주어진다. n은 처음 회사의 수(2 ≤ n ≤ 100 000)이고, p는 부분 문제 번호(0 ≤ p ≤ 4)이다.

둘째 줄에는 n개의 정수 a1, a2, …, an이 주어지며, 이는 처음 구간들의 길이이다.

셋째 줄에는 정수 k가 주어지며, 이는 회사에 일어난 사건의 수이다(1 ≤ k ≤ 100 000).

이어지는 k개의 줄에는 사건의 설명이 주어진다. i번째 줄에는 두 정수 ei와 vi가 주어지며, 각각 사건의 종류와 사건이 일어난 회사의 번호이다. ei = 1이면 이전 사건을 모두 반영한 뒤 강의 발원지부터 1번으로 세어 vi번째인 회사가 파산했다는 뜻이고, ei = 2이면 그 회사가 두 개로 분할되었다는 뜻이다.

vi는 현재 회사의 수를 넘지 않는다. 파산이나 분할로 구간을 두 부분으로 나누어야 할 때 그 구간의 길이는 2 이상이다. 강에 회사가 하나만 남으면 그 회사는 파산하지 않는다.

출력 파일에는 k + 1개의 정수가 한 줄에 하나씩 들어가야 한다. 첫째 줄에는 처음 강 구간 길이의 제곱의 합이, 그다음 k개의 줄에는 각 사건이 일어난 뒤의 강 구간 길이의 제곱의 합이 들어간다.

예제에 설명된 각 사건이 일어난 뒤 회사들 사이의 강 구간 분포는 아래 그림과 같다.

1번 회사의 파산 후

1번 회사의 분할 후

3번 회사의 파산 후

2번 회사의 분할 후

3번 회사의 파산 후