바이러스

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

현재 가용한 정보를 취합해서 얻어낸 바이러스의 비트 패턴은 정규 표현식으로 다음과 같다.

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

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

• 비트를 그대로 적으면 정확히 일치하는 한 글자의 비트열을 찾는다.

  • 0 = { "0" }
  • 1 = { "1" }

• 모든 정규 표현식 x와 y에 대해 다음 연산이 성립한다.

  • 괄호를 씌운 (x)는 x와 일치하는 비트열을 동일하게 찾는다.

    • (0) = { "0" }
    • (1) = { "1" }

  • 연산자 없이 두 정규 표현식을 연결한 xy는 두 정규 표현식과 일치하는 비트열 중 하나씩을 순서대로 연결한 비트열을 찾는다.

    • 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$을 만족한다.