Migrated from Lutece 3036 Line Coverage Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a number line whose range is on the closed interval $[1,N]$. For each query, a closed interval $[X,Y]$ on the number line is given, and you need to completely cover $[X,Y]$ with the minimum number of line segments.

Given $M$ conditions, the line segment you use must satisfy at least one of these $M$ conditions (note: not all must be satisfied). Among them, the $i$-th constraint is in the form of a closed interval $[L_i,R_i]$ and a positive integer $K_i$, which means:

• The line segment $[l,r]$ you use needs to be completely within $[L_i,R_i]$, that is, $L_i\le l<r\le R_i$;
• The length of the line segment $[l,r]$ you use cannot exceed $K_i$, which is $r-l\le K_i$.

For each query, you should calculate the minimum number of line segments required to completely cover the given closed interval. Ultimately, you need to output the XOR sum of all the answers asked.

The data guarantees that there is no position on the entire number line that cannot be covered.

$\text{}$

Please note:

• In all the above expressions of the form "closed interval $[S,T]$", $S$ and $T$ represent the endpoints on the number axis, not the area of unit length;
• "Complete coverage" means to cover every position of the interval, not just integer points.

For example, assuming that the closed interval $[1,4]$ is to be covered now, it is illegal to cover the entire interval with line segments $[1,2]$ and $[3,4]$, because the open interval $(2,3)$ is not covered.

Any position on the number line can be covered multiple times. A closed interval is completely covered if and only if any position in the closed interval is covered at least $1$ times.

Input

The content of each query is given by a random generator, please read the instructions in the Note section below.

The first line contains four integers $N, M, Q, S$, respectively representing the size of the number axis, the number of conditions, the number of queries, and the seed of the random generator;

Then $M$ line follows, where line $i+1$ contains three integers $L_i,R_i,K_i$, representing the content of the $i$-th limit.

Output

Output an integer on one line representing the XOR sum of all queried answers.

Samples

7 2 1 24
1 4 2
3 7 3

3

Note

Example Explanation

The query interval generated by the random generator is $[1,7]$.

At least $3$ line segments are required to cover this interval. The $3$ line segments used by one of the optimal schemes are:

1. $[1,3]$, which meets the $1$-st condition;
2. $[3,4]$, which also meets the $1$-st condition;
3. $[4,7]$, which meets the $2$-nd condition.

Constraints

$1\le N\le 2\times 10^6$

$1\le M\le 10^5$

$1\le Q\le 2\times 10^6$

$0\le S\le 2^{31}-1$

$1\le L_i<R_i\le N$

$1\le K_i\le R_i-L_i$

$1\le X<Y\le N$

Random Generator

The random generator code is as follows (please copy it into your own code):

// Please include these header files
#include <iostream>
#include <utility>
using namespace std;

// The body of the generator
namespace RD{
    static unsigned long long splitmix64(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    unsigned long long n, s;
    void init(int N, int S){
        n = N - 1, s = S;
    }
    pair<int, int> getquery(){
        s = splitmix64(s);
        int l = s % n;
        s = splitmix64(s);
        int r = s % n;
        if(l > r)
            swap(l, r);
        return pair<int, int>(l + 1, r + 2);
    }
}

After you have read all the data, please call the function RD::init(N, S) to initialize the random generator;

Then, for each query, you need to call the function RD::getquery() to get the content of the current query, which returns the query range as a pair<int, int> type variable. pair<int, int> has two members of type int, namely first and second, where the value of first is the left endpoint $X$ of the interval, and the value of second is the right endpoint $Y$ of the interval.

The following is a demonstration of how to use it (applicable to C++ 17 and above standards):

int main(){
    int n, m, q, s;
    ... // Read in n, m, q, s, ...
    RD::init(n, s); // Initialize the generator
    while(q--){
        auto [x, y] = RD::getquery();
        // [x, y] is the interval of the current query
    }
}

If your compiler does not support C++ 17, you can also refer to the following examples:

int main(){
    int n, m, q, s;
    ... // Read in n, m, q, s, ...
    RD::init(n, s); // Initialize the generator
    while(q--){
        pair<int, int> nd = RD::getquery();
        int x = nd.first;
        int y = nd.second;
        // [x, y] is the interval of the current query
    }
}