One of the main tasks of an operating system is process scheduling, i.e., managing CPU sharing among a community of ready processes. Several algorithms exist for scheduling tasks to the CPU. Here we are considering Round Robin Scheduling(in a single CPU system) which is the most widely used of all the scheduling algorithms.

Round Robin works with a timer interrupt which is set to occur after specific time intervals. Suppose there are n processes which need the CPU. Each process has a specific run time(amount of CPU time it needs to complete the process). Initially CPU is allocated to the first process. It stays on CPU till the timer interrupt occurs or till the process is complete, whichever happens first. Then CPU is allocated to the next task, which stays there till the next timer interrupt. This goes on till all n tasks get the CPU. After all n tasks the cycle is repeated again. This continues till all the processes are over.

Your task is to answer queries of two kind as described in input section.

Input:

First line contains two integers N (1<=N<=100000), the no. of processes and C (1<=C<=10000), cycle length(interval after which each interrupt occurs).

The next line contains N integers, with ith line containing the run time of process indexed i(1<=A[i]<=1000000000). Indexing is 1-based.

The next line contains integer Q (1<=Q<=100000), denoting the number of queries on this data. Each of the next Q lines contain two space-separated integers M (1 or 2) and D (1<=D<=N). M indicates the mode of query.

1) 1 D 2) 2 D

where: M=1, for wait time of process D, i.e., how much time it has to wait before getting CPU for the first time.

M=2, for rank of process D when finished, e.g., if process D is 5th to get completed, then output 5.

Output:

There should be one line of input for each query.

If M=1, output the wait time of each process, which is the time from the start till the process with index D first gets the CPU.

If M=2, output an integer k, where process D was the kth process to get finished(see sample input for a better understanding).