People have been coming to the wise man, complaining about the same problems every time.

One day he told them a joke and everyone roared in laughter.

After a couple of minutes, he told them the same joke and only a few of them smiled.

When he told the same joke for the third time no one laughed.

The wise man smiled and said:

"You can't laugh at the same joke over and over. So why are you always crying about the same problem?"

He has also created a very simple game to cheer the people up. The game is as follows:

You are given a sequence A of N integers.

The task is to answer Q queries on the given sequence. For each query, you will be given four space-separated integers L, R, P, K.

Print the index of K^th occurrence of P in L to R(inclusive). If no such index exists, print -1.

Input

The first line contains two space-separated integers N and Q.

The second line contains N space-separated integers. (1-based indexing)

Following Q lines contain,

Four integers L, R, P, K.

Output

For each query, print a single line containing one integer between 1 to N i.e. index of the K^th occurrence of P in L to R.

Print -1 if no such index exists.

Constraints

2 ≤ N, Q ≤ 10⁵

1 ≤ A_i ≤ 10⁶

1 ≤ L < R ≤ N

1 ≤ P ≤ 10⁶

1 ≤ K ≤ N

Example

Input:
10 3
1 1 2 1 2 3 1 2 3 4
1 10 2 3
1 5 2 3
5 9 3 2

Output:
8
-1
9