합주 공연

마비노기에서 가장 번화한 도시 중 하나인 던바튼의 광장은 합주하기 위해 모여든 음악가들로 항상 북적인다.

$N$ 명의 음악가가 모여있고, 편의상 $1$번부터 $N$번까지 번호가 매겨져 있다. 음악가는 $1$번부터 $N$번까지 순서대로 줄 서 있다.

마비노기에는 인간, 엘프, 자이언트 세 종족이 있다. 엘프와 자이언트는 서로 적대적인 관계라 서로 인접하여 있으면, 집중을 못 하여 합주할 수 없다. 그 때문에 음악가 중 일부를 제외하여 엘프와 자이언트가 인접하지 않도록 해야 한다. 단, 음악가들이 제외되고 나면 빈자리 없이 서로 붙어서 합주해야 한다.

$1$번부터 $N$번까지 $N$ 명의 음악가의 종족이 주어졌을 때, 엘프와 자이언트가 인접하지 않도록 하기 위해 제외해야 하는 최소 인원을 계산하는 프로그램을 작성하라.

이 문제는 쿼리 형식으로 입력이 주어진다. 각 쿼리는 $(x, v, s, e)$의 형태인데, 이는 $x$번 음악가를 $v$ 종족으로 변경하고, $s$번부터 $e$번 음악가만 고려하였을 때 제외해야 하는 최소 인원을 구하라는 의미이다. 쿼리로 변경된 종족은 누적된다는 점에 유의하라.

입력 형식

첫 줄에 음악가의 수를 나타내는 정수 $N$과 쿼리의 수를 나타내는 정수 $Q$가 공백으로 구분되어 주어진다. ($1\le N \le 1\,000\,000;$ $1\le Q \le 300\,000$)

그다음 줄에 초기 각 음악가의 종족을 나타내는 영어 소문자 h, e, g로 구성된 길이가 $N$인 문자열이 주어진다. $i$ 번째 문자가 h라는 것은 $i$번 음악가가 인간 종족임을, $i$ 번째 문자가 e라는 것은 $i$번 음악가가 엘프 종족임을, $i$ 번째 문자가 g라는 것은 $i$번 음악가가 자이언트 종족임을 의미한다.

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 쿼리에 대한 정보가 주어진다. 각 줄은 쿼리에 해당하는 정수 $x$, 문자 $v$, 정수 $s$와 정수 $e$가 공백으로 구분되어 주어진다. ($1 \le x \le N;$ $1 \le s \le e \le N;$ $v$는 h, e, 또는 g이다)

출력 형식

$Q$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 $i$ 번째 쿼리에 대한 정답을 출력한다.

예제

4 5
eghg
3 h 1 4
3 e 1 4
2 h 1 3
3 g 2 4
2 e 2 3

1
2
0
0
1

예제 설명

초기 음악가의 종족을 나타낸 종족 문자열은 eghg이다. 첫 번째 쿼리는 $(3, h, 1, 4)$이므로 종족 문자열은 여전히 eghg이다. 종족 문자열 전체에 대한 쿼리이므로 $1$번 음악가를 제외하여 ghg인 배치를 얻거나, $2$번 음악가를 제외하여 ehg인 배치를 얻으면 조건을 만족시킬 수 있다. 따라서, 첫 쿼리에 대한 답은 $1$이다.

두 번째 쿼리는 $(3, e, 1, 4)$이다. 종족 문자열은 이제 egeg로 바뀌었다. 이 쿼리도 종족 문자열 전체에 대한 쿼리이다. $1$번과 $3$번 음악가를 제외하면 gg가 되어 조건을 만족한다. 이 쿼리에 대한 답은 $2$이다.

세 번째 쿼리는 $(2, h, 1, 3)$이다. 종족 문자열은 이제 eheg로 바뀌었다. 이 쿼리는 문자열의 $1$ 번째부터 $3$ 번째까지인 ehe에 대한 쿼리이다. 이 경우 그대로 조건을 만족하므로 답은 $0$이다.

네 번째 쿼리는 $(3, g, 2, 4)$이다. 종족 문자열은 이제 ehgg로 바뀌었다. 이 쿼리는 문자열의 $2$ 번째부터 $4$ 번째까지인 hgg에 대한 쿼리이다. 이 경우의 답은 $0$이다.

마지막 쿼리는 $(2, e, 2, 3)$이다. 종족 문자열은 이제 eegg로 바뀌었다. 이 쿼리는 문자열의 $2$ 번째부터 $3$ 번째까지인 eg에 대한 쿼리이다. 두 음악가 중 한 명을 제외하면 조건이 만족하므로 이 경우의 답은 $1$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설