Though Rujia Liu usually sets hard problems for contests (for example, regional contests like Xi'an 2006, Beijing 2007 and Wuhan 2009, or UVa OJ contests like Rujia Liu's Presents 1 and 2), he occasionally sets easy problem (for example, 'the Coco-Cola Store' in UVa OJ), to encourage more people to solve his problems :D
Given an array, your task is to find the k-th occurrence (from left to right) of an integer v. To make the problem more difficult (and interesting!), you'll have to answer m such queries.
Input
There are several test cases. The first line of each test case contains two integers n, m(1<=n,m<=100,000), the number of elements in the array, and the number of queries. The next line contains n positive integers not larger than 1,000,000. Each of the following m lines contains two integer k and v (1<=k<=n, 1<=v<=1,000,000). The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.
Output
For each query, print the 1-based location of the occurrence. If there is no such element, output 0 instead.
Sample Input
8 4
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2
Output for the Sample Input
2
0
7
0
/*
* Author: Joshua
* Created Time: 2014年07月10日 星期四 14时23分15秒
* File Name: uva11991.cpp
*/
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
int n,m;
map <int ,vector <int> > a; int main()
{
int x,y;
while (scanf("%d%d",&n,&m)==2)
{
a.clear();
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
if (a.count(x)==0) a[x] = vector<int>();
a[x].push_back(i);
}
while (m--)
{
scanf("%d%d",&x,&y);
if (a.count(y) == 0 || a[y].size()<x ) printf("0\n");
else printf("%d\n",a[y][x-1]);
}
}
return 0;
}