KTH_INDEX - Solution to all the problems


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 Kth 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 Kth occurrence of P in L to R.

Print -1 if no such index exists.

Constraints

2 ≤ N, Q ≤ 105

1 ≤ Ai ≤ 106

1 ≤ L < R ≤ N

1 ≤ P ≤ 106

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

hide comments
shoaib_ali_34: 2022-01-08 14:45:38

i SOLVED this in O(n) in java , its giving TLE.

Waseem Ahmed: 2021-09-23 14:24:15

Nice problem. A little thinking needed about the appropriate data structures to use. That's all.

Jean-Ralph Aviles: 2021-08-29 16:36:13

Time limits are VERY tight. I had to micro-optimize a O(q*log(n) + n) solution for it to AC.

sahil_19: 2020-05-21 05:20:39

I am using linear search but getting TLE

[Lakshman]: 2020-02-10 20:43:09

@sahil1422 My Solution is not a brute force rather its a badly written Java code. I think need to check my CPP version.

A small change in code got AC.

Last edit: 2020-02-12 18:13:12
sahil1422: 2020-02-10 07:25:28

Yes, I changed the test data after a week so as to stop the brute solutions. I realised later that brute solutions are getting AC. Sorry for the inconvenience caused.

nadstratosfer: 2020-02-05 23:48:15

Lakshman, I just resubmitted my 0.16s solution that originally got AC on the day of publication, and it came in at 0.15s.

[Lakshman]: 2020-02-05 12:10:46

@Problem setter Did you change the Test data set ? Because my earlier accepted solution got TLE. Its no a good idea to update the test date after problem is publish . I did not see any warning or comment from you.

:D: 2019-11-21 13:27:55

Great problem. it's easy but fun and, as such, a great entry point for people new to query problems.

sriram_21: 2019-11-19 14:20:35

Good problem constraints made it possible for me!!!


Added by:Sahil
Date:2019-11-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All