Task

Simulate a consistent hashing ring with k servers and n virtual nodes per server. Place each server s (0-indexed) at ring positions s, s+k, s+2k, ..., s+(n-1)k on a ring of total size kn. For each query key, map it to ring position key % (k*n), then assign it to the server whose virtual node has the smallest position that is >= the key's ring position (wrapping to position 0 if none exists).

Input

• Line 1: k n — number of servers, number of virtual nodes per server
• Line 2: q — number of queries
• Lines 3 to q+2: one integer key per line

Output

Print the server index (0-indexed) for each query, one per line.

Example

Input:

3 2
3
0
1
2

Output:

0
1
2

Scaffolding

Submit a Python file defining:

def consistent_hash_queries(k_servers: int, n_vnodes: int,
                            keys: list[int]) -> list[int]:
    ...

Receives the number of servers, virtual nodes per server, and a list of integer keys; returns a list of server indices, one per key.