Given an array $A$ of $n$ integers. Your task is to process $q$ queries of the form $(l,r)$, find a value occuring exactly one time in the subarray $A_l,A_{l+1},...,A_r$.
### Input
- The first line contains two integers $n,q$.
- The second line contains $n$ integer $A_i$.
- The next $q$ lines, each line contains two integer $l,r$, a query.
### Output
- For each query, print the value occuring exactly in the given subarray. If there are multiple value, print any. If there are no satisfied value, print `0`.
### Constraints
- $1 \le n, q \le 2 \times 10^5$.
- $1 \le A_i \le 2 \times 10^5$.
- $1 \le l \le r \le n$.
### Example
Input:
```
6 2
1 1 2 3 2 4
2 6
1 2
```
Output:
```
4
0
```
