가로등

수중 운하 거리를 $n$개의 가로등이 밝히고 있으며, 거리를 따라 1번부터 $n$번까지 번호가 붙어 있다. 연속해서 놓인 하나 이상의 가로등을 세그먼트라고 부르자. 따라서 세그먼트의 총 개수는 $\frac{n(n+1)}{2}$개이다. 세그먼트에 속한 모든 가로등의 전구가 켜져 있으면 그 세그먼트를 정상이라고 한다.

가로등에는 두 가지 종류의 사건이 규칙적으로 일어난다.

• 어떤 세그먼트에서 전압 변동으로 모든 전구가 한꺼번에 나간다.
• 아르히에네르고가 어떤 세그먼트를 골라 수리공을 보내, 그 세그먼트에서 나간 전구를 모두 정상 전구로 교체한다.

사건이 일어날 때마다 시청은 아르히에네르고에 정상 세그먼트의 개수를 보고하라고 요구한다. 실적을 좋게 보이려고 수리공들은 지금 정상인 세그먼트와 이전에 한 번이라도 정상이었던 세그먼트를 모두 보고서에 넣는다.

각 사건이 일어난 뒤, 그 시점에 정상이거나 그 사건 이전에 한 번이라도 정상이었던 세그먼트의 개수를 구하는 프로그램을 작성해야 한다.

첫째 줄에 가로등의 개수 $n$과 일어난 사건의 개수 $q$가 주어진다. 다음 줄에는 가로등의 초기 상태를 나타내는 0과 1로 이루어진 $n$개의 문자가 주어지며, 1은 전구가 정상인 가로등, 0은 전구가 나간 가로등을 뜻한다.

이어지는 $q$개의 줄에는 사건의 설명이 세 수 $l_i, r_i, c_i$로 주어진다. 이는 이 사건 이후 $l_i, l_i+1, \ldots, r_i$번 가로등의 전구가 모두 다음과 같이 된다는 뜻이다.

• $c_i = 0$이면 나간다.
• $c_i = 1$이면 정상이 된다.

모든 사건에서 $1 \le l_i \le r_i \le n$이고, $c_i$는 $0$ 또는 $1$이다.

첫째 줄에 초기 상태의 정상 세그먼트 개수를 출력한다. 이어서 $q$개의 줄에 하나씩, 각 사건이 일어난 뒤 보고서에 넣는 세그먼트 개수를 출력한다.

• $1 \le n \le 300\,000$
• $1 \le q \le 300\,000$