27914번 - 인터뷰 서브태스크

서울과학고의 급식실은 줄이 깁니다. 은호는 줄을 선 사람들 중 연속한 위치에 있는 몇 명을 골라 인터뷰를 하려고 합니다. 단, 은호와 같은 학년의 학생은 인터뷰를 할 수 없습니다.

현재 급식실에는 $N$명의 학생이 줄을 서 있습니다. 은호는 문득 자신이 인터뷰를 할 수 있는 방법이 몇 가지나 될지 궁금해졌습니다. 다음과 같은 $Q$개의 질문에 답해 은호의 궁금증을 풀어 줍시다.

• 앞 $X_i$명의 학생들 중 연속한 몇 명을 골라 인터뷰를 할 때, 자신과 같은 학년의 학생이 한 명도 없도록 고르는 방법의 수는 몇 가지인가?

첫 줄에 학생의 수 $N$과 은호의 학년을 나타내는 정수 $K$, 그리고 질문의 수 $Q$가 주어집니다. 둘째 줄에 줄을 서 있는 학생들의 학년 $A_1$, $A_2$, $\cdots$, $A_N$이 띄어쓰기를 사이에 두고 주어집니다. $i$번 학생은 앞에서부터 $i$번째에 서 있는 학생을 말합니다. 셋째 줄에 $Q$개의 질문에 대한 정수 $X_1$, $X_2$, $\cdots$, $X_Q$가 띄어쓰기를 사이에 두고 주어집니다.

각 경우에 대해 가능한 인터뷰 대상의 가짓수를 한 줄에 하나씩 출력합니다.

• $1 \le N \le 10^5$
• $1 \le K \le 3$
• $1 \le Q \le N$
• $1 \le A_i \le 3$ ($1 \le i \le N$)
• $1 \le X_1 < \cdots < X_Q \le N$