cho.sh

논리식의 개수와 쿼리

시간 제한5초메모리 제한2048 MB

문제

논리 연산이란 참을 나타내는 논리값 1 과 거짓을 나타내는 논리값 0 을 다루는 연산을 말합니다. 이 문제에서는 다음의 두 가지 논리 연산자가 등장합니다.

  • 논리합 (|, OR): 양쪽의 두 값 중 한쪽이라도 1 이라면 연산의 결과는 1 입니다. 그렇지 않다면 연산의 결과는 0 입니다. 예시는 다음과 같습니다.

    • 0|0 = 0
    • 0|1 = 1
    • 1|0 = 1
    • 1|1 = 1

  • 논리곱 (&, AND): 양쪽의 두 값이 모두 1 이라면 연산의 결과는 1 입니다. 그렇지 않다면 연산의 결과는 0 입니다. 예시는 다음과 같습니다.

    • 0&0 = 0
    • 0&1 = 0
    • 1&0 = 0
    • 1&1 = 1

이때, 논리값 $N$개와 논리 연산자 $N-1$개가 번갈아서 등장하는 문자열을 길이 $2N-1$의 논리식이라고 부릅니다. 모든 논리식은 대응되는 하나의 논리값을 가지며, 이는 다음과 같이 구할 수 있습니다.

  1. 먼저, 논리식에 등장하는 논리곱 연산자 각각에 대해 양쪽의 두 값과 연산자를 지우고 해당하는 연산의 결과로 교체합니다.
  2. 다음, 논리식에 등장하는 논리합 연산자 각각에 대해 양쪽의 두 값과 연산자를 지우고 해당하는 연산의 결과로 교체합니다.

이때 하나의 논리식에 같은 논리 연산자가 여러 번 등장한다면 그중 맨 왼쪽부터 순서대로 연산을 수행합니다.

예를 들어 논리식 0&1&1|0|1|1&1 에 대해 다음과 같이 대응되는 논리값을 구할 수 있습니다.

  • 0&1&1|0|1|1&1
  • 0&1|0|1|1&1 (0&1 을 0 으로 교체합니다.)
  • 0|0|1|1&1 (0&1 을 0 으로 교체합니다.)
  • 0|0|1|1 (1&1 을 1 로 교체합니다.)
  • 0|1|1 (0|0 을 0 으로 교체합니다.)
  • 1|1 (0|1 을 1 로 교체합니다.)
  • 1 (1|1 을 1 로 교체합니다.)

따라서 0&1&1|0|1|1&1 에 대응되는 논리값은 1 입니다.

여러분이 해결해야 하는 문제는 다음과 같습니다.

여러분에게 길이 $2N-1$의 문자열이 주어집니다. 이 문자열은 다음 조건을 만족합니다.

  • 홀수 $i$에 대해, $i$번째 문자는 '0', '1', '?' 중 하나입니다.
  • 짝수 $i$에 대해, $i$번째 문자는 '|', '&', '?' 중 하나입니다.

여러분은 이 문자열에 대해 다음 동작을 $Q$번 수행해야 합니다.

  • $1$ 이상 $2N-1$ 이하의 정수 $k$와 문자 $c$가 주어질 때, 문자열의 $k$번째 문자를 $c$로 바꿉니다. 문자를 바꾼 후에도 문자열은 위의 조건을 항상 만족합니다.

이때 각 동작 후 논리식의 상태는 유지됩니다. 예를 들어 한 번의 동작으로 문자열 "0&??1|0|1|1&1"이 "0&??1|0|0|1&1"으로 바뀌었을 경우 그다음 동작은 문자열 "0&??1|0|0|1&1"에 수행합니다.

동작을 $Q$번 수행하면서, 각 동작 이전과 이후에 문자열에서 '?'를 각각 적절한 문자로 바꾸어 대응되는 논리값이 1인 올바른 논리식으로 만드는 방법의 가짓수를 구하는 프로그램을 작성해 주세요. 단, 정답이 매우 클 수 있으니 정답을 $998\ 244\ 353$으로 나눈 나머지를 구해 주세요.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어집니다.

그다음 줄부터 $T$개의 테스트 케이스가 주어집니다. 테스트 케이스의 형식은 다음과 같습니다.

첫 번째 줄에는 두 정수 $N$과 $Q$가 공백으로 구분되어 주어집니다.

두 번째 줄에는 길이 $2N-1$의 논리식이 공백 없이 주어집니다.

그다음 줄부터 $Q$개의 줄에 각각 수행해야 하는 동작을 나타내는 정수 $k_i$와 문자 $c_i$가 공백으로 구분되어 주어집니다.

출력

각 테스트 케이스에 대해 새로운 줄에 $Q+1$개의 정수를 공백으로 구분해 출력합니다. 출력해야 하는 정수는 다음과 같습니다.

  • 첫 번째로 출력할 정수는 처음 주어진 문자열에 대한 정답을 $998\ 244\ 353$으로 나눈 나머지입니다.
  • $i>1$일 때, $i$번째로 출력할 정수는 $i-1$번째 동작 후의 정답을 $998\ 244\ 353$으로 나눈 나머지입니다.

제한

  • $1 \le T \le 1000$
  • $1 \le N \le 500\ 000$
  • $1 \le Q \le 100\ 000$
  • $1 \le k_i \le 2N-1$
  • 모든 테스트 케이스에서 $N$의 합은 $500\ 000$을 초과하지 않습니다.
  • 모든 테스트 케이스에서 $Q$의 합은 $100\ 000$을 초과하지 않습니다.
  • 홀수 $i$에 대해, $i$번째 문자는 항상 '0', '1', '?' 중 하나입니다.
  • 짝수 $i$에 대해, $i$번째 문자는 항상 '|', '&', '?' 중 하나입니다.

힌트

첫 번째 테스트 케이스에서, 처음 주어진 문자열은 "???"입니다. 정답을 구할 $Q+1$개의 문자열과 대응되는 설명은 다음과 같습니다.

  1. "???": 논리값 1 에 대응되는 논리식 0|1, 1|0, 1|1, 1&1 을 만들 수 있습니다. 정답은 $4$입니다.
  2. "?|?": 논리값 1 에 대응되는 논리식 0|1, 1|0, 1|1 을 만들 수 있습니다. 정답은 $3$입니다.
  3. "?&?": 논리값 1 에 대응되는 논리식 1&1 을 만들 수 있습니다. 정답은 $1$입니다.
  4. "???": 논리값 1 에 대응되는 논리식을 만들 수 없습니다. 정답은 $0$입니다.
  5. "0??": 논리값 1 에 대응되는 논리식 0|1 을 만들 수 있습니다. 정답은 $1$입니다.