Background

CF站长发神经, 修改了反爬机制, 让ACjudge无法远程评测CF的题目了, 于是ACjudge管理员打算绑架CF站长

Description

现在我们把CF站长围在一个房间里, 这个角落有$n$条为狗爬出的洞口敞开着, 每个洞口可以通往$m$个房间中的任意一个, 现在有$q$次询问, 每次询问为当Acjudge管理员站在第$x$个房间的时候, CF站长有多少种跑路方式.

Format

Input

第一行三个整数$n, m, q$, 分别表示$n$个洞口, $m$个房间, $q$次询问

第二行$n$个整数, 每个整数表示这个洞口通往哪个房间

接下来$q$行, 每行一个整数$x$表示ACjudge管理员藏在哪个房间里抓$CF$的站长

Output

输出$q$行, 每行一个整数, 表示CF站长有多少种跑路方式.

Samples

5 2 2
1 2 2 1 2
1
2

3
2

Limitation

$1 <= n, m, q <= 10^5$