Ryhmät

//////// From bqi343

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! //

// pairs
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second

#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)

const int MOD = (int)1e9+7; // 998244353;
const int MX = (int)2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
	return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; } // set a = max(a,b)

tcTU> T fstTrue(T lo, T hi, U f) {
	++hi; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	--lo; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
	auto it = t.find(u); assert(it != end(t));
	t.erase(it); } // element that doesn't exist from (multi)set


/**
 * Description: point update and rectangle sum with offline 2D BIT. 
	* For each of the points to be updated, $x\in (0,SZ)$ and $y\neq 0$.
 * Time: O(N\log^2 N)
 * Memory: O(N\log N)
 * Source: Own
 * Verification: 
 	* https://dmoj.ca/problem/occ19g4
 	* http://www.usaco.org/index.php?page=viewproblem2&cpid=722 (753 ms)
 	* http://www.usaco.org/index.php?page=viewproblem2&cpid=601 (679 ms)
 */

template<class T, int SZ> struct OffBIT2D { 
	bool mode = 0; // mode = 1 -> initialized
	vpi todo; // locations of updates to process
	int cnt[SZ], st[SZ];
	vi val; vector<T> bit; // store all BITs in single vector
	void init() { assert(!mode); mode = 1;
		int lst[SZ]; F0R(i,SZ) lst[i] = cnt[i] = 0;
		sort(all(todo),[](const pi& a, const pi& b) { 
			return a.s < b.s; });
		each(t,todo) for (int x = t.f; x < SZ; x += x&-x) 
			if (lst[x] != t.s) lst[x] = t.s, cnt[x] ++;
		int sum = 0; F0R(i,SZ) lst[i] = 0, st[i] = (sum += cnt[i]);
		val.rsz(sum); bit.rsz(sum); reverse(all(todo));
		each(t,todo) for (int x = t.f; x < SZ; x += x&-x) 
			if (lst[x] != t.s) lst[x] = t.s, val[--st[x]] = t.s;
	}
	int rank(int y, int l, int r) {
		return ub(begin(val)+l,begin(val)+r,y)-begin(val)-l; }
	void UPD(int x, int y, T t) {
		for (y = rank(y,st[x],st[x]+cnt[x]); y <= cnt[x]; y += y&-y) 
			bit[st[x]+y-1] += t; }
	void upd(int x, int y, T t) { 
		if (!mode) todo.pb({x,y});
		else for (;x<SZ;x+=x&-x) UPD(x,y,t); }
	int QUERY(int x, int y) { T res = 0;
		for (y = rank(y,st[x],st[x]+cnt[x]); y; y -= y&-y) res += bit[st[x]+y-1];
		return res; }
	T query(int x, int y) { assert(mode);
		T res = 0; for (;x;x-=x&-x) res += QUERY(x,y);
		return res; }
	T query(int xl, int xr, int yl, int yr) { 
		return query(xr,yr)-query(xl-1,yr)
			-query(xr,yl-1)+query(xl-1,yl-1); }
};

int maxnum = 0;


void test(OffBIT2D<int, 100000>& Ta){
    int m;
    cin >> m;
    multiset<int> s;
    for (int i=1; i<=m; ++i){
        int c;
        cin >> c;
        s.insert(c);
    }
    vector<pair<pair<int, int>, pair<int, int>>> v;
    int prev_u = 0;
    for (auto u:s){
        int ch_needed = u;
        if (u > prev_u){ 
            v.push_back({{prev_u+1, u}, {u, 0}});
            prev_u = u;
        }
        while (ch_needed){
            //for (auto u1:v) cout << u1.f.f << " " << u1.f.s << " " << u1.s << "\n";
            //cout << "here " << u << " " << ch_needed << " " << maxnum << "\n";
            if (v.size()==0){
                cout << "NO\n";
                return;
            }
            int k = v.size();
            int a1 = v[k-1].f.f, b1 = v[k-1].f.s, c1 = v[k-1].s.f, d1 = v[k-1].s.s;
            // [a, b]: start interval, c: first ending point, d : how many of those ending at c or later already used.
            
            if (k == 1){
                int cnt = Ta.query(1, u, c1, maxnum);
                if (cnt-d1 < ch_needed){
                    cout << "NO\n";
                    return;
                }
                else {
                    v.pop_back();
                    v.push_back({{1, u}, {c1, d1 + ch_needed}});
                    ch_needed = 0;
                }
                continue;
            }
            // k >= 2
            int a2 = v[k-2].f.f, b2 = v[k-2].f.s, c2 = v[k-2].s.f, d2 = v[k-2].s.s;
            
            // If we have went past the first ending point of the previous group, we merge directly.
            if (c1 >= c2){
                v.pop_back();
                v.pop_back();
                // We need to check whether we have assigned all the children in between preferences.
                int cnt = Ta.query(a2, b2, c2, c1); 
                int used_of_last = Ta.query(a2, b2, c1, c1);
                if (cnt - used_of_last >= d2) {
                    v.push_back({{a2, b1}, {c1, d1}});
                }
                else v.push_back({{a2, b1}, {c1, d1 + d2 - (cnt - used_of_last)}});
                continue;
            }
            
            // Now we can assume c2 > c1 
            int cnt = Ta.query(a1, b1, c1, c2); // b1 should be u but we can use this 
            if (cnt-d1 < ch_needed){
                // Last group alone isn't enough, so we merge it with the previous one.
                v.pop_back();
                v.pop_back();
                if (cnt < d1){  // Not sure if this case is possible
                    int used_of_last = Ta.query(a1, b1, c2, c2);
                    v.push_back({{a2, b1}, {c2, d2 + d1 - cnt + used_of_last}});
                }
                else{
                    // Here cnt >= d1 so possible some children go unassigned, and we can forget about d1.
                    ch_needed -= cnt-d1;
                    int used_of_last = Ta.query(a1, b1, c2, c2);
                    v.push_back({{a2, b1}, {c2, d2 + used_of_last}});
                }
            }
            else {
                // Last group suffices.
                v.pop_back();
                v.push_back({{a1, b1}, {c1, d1 + ch_needed}});
                ch_needed = 0;
            }
        }
    }
    cout << "YES\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    OffBIT2D<int, 100000> Ta;
    int n, t;
    cin >> n >> t;
    int a[n+1]={}, b[n+1]={};
    for (int i=1; i<=n; ++i){
        cin >> a[i] >> b[i];
        Ta.upd(a[i], b[i], 0);
        maxnum = max(maxnum, a[i]);
        maxnum = max(maxnum, b[i]);
    }
    Ta.init();
    for (int i=1; i<=n; ++i){
        Ta.upd(a[i], b[i], 1);
    }
    for (int i=0; i<t; ++i){
        test(Ta);
    }
}







/*

Käy ryhmätoiveet läpi suuruusjärjestyksessä.
Pidä yllä listaa, joka kertoo, aiemmat päättymiskohdat. Esim: 
- Niistä, joilla aloitus viimeistään kohdassa 5, on jäljellä ne, joilla lopetus vähintään kohdassa 20
- 6- 8: lopetus väh. kohd. 15.
- 9 - 12: Lopetus väh. kohd. 25.

Jos ollaan kohdassa 14, niin käytetään ensin toisen ryhmän tyyppejä, kunnes jäljellä olevilla niillä on lopetus vähintään kohdassa 20. 
Sitten yhdistetään eka ja toka ryhmä porukaksi, jolla aloitus viim. kohdassa 8 ja lopetus väh. kohdassa 20. 
Voidaan itse asiassa yhdistää vielä seuraavaan ryhmään, koska sitä ei ole vielä käytetty, ja saadaan ryhmä "aloitus viim. 12, lopetus väh. 20".
Eli ryhmiä voidaan järjestää niin, että "viim"-kohdat kasvavat ja "väh"-kohdat pienenevät (jos viim isompi ja väh isompi, voidaan yhdistää edellisen kanssa samaan)

Eli olisi hyvä, jos olisi nopea tapa hakea, kuinka monta lasta on esim. joukossa "aloitus 6 - 8, lopetus 15 tai myöhemmin".

*/

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED