#include <bits/stdc++.h>
using namespace std;

int prime[100001] = {0};
int k[100001] = {0};

void Sieve() {
    for (int i = 1; i < 100001; i++)
        k[i] = i;

    for (int i = 2; i < 100001; i++) {
        if (prime[i] == 0) {
            for (int j = i; j < 100001; j += i) {
                prime[j] = 1;
                while (k[j] % (i * i) == 0)
                    k[j] /= (i * i);
            }
        }
    }
}

int countPairs(int arr[], int n) {
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        freq[k[arr[i]]]++;
    }

    int sum = 0;
    for (auto i : freq) {
        sum += ((i.second - 1) * i.second) / 2;
    }

    return sum;
}

#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
public:
    int n;
    vector<vector<int>> tree; 
    SegmentTree(const vector<int>& salaries) {
        n = salaries.size();
        tree.resize(4 * n);
        build(0, 0, n - 1, salaries);
    }
    void build(int node, int start, int end, const vector<int>& salaries) {
        if (start == end) {
            tree[node] = {salaries[start]};
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid, salaries);
            build(2 * node + 2, mid + 1, end, salaries);
       merge(tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
                  tree[2 * node + 2].begin(), tree[2 * node + 2].end(),
                  back_inserter(tree[node]));
        }
    }
    int query(int node, int start, int end, int L, int R, int x) {
        if (start > R || end < L) {
            return 0;
        }
        if (start >= L && end <= R) {
            return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), x);
        }
        int mid = (start + end) / 2;
        int left_result = query(2 * node + 1, start, mid, L, R, x);
        int right_result = query(2 * node + 2, mid + 1, end, L, R, x);
        return left_result + right_result;
    }
};

vector<int> solve(int N, vector<vector<int>> A, int Q, vector<vector<int>> queries) {
    vector<int> salaries(N);
    for (int i = 0; i < N; ++i) {
        salaries[i] = A[i][1];
    }
    SegmentTree segTree(salaries);
    vector<int> result;
    for (const auto& query : queries) {
        int L = query[0];
        int R = query[1];
        int x = query[2];
        L--; R--;
        result.push_back(segTree.query(0, 0, N - 1, L, R, x));
    }
    return result;
}

#include <iostream>
#include <vector>
using namespace std;
int firstMomentAllGreen(int N, int T, const vector<vector<int>>& A) {
    for (int t = 0; t < T; ++t) {
        bool allGreen = true;
                for (int i = 0; i < N; ++i) {
            if (A[i][t] == 0) {
                allGreen = false;
                break;
            }
        }
        
        if (allGreen) {
            return t;
        }
    }
    
    return -1; 
}