//「区間[l, r]をすべてtrueにする」「区間[l, r]がすべてtrueか判定する」
//→「区間に1を足す」「区間の最小値が1以上かを判定する」
//これはStarrySky木ですね。間違いない。なんだこれは…典型だなぁ…
//（StarySky木を自力で書いたことがないので、verify代わりに実装してみます）
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
using namespace std;

const int DEPTH = 17;
const int INF = 114514;

class StarrySky {
	int all[1 << (DEPTH + 1)];		//all[i] = ノードiと対応する区間に一様に足された値
	int part[1 << (DEPTH + 1)];		//part[i] = all[iの親, 祖先]を無視したときの, ノードiと対応する区間の最小値 (all[i]は反映する)
	
public:
	StarrySky() {
		for (int i = 0; i < (1 << (DEPTH + 1)); i++) {
			all[i] = part[i] = 0;
		}
	}
	
	//区間[l, r)にvを足す
	void add(int l, int r, int v, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (b <= l || a >= r) return;
		if (l <= a && b <= r) { all[id] += v; part[id] += v; return; }
		add(l, r, v, a, a + (b - a) / 2, id * 2 + 1);
		add(l, r, v, a + (b - a) / 2, b, id * 2 + 2);
		part[id] = min(part[id * 2 + 1], part[id * 2 + 2]) + all[id];
	}
	
	//区間[l, r)の最小値を求める
	int getMin(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (b <= l || a >= r) return INF;
		if (l <= a && b <= r) return part[id];
		int u = getMin(l, r, a, a + (b - a) / 2, id * 2 + 1);
		int v = getMin(l, r, a + (b - a) / 2, b, id * 2 + 2);
		return min(u, v) + all[id];
	}
};

typedef tuple<int, int, int, int, int> T;	//(time, type, l, r, ans_id), type=1:設置, type=0:移動
int n, m, q;
vector<T> query;
StarrySky seg;

signed main() {
	int i;
	
	cin >> n >> m >> q;
	for (i = 0; i < m; i++) {
		int d, a, b;
		cin >> d >> a >> b;
		query.push_back(T(d, 1, a, b, -1));
	}
	for (i = 0; i < q; i++) {
		int e, s, t;
		cin >> e >> s >> t;
		query.push_back(T(e, 0, s, t, i));
	}
	sort(query.begin(), query.end());
	
	static bool ans[100000];
	for (i = 0; i < query.size(); i++) {
		int type = get<1>(query[i]);
		int l = get<2>(query[i]);
		int r = get<3>(query[i]);
		int id = get<4>(query[i]);
		
		if (type == 1) seg.add(l, r, 1);
		if (type == 0) {
			ans[id] = (seg.getMin(l, r) >= 1);
		}
	}
	
	for (i = 0; i < q; i++) {
		if (ans[i]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

### Prompt

Generate a CPP solution to the following problem:

problem

AOR Co., Ltd. is a $ N $ story building. There is no basement floor.
AOR Ika-chan is a squid, so she can go down the stairs, but not up.

I decided to install $ M $ elevators in the building because it would be inconvenient if I couldn't climb upstairs.
It takes time to install the elevator, and the $ i $ th elevator will be installed the night after $ D_i $ and will be mobile on all floors above the $ A_i $ floor and below the $ B_i $ floor.

You were asked $ Q $ questions by AOR Ika-chan. The $ i $ th question is, "Can I move from the $ S_i $ floor to the $ T_i $ floor at noon $ E_i $ days later?"
The only means of transportation are stairs and elevators. In addition, the time required for movement shall be negligible.



input

$ N \ M \ Q $
$ D_1 \ A_1 \ B_1 $
$ \ vdots $
$ D_M \ A_M \ B_M $
$ E_1 \ S_1 \ T_1 $
$ \ vdots $
$ E_Q \ S_Q \ T_Q $

output

Print Yes or No on one line for each question. However, answer in the order in which they are asked. Also, output a line break at the end.

Example

Input

5 1 2
3 1 5
3 1 5
4 1 5


Output

No
Yes

### Response

```cpp
//「区間[l, r]をすべてtrueにする」「区間[l, r]がすべてtrueか判定する」
//→「区間に1を足す」「区間の最小値が1以上かを判定する」
//これはStarrySky木ですね。間違いない。なんだこれは…典型だなぁ…
//（StarySky木を自力で書いたことがないので、verify代わりに実装してみます）
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
using namespace std;

const int DEPTH = 17;
const int INF = 114514;

class StarrySky {
	int all[1 << (DEPTH + 1)];		//all[i] = ノードiと対応する区間に一様に足された値
	int part[1 << (DEPTH + 1)];		//part[i] = all[iの親, 祖先]を無視したときの, ノードiと対応する区間の最小値 (all[i]は反映する)
	
public:
	StarrySky() {
		for (int i = 0; i < (1 << (DEPTH + 1)); i++) {
			all[i] = part[i] = 0;
		}
	}
	
	//区間[l, r)にvを足す
	void add(int l, int r, int v, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (b <= l || a >= r) return;
		if (l <= a && b <= r) { all[id] += v; part[id] += v; return; }
		add(l, r, v, a, a + (b - a) / 2, id * 2 + 1);
		add(l, r, v, a + (b - a) / 2, b, id * 2 + 2);
		part[id] = min(part[id * 2 + 1], part[id * 2 + 2]) + all[id];
	}
	
	//区間[l, r)の最小値を求める
	int getMin(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (b <= l || a >= r) return INF;
		if (l <= a && b <= r) return part[id];
		int u = getMin(l, r, a, a + (b - a) / 2, id * 2 + 1);
		int v = getMin(l, r, a + (b - a) / 2, b, id * 2 + 2);
		return min(u, v) + all[id];
	}
};

typedef tuple<int, int, int, int, int> T;	//(time, type, l, r, ans_id), type=1:設置, type=0:移動
int n, m, q;
vector<T> query;
StarrySky seg;

signed main() {
	int i;
	
	cin >> n >> m >> q;
	for (i = 0; i < m; i++) {
		int d, a, b;
		cin >> d >> a >> b;
		query.push_back(T(d, 1, a, b, -1));
	}
	for (i = 0; i < q; i++) {
		int e, s, t;
		cin >> e >> s >> t;
		query.push_back(T(e, 0, s, t, i));
	}
	sort(query.begin(), query.end());
	
	static bool ans[100000];
	for (i = 0; i < query.size(); i++) {
		int type = get<1>(query[i]);
		int l = get<2>(query[i]);
		int r = get<3>(query[i]);
		int id = get<4>(query[i]);
		
		if (type == 1) seg.add(l, r, 1);
		if (type == 0) {
			ans[id] = (seg.getMin(l, r) >= 1);
		}
	}
	
	for (i = 0; i < q; i++) {
		if (ans[i]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

```