Interview

Time limit1sMemory limit1024 MB

Summary

For each query X, count the contiguous groups of students among the first X that contain no student in Eunho's grade.

Level: Easy3 of 10
Topics: Array, Prefix sum, Math
Solved: No attempts yet

Problem

The cafeteria line at Seoul Science High School is long. Eunho wants to interview some students who stand in consecutive positions in the line. However, students in the same grade as Eunho cannot be interviewed.

Currently $N$ students are standing in the line. Eunho wonders how many ways he can conduct an interview. Answer the $Q$ queries below to satisfy his curiosity.

When interviewing several consecutive students among the first $X_i$ students, how many ways are there to choose them so that no student in the same grade as Eunho is included?

Input

The first line contains the number of students $N$ , Eunho's grade $K$ , and the number of queries $Q$ , separated by spaces. The second line contains the grades $A_1, A_2, \cdots, A_N$ of the students in the line, separated by spaces. Student $i$ is the one standing $i$ -th from the front. The third line contains the integers $X_1, X_2, \cdots, X_Q$ , separated by spaces.

Output

For each query, print the number of possible interview choices on its own line.

Constraints

$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$

Examples1

Example 1
Input
```
5 2 5
1 2 3 1 2
1 2 3 4 5
```
Expected output
```
1
1
2
4
4
```