Description

Given a sequence A = a₁, a₂, ..., a_N.

However, for any a_i ≠ a_j, a_i hates a_j and a_j hates a_i. Two distinct elements don't want to be together.

You are given Q queries.

In each query, you are given L_i, R_i, and X_i. You have to find the number of elements needed to be removed to make A[L_i...R_i] contain X_i only.

It is guaranteed for each i = 1, 2, ..., Q - 1, L_i ≤ L_i+1 and R_i ≤ R_i+1.

 

For example, if A = [1, 3, 2, 3, 3] and L = 1, R = 5, and X = 3.

Then you have to remove A[1] and A[3] to make A contain 3 only.

Hence, the number of elements needed to be removed is 2 in this example.

 

It is recommended to include<stdio.h> and use scanf/printf instead of cin/cout to speed up input and output.

You may need to select c++11, c++14, c++17 as the compiler to avoid compile error.

 

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains two integers N Q, the length of A and the number of queries.

The second line of each testcase contains N integers, a₁, a₂, ..., a_N.

The next Q lines contains three integers L_i, R_i, and X_i as described in the statement.

 

For each test,

1. N ≤ 100, Q ≤ 100
2. N ≤ 100, Q ≤ 100
3. N ≤ 1000, Q ≤ 1000
4. N ≤ 1000, Q ≤ 1000
5. N ≤ 200000, Q ≤ 100000
6. N ≤ 200000, Q ≤ 100000

T ≤ 10, 1 ≤ a_i ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ N, 1 ≤ X_i ≤ 10⁹.

 

 

Output

For each query in each testcase, please print the number of elements needed to be removed to make A[L_i...R_i] contain X_i only.

You have to print an extra new line at the end of each testcase, including the last one.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss