바이러스

신종 컴퓨터 바이러스가 전 세계를 휩쓸고 있다! 바이러스를 분석하고 치료하는 데 당신의 도움이 필요하다.

현재 가용한 정보를 취합해 얻은 바이러스의 비트 패턴은 다음 정규 표현식으로 나타난다.

(1(10)+1*|0+10)+

정규 표현식은 문자열에 여러 연산을 더해 원하는 패턴을 기술할 수 있게 만든 것으로, 다음과 같이 읽으면 된다.

• 비트를 그대로 적으면 정확히 일치하는 한 글자의 비트열을 찾는다.
  • 0 = { "0" }
  • 1 = { "1" }
• 모든 정규 표현식 x와 y에 대해 다음 연산이 성립한다.
  • 괄호를 씌운 (x)는 x와 일치하는 비트열을 똑같이 찾는다.
    • (0) = { "0" }
    • (1) = { "1" }
  • 연산자 없이 두 정규 표현식을 연결한 xy는 x와 y에 각각 일치하는 비트열을 하나씩 골라 순서대로 이어 붙인 비트열을 찾는다.
    • 000 = { "000" }
    • 10010110 = { "10010110" }
  • x|y는 x와 일치하는 비트열이나 y와 일치하는 비트열 중 아무것이나 찾는다.
    • 0|1 = { "0", "1" }
    • 0(0|1)1 = { "001", "011" }
    • 1|111|11111 = { "1", "111", "11111" }
  • x*는 x와 일치하는 비트열이 0개 이상 연결된 비트열을 찾는다. 즉 x*는 (빈 문자열)|x|xx|xxx|...와 같은 뜻이다.
    • 0* = { "", "0", "00", "000", ... }
    • 01* = { "0", "01", "011", "0111", ... }
    • (01)* = { "", "01", "0101", "010101", ... }
    • 111(01|001)* = { "111", "11101", "111001", "1110101", "11100100101", "1110100100101", ... }
  • x+는 x와 일치하는 비트열이 1개 이상 연결된 비트열을 찾는다. 즉 x+는 x|xx|xxx|...와 같은 뜻이다.
    • 0+ = { "0", "00", "000", ... }
    • 01+ = { "01", "011", "0111", ... }
    • (01)+ = { "01", "0101", "010101", ... }
    • (01+)+ = { "01", "011", "01111", "01011", "0111010101", "01111011111011", ... }

연산자를 적용하는 순서는 다음과 같다. 예를 들어 01|10**는 (01)|(1((0*)*))로 읽는다.

• (x)
• x*, x+
  • 두 연산자의 우선순위는 같다.
• xy
• x|y

이 바이러스는 자신의 비트열을 계속 바꾸며 예측할 수 없는 움직임을 보이기 때문에, 비트열이 바뀔 때마다 빠른 연산과 탐지가 필요하다. 비트열은 다음과 같이 갱신될 수 있다.

• $fg\,l\,r$: $l$번째 비트부터 $r$번째 비트까지가 다음과 같이 갱신된다. 비트 번호는 왼쪽에서 오른쪽으로 0부터 세며, $l$과 $r$이 모두 포함된다.

  • 갱신 이전에 0이었던 비트는 $f$로 바뀐다.
  • 갱신 이전에 1이었던 비트는 $g$로 바뀐다.

• 갱신된 데이터는 다음번 갱신 전까지 메모리에 계속 남는다.

탐지한 메모리 구역의 비트열이 주어지면, 갱신될 때마다 그 비트열이 바이러스의 비트 패턴과 일치하는지 확인하는 프로그램을 작성하라.

첫 번째 줄에 메모리 구역의 비트 수 $N$이 주어진다.

두 번째 줄에 해당 메모리 구역의 초기 데이터 $S$가 숫자 0과 1만으로 이루어진 문자열로 주어진다.

세 번째 줄에는 데이터가 갱신되는 횟수 $Q$가 주어진다.

네 번째 줄부터 $Q$개의 줄에 걸쳐 데이터 갱신 정보가 한 줄에 하나씩 $fg\,l\,r$ 형태로 주어진다. $f$와 $g$ 사이에는 공백 문자가 없다.

첫 번째 줄에 초기 비트열이 바이러스의 비트 패턴과 일치하면 YES를, 그렇지 않으면 NO를 출력한다.

두 번째 줄부터는 비트열이 갱신될 때마다 갱신된 비트열이 바이러스의 비트 패턴과 일치하면 YES를, 그렇지 않으면 NO를 각각 한 줄에 출력한다.

출력하는 모든 문자는 대문자이다.

• $1 \le N, Q \le 100\,000$
• $|S| = N$
• 모든 갱신은 $f, g \in \{ 0, 1 \}$과 $0 \le l \le r \le N-1$을 만족한다.