33757번 - 논리 연산과 쿼리 서브태스크

문제

논리 연산이란 참을 나타내는 논리값 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$개가 번갈아서 등장하는 문자열을 길이 2ドルN-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 입니다.

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

여러분에게 길이 2ドルN-1$의 논리식이 주어집니다. 여러분은 이 논리식에 대해 다음 동작을 $Q$번 수행해야 합니다.

• 1ドル$ 이상 $N$ 이하의 정수 $k$가 주어질 때, 논리식에 등장하는 $k$번째 논리값을 바꿉니다. $k$번째 논리값이 1 이었다면 0 으로, 0 이었다면 1 로 바뀝니다.

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

동작을 $Q$번 수행하면서, 각 동작을 수행한 후의 논리식에 대응되는 논리값을 구하는 프로그램을 작성해 주세요.

입력

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

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

세 번째 줄에 수행해야 하는 동작을 나타내는 정수 $k_1,k_2,\ldots,k_Q$가 공백으로 구분되어 주어집니다.

출력

한 줄에 길이 $Q$의 문자열 $S$를 출력합니다. $i$번째 동작 후 논리식에 대응되는 논리값이 1 이라면 $S_i$는 '1', 0 이라면 $S_i$는 '0'입니다.

제한

• 1ドル \le N,Q \le 200\ 000$
• 1ドル \le k_i \le N$

서브태스크

노트

동작이 주어지기 전 논리식은 0&1&1|0|1|1&1 입니다. 각 동작 후 논리식과 대응되는 논리값은 다음과 같습니다.

1. 0&1&1|0|0|1&1: 대응되는 논리값이 1 입니다.
2. 0&0&1|0|0|1&1: 대응되는 논리값이 1 입니다.
3. 1&0&1|0|0|1&1: 대응되는 논리값이 1 입니다.
4. 1&0&1|0|0|0&1: 대응되는 논리값이 0 입니다.
5. 1&0&1|0|0|0&0: 대응되는 논리값이 0 입니다.
6. 1&1&1|0|0|0&0: 대응되는 논리값이 1 입니다.
7. 1&1&1|1|0|0&0: 대응되는 논리값이 1 입니다.