#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

const string T = "abacaba";

int count(const string& s) {
    int cnt = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        if (s.substr(i, T.size()) == T) {
            ++cnt;
        }
    }

    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    for (int tt = 1; tt <= t; ++tt) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        bool F = false;

        for (int i = 0; i + T.size() <= n; ++i) {
            string ss = s;
            bool ok = true;
            for (int j = 0; j < T.size(); j++) {
                if (ss[i + j] != '?' && ss[i + j] != T[j]) {
                    ok = false;
                    break;
                }
                ss[i + j] = T[j];
            }
            if (ok && count(ss) == 1) {
                for (int j = 0; j < n; j++) {
                    if (ss[j] == '?') {
                        ss[j] = 'd';
                    }
                }
                F = true;
                cout << "Yes\n";
                cout << ss << "\n";
                break;
            }
        }
        if (!F) {
            cout << "No\n";
        }
    }

    return 0;
}

#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

vector<ll> gao(vector<int> a) {
    int n = a.size();
    vector<ll> res(n + 1);
    int i = 0;
    while (i < n) {
        if (a[i] == 0) {
            i++;
            continue;
        }

        int j = i;
        while (j < n && a[j] == 1) {
            j++;
        }
        for (int len = 1; len <= j - i; len++) {
            res[len] += j - i - len + 1;
        }
        i = j;
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    ll k;
    cin >> n >> m >> k;
    vector<int> a(n);
    vector<int> b(m);
    for (int& x : a) {
        cin >> x;
    }
    for (int& x : b) {
        cin >> x;
    }

    ll ans = 0;

    auto ga = gao(a);
    auto gb = gao(b);
    for (int i = 1; i < ga.size(); i++) {
        if (k % i == 0 && k / i <= m) {
            ans += ga[i] * gb[k / i];
        }
    }

    cout << ans << "\n";
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 1005;

int n, x, sad;
int64 answer;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d %d\n", &n, &x);

	answer = x;
	sad = 0;

	int cur;
	char type;
	for (int i = 0; i < n; ++i)
	{
		scanf("%c %d\n", &type, &cur);
		if (type == '+')
		{
			answer += cur;
		}
		else if (answer >= cur)
		{
			answer -= cur;
		}
		else
		{
		    ++sad;
		}
	}

	cout << answer << " " << sad << "\n";

	fclose(stdin);
	fclose(stdout);

	return 0;
}

import sys

def main():
    n, answer = map(int, sys.stdin.readline().split())
    sad = 0

    for i in range(n):
        type_of, cur = sys.stdin.readline().split()
        cur = int(cur)
        if type_of == "+":
            answer += cur
        elif answer >= cur:
            answer -= cur
        else:
            sad += 1

    sys.stdout.write(str(answer) + " " + str(sad))

main()

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 105;

int n;
int arr[MAX_N];

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d", &n);

	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &arr[i]);
	}

	for (int i = n - 1; i > 0; --i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				printf("%d %d\n", j + 1, j + 2);
			}
		}
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}

n = int(input())
arr = list(map(int, input().split()))

for i in range(n - 1, 0, -1):
    for j in range(i):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            print(j + 1, j + 2)

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n, m;
    cin >> n >> m;

    size_t len1 = 1, len2 = 1;
    for (size_t a = 7; a < n; a *= 7)
        len1 += 1;
    for (size_t b = 7; b < m; b *= 7)
        len2 += 1;

    size_t ans = 0;
    if (len1 + len2 <= 7)
        for (size_t i = 0; i != n; ++i)
            for (size_t j = 0; j != m; ++j) {
                vector<size_t> used(7, 0);
                
                for (size_t a = i, k = 0; k != len1; a /= 7, ++k)
                    used[a % 7] += 1;
                for (size_t b = j, k = 0; k != len2; b /= 7, ++k)
                    used[b % 7] += 1;
                
                if (*std::max_element(used.begin(), used.end()) <= 1)
                    ++ans;
            }
    
    cout << ans << "\n";
    
    return 0;
}

BASE = 7

def itov(x):
    digits = []
    if x == 0:
        digits.append(0)
    while x > 0:
        digits.append(x % BASE)
        x //= BASE
    digits.reverse()
    return digits

def gen(pos = 0, minute = False, smaller = False):
    max_val = max_minute if minute else max_hour
    if pos >= len(max_val):
        if minute:
            return 1
        else:
            return gen(0, True)
    else:
        ans = 0
        for digit in range(BASE):
            if not used[digit] and (smaller or digit <= max_val[pos]):
                used[digit] = True
                ans += gen(pos + 1, minute, smaller or digit < max_val[pos])
                used[digit] = False
        return ans

n, m = map(int, input().split())
n -= 1
m -= 1
used = [False] * BASE
max_hour = itov(n)
max_minute = itov(m)
print(gen())

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

const size_t MAXN = (1 << 19);
vector<size_t> graph[MAXN];

vector<pair<size_t, size_t>> segm[2 * MAXN - 1];

#define time TIME_FUCKLIBC

pair<size_t, size_t> times[MAXN];
size_t time = 0;

size_t sizes[MAXN];

void dfs(size_t v) {
    size_t sz = 1;
    
    times[v].first = time++;

    for (size_t u: graph[v]) {
        dfs(u);
        sz += sizes[u];
    }
    
    times[v].second = time;
    segm[MAXN - 1 + times[v].first].emplace_back(sz, v);
    
    sizes[v] = sz;
}

void buildseg(size_t node, size_t L, size_t R) {
    if (L != R - 1) {
        size_t mid = L + (R - L) / 2;
        buildseg(2 * node + 1, L, mid);
        buildseg(2 * node + 2, mid, R);
        
        segm[node].resize(segm[2 * node + 1].size() + segm[2 * node + 2].size());
        std::merge(segm[2 * node + 1].begin(), segm[2 * node + 1].end(), segm[2 * node + 2].begin(), segm[2 * node + 2].end(), segm[node].begin());
    }
}

pair<size_t, size_t> lowerb(size_t node, size_t L, size_t R, size_t rl, size_t rr, pair<size_t, size_t> minval) {
    if (rl <= L and R <= rr) {
        auto it = std::lower_bound(segm[node].begin(), segm[node].end(), minval);
        if (it == segm[node].end())
            return make_pair(SIZE_MAX, SIZE_MAX);
        else
            return *it;
    }
    if (R <= rl or rr <= L)
        return make_pair(SIZE_MAX, SIZE_MAX);

    size_t mid = L + (R - L) / 2;
    return min(lowerb(2 * node + 1, L, mid, rl, rr, minval)
              ,lowerb(2 * node + 2, mid, R, rl, rr, minval));
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n, q;
    cin >> n >> q;
    
    for (size_t i = 1; i != n; ++i)
        graph[input<size_t>() - 1].push_back(i);

    dfs(0);
    buildseg(0, 0, MAXN);
    
    for (size_t i = 0; i != q; ++i) {
        size_t v = input<size_t>() - 1;
        cout << lowerb(0, 0, MAXN, times[v].first, times[v].second, make_pair((sizes[v] + 1) / 2, 0)).second + 1 << "\n";
    }
    
    return 0;
}

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

set<pair<size_t, size_t>> solve(const vector<vector<size_t>>& graph, vector<size_t>& ans, size_t v) {
    set<pair<size_t, size_t>> cur;

    for (size_t u: graph[v]) {
        auto ch = solve(graph, ans, u);
        if (not (ch.size() < cur.size()))
            std::swap(ch, cur);
        
        for (auto elem: ch)
            cur.insert(elem);
    }

    size_t sz = cur.size() + 1;
    cur.emplace(sz, v);

    ans[v] = cur.lower_bound(make_pair((sz + 1) / 2, 0))->second;
    
    return std::move(cur);
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n, q;
    cin >> n >> q;
    
    vector<vector<size_t>> graph(n);
    for (size_t i = 1; i != n; ++i)
        graph[input<size_t>() - 1].push_back(i);

    vector<size_t> ans(n, SIZE_MAX);

    solve(graph, ans, 0);
    
    for (size_t i = 0; i != q; ++i)
        cout << ans[input<size_t>() - 1] + 1 << "\n";
    
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 300 * 1000 + 5;
const int MAX_Q = 300 * 1000 + 5;

int n, q;
vector<int> graph[MAX_N];
int size_of[MAX_N];
int prev_of[MAX_N];
int big_subtree[MAX_N];
int centroid[MAX_N];

bool is_centroid_of_subtree(int v, int c)
{
	return ((size_of[v] - size_of[c]) * 2 <= size_of[v] && big_subtree[c] * 2 <= size_of[v]);
}

void dfs_calc(int v, int p)
{
	big_subtree[v] = 0;
	size_of[v] = 1;
	prev_of[v] = p;

	for (int i = 0; i < graph[v].size(); ++i)
	{
		dfs_calc(graph[v][i], v);
		size_of[v] += size_of[graph[v][i]];
		big_subtree[v] = max(big_subtree[v], size_of[graph[v][i]]);
	}
}

void dfs_centroid(int v)
{
	if (size_of[v] == 1)
	{
		centroid[v] = v;
	}
	else
	{
		int ptr = 0;
		for (int i = 0; i < graph[v].size(); ++i)
		{
			dfs_centroid(graph[v][i]);
			if (size_of[graph[v][ptr]] < size_of[graph[v][i]])
			{
				ptr = i;
			}
		}

		int c = centroid[graph[v][ptr]];

		while (!is_centroid_of_subtree(v, c))
		{
			c = prev_of[c];
		}

		centroid[v] = c;
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d %d", &n, &q);

	int v;
	for (int i = 0; i < n - 1; ++i)
	{
		scanf("%d", &v);
		graph[v - 1].push_back(i + 1);
	}

	dfs_calc(0, 0);
	dfs_centroid(0);

	for (int i = 0; i < q; ++i)
	{
		scanf("%d", &v);
		printf("%d\n", centroid[v - 1] + 1);
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

struct coord {
    int64_t x;
    int64_t y;
    int64_t z;
};

struct equation {
    pair<int64_t, int64_t> S;
    pair<int64_t, int64_t> a;
    pair<int64_t, int64_t> b;
    pair<int64_t, int64_t> c;
};

vector<coord> list;

equation operator+(const equation& e1, const equation& e2) {
    equation res;
    res.S = {max(e1.S.first, e2.S.first), min(e1.S.second, e2.S.second)};
    res.a = {max(e1.a.first, e2.a.first), min(e1.a.second, e2.a.second)};
    res.b = {max(e1.b.first, e2.b.first), min(e1.b.second, e2.b.second)};
    res.c = {max(e1.c.first, e2.c.first), min(e1.c.second, e2.c.second)};
    return res;
}

coord get_solution(const equation& eq) {
    if ((eq.S.first > eq.S.second)
     or (eq.a.first > eq.a.second)
     or (eq.b.first > eq.b.second)
     or (eq.c.first > eq.c.second))
        return coord {INT64_MAX, INT64_MAX, INT64_MAX};
        
     if ((eq.a.first + eq.b.first + eq.c.first > eq.S.second)
     or (eq.a.second + eq.b.second + eq.c.second < eq.S.first))
        return coord {INT64_MAX, INT64_MAX, INT64_MAX};

     coord res;
     res.x = eq.a.first;
     res.y = eq.b.first;
     res.z = eq.c.first;
     int64_t delta = max(int64_t(0), eq.S.first - res.x - res.y - res.z);

     res.x += min(delta, eq.a.second - eq.a.first);
     delta -= min(delta, eq.a.second - eq.a.first);
     res.y += min(delta, eq.b.second - eq.b.first);
     delta -= min(delta, eq.b.second - eq.b.first);
     res.z += min(delta, eq.c.second - eq.c.first);
     delta -= min(delta, eq.c.second - eq.c.first);

     assert(delta == 0);
     
     return res;
}

int64_t DIV2(int64_t arg) {
    return (arg - (arg & 1)) / 2;
}

coord can(int64_t MAXANS) {
    equation eq;
    eq.S = eq.a = eq.b = eq.c = {INT64_MIN, INT64_MAX};
    
    for (const coord& crd: list) {
        equation nw;
        nw.S = { crd.x + crd.y + crd.z - MAXANS,  crd.x + crd.y + crd.z + MAXANS};
        nw.a = {-crd.x + crd.y + crd.z - MAXANS, -crd.x + crd.y + crd.z + MAXANS};
        nw.b = { crd.x - crd.y + crd.z - MAXANS,  crd.x - crd.y + crd.z + MAXANS};
        nw.c = { crd.x + crd.y - crd.z - MAXANS,  crd.x + crd.y - crd.z + MAXANS};
        
        eq = eq + nw;
    }

    for (int64_t r = 0; r <= 1; ++r) {
        equation tr = eq;

        tr.S.first  = DIV2(tr.S.first - 3 * r + 1);
        tr.a.first  = DIV2(tr.a.first - r + 1);
        tr.b.first  = DIV2(tr.b.first - r + 1);
        tr.c.first  = DIV2(tr.c.first - r + 1);

        tr.S.second = DIV2(tr.S.second - 3 * r);
        tr.a.second = DIV2(tr.a.second - r);
        tr.b.second = DIV2(tr.b.second - r);
        tr.c.second = DIV2(tr.c.second - r);

        coord sol = get_solution(tr);
        if (sol.x != INT64_MAX) {
            coord ans;
            ans.x = r + sol.y + sol.z;
            ans.y = r + sol.x + sol.z;
            ans.z = r + sol.x + sol.y;

            return ans;
        }
    }
    return coord {INT64_MAX, INT64_MAX, INT64_MAX};
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    list.reserve(100000);
    
    for (size_t T = input<size_t>(); T != 0; --T) {
        list.resize(input<size_t>());
        
        for (coord& crd: list)
            cin >> crd.x >> crd.y >> crd.z;

        int64_t L = -1; // definitely imposible
        int64_t R = 3 * int64_t(1000 * 1000 * 1000) * int64_t(1000 * 1000 * 1000) + 10; // definitely possible

        while (R - L > 1) {
            int64_t M = L + (R - L) / 2;
            if (can(M).x != INT64_MAX)
                R = M;
            else
                L = M;
        }
        coord ans = can(R);
        cout << ans.x << " " << ans.y << " " << ans.z << "\n";
    }
    
    return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

#define NotANumber -1791791791

struct query {
    int row, l, r; bool a;
    int lbl, ubr;
    query(int _row, int _l, int _r, bool _a) {row = _row; l = _l; r = _r; a = _a;}
    bool operator<(const query& other) const {
        return row < other.row;
    }
};

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    vector<pair<int, int> > points(n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &points[i].first, &points[i].second);

    sort(points.begin(), points.end());
    vector<int> xcoords;
    for (int i = 0; i < n; i++) {
        int st;
        if (xcoords.empty())
            st = points[i].first - k + 1;
        else
            st = max(xcoords.back() + 1, points[i].first - k + 1);
        for (int j = st; j <= points[i].first; j++)
            xcoords.push_back(j);
    }

    vector<query> qs;
    for (int i = 0; i < n; i++) {
        qs.push_back(query(points[i].second - k + 1, points[i].first - k + 1, points[i].first, 1));
        qs.push_back(query(points[i].second + 1, points[i].first - k + 1, points[i].first, 0));
    }

    for (query & q : qs) {
        q.lbl = lower_bound(xcoords.begin(), xcoords.end(), q.l) - xcoords.begin();
        q.ubr = upper_bound(xcoords.begin(), xcoords.end(), q.r) - xcoords.begin();
    }
    
    int xcdssz = xcoords.size();
    xcoords.clear();
    xcoords.shrink_to_fit();

    sort(qs.begin(), qs.end());

    vector<int> vec(xcdssz, 0);
    vector<int> lastchanged(xcdssz, NotANumber);
    vector<ll> ans(n);

    for (query q : qs) {
        int lbl = q.lbl;
        int ubr = q.ubr;
        for (int i = lbl; i < ubr; i++) {
            if (lastchanged[i] != NotANumber && vec[i] != 0) {
                ans[vec[i] - 1] += q.row - lastchanged[i];
            }
            if (q.a)
                vec[i]++;
            else
                vec[i]--;
            lastchanged[i] = q.row;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%lld ", ans[i]);
    printf("\n");
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 1000 * 100 + 5;
const int MAX_K = 305;

/** Interface */

inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt(T x);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void flush();

/** Read */

static const int buf_size = 20 * 1000 * 1000;

inline int getChar()
{
	static char buf[buf_size];
	static int len = 0, pos = 0;
	if (pos == len)
		pos = 0, len = fread(buf, 1, buf_size, stdin);
	if (pos == len)
		return -1;
	return buf[pos++];
}

inline int readChar()
{
	int c = getChar();
	while (c <= 32)
		c = getChar();
	return c;
}

template <class T>
inline T readInt()
{
	int s = 1, c = readChar();
	T x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}

inline int64 readInt64()
{
	int s = 1, c = readChar();
	int64 x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar(int x)
{
	if (write_pos == buf_size)
		fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
	write_buf[write_pos++] = x;
}

inline void flush()
{
	if (write_pos)
		fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}

template <class T>
inline void writeInt(T x)
{
	if (x < 0)
		writeChar('-'), x = -x;

	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
}

inline void writeInt64(int64 x)
{
	if (x < 0)
		writeChar('-'), x = -x;

	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
}

inline void writeWord(const char *s)
{
	while (*s)
		writeChar(*s++);
}

struct point
{
	int x;
	int y;
};

struct ask
{
	int l;
	int r;
	int ptr;
	int type;
};

bool cmp(const ask &a, const ask &b)
{
	return a.ptr < b.ptr;
}

int n, k;
point arr[MAX_N];
int cord[MAX_N * 2];
ask asks[MAX_N * 2];
int cord_len = 0;
int asks_len = 0;
bool have_prev_cord[MAX_N * 2];
bool have_prev_line[MAX_N * 2];
int last_of_cord[MAX_N * 2];
int last_of_line[MAX_N * 2];
int at_cord[MAX_N * 2];
int at_line[MAX_N * 2];
int64 answer[MAX_N];

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	n = readInt();
	k = readInt();

	for (int i = 0; i < n; ++i)
	{
		arr[i].x = readInt();
		arr[i].y = readInt();
		cord[cord_len++] = arr[i].x;
		cord[cord_len++] = arr[i].x - k + 1;
	}

	sort(cord, cord + 2 * n);
	cord_len = unique(cord, cord + 2 * n) - cord;
	
	for (int i = 0; i < n; ++i)
	{
		asks[asks_len].l = lower_bound(cord, cord + cord_len, arr[i].x - k + 1) - cord;
		asks[asks_len].r = lower_bound(cord, cord + cord_len, arr[i].x) - cord;
		asks[asks_len].ptr = arr[i].y - k + 1;
		asks[asks_len].type = 1;
		++asks_len;
		asks[asks_len].l = asks[asks_len - 1].l;
		asks[asks_len].r = asks[asks_len - 1].r;
		asks[asks_len].ptr = arr[i].y + 1;
		asks[asks_len].type = -1;
		++asks_len;
	}

	sort(asks, asks + asks_len, cmp);
	memset(answer, 0, sizeof(answer));
	memset(last_of_cord, 0, sizeof(last_of_cord));
	memset(last_of_line, 0, sizeof(last_of_line));
	memset(at_cord, 0, sizeof(at_cord));
	memset(at_line, 0, sizeof(at_line));
	memset(have_prev_cord, 0, sizeof(have_prev_cord));
	memset(have_prev_line, 0, sizeof(have_prev_cord));

	for (int i = 0; i < asks_len; ++i)
	{
		for (int j = asks[i].l; j <= asks[i].r; ++j)
		{
			if (!have_prev_cord[j])
			{
				have_prev_cord[j] = true;
				last_of_cord[j] = asks[i].ptr;
				at_cord[j] += asks[i].type;
			}
			else
			{
				answer[at_cord[j]] += asks[i].ptr - last_of_cord[j];

				last_of_cord[j] = asks[i].ptr;
				at_cord[j] += asks[i].type;
			}
		

			if (j != asks[i].r)
			{
				if (!have_prev_line[j])
				{
					have_prev_line[j] = true;
					last_of_line[j] = asks[i].ptr;
					at_line[j] += asks[i].type;
				}
				else
				{
					answer[at_line[j]] += 1ll * (cord[j + 1] - cord[j] - 1) * (asks[i].ptr - last_of_line[j]);

					last_of_line[j] = asks[i].ptr;
					at_line[j] += asks[i].type;
				}
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		writeInt64(answer[i]);
		writeChar(' ');
	}

	flush();

	fclose(stdin);
	fclose(stdout);

	return 0;
}

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
#include <bitset>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

#define size_t uint32_t

struct Req {
    size_t L;
    size_t R;
    size_t S;
    size_t T;
    size_t ID;
};

struct Edge {
    size_t v;
    size_t u;
    size_t prev1;
    size_t prev2;
    size_t next1;
    size_t next2;
};

const size_t MAXQ = 200000;
const size_t MAXN = 1000;
const size_t MAXM = 200000;

char answers[MAXQ];
Edge list[MAXM];
vector<size_t> last[MAXN];

std::bitset<MAXN> masks_r[MAXM / 2 + 10];
std::bitset<MAXN> masks_l[MAXM / 2 + 10];

void solve_layer(vector<Req>& requests, size_t l, size_t m, size_t r) {
    bool has = false;
    for (size_t i = 0; i != requests.size(); ++i)
        has or_eq (requests[i].L <= m - 1 and requests[i].R >= m);
    if (not has)
        return;
    
    for (size_t i = 0; i != r - m; ++i) {
        masks_r[i] = std::bitset<MAXN>();
        if (list[m + i].prev1 >= m and list[m + i].prev1 != std::numeric_limits<size_t>::max())
            masks_r[i] |= masks_r[list[m + i].prev1 - m];
        if (list[m + i].prev2 >= m and list[m + i].prev2 != std::numeric_limits<size_t>::max())
            masks_r[i] |= masks_r[list[m + i].prev2 - m];

        masks_r[i][list[m + i].v] = true;
        masks_r[i][list[m + i].u] = true;
    }
    
    for (size_t z = 0; z != m - l; ++z) {
        size_t i = (m - l) - 1 - z;
        masks_l[i] = std::bitset<MAXN>();
        
        if (list[l + i].next1 < m)
            masks_l[i] |= masks_l[list[l + i].next1 - l];
        if (list[l + i].next2 < m)
            masks_l[i] |= masks_l[list[l + i].next2 - l];
        masks_l[i][list[l + i].v] = true;
        masks_l[i][list[l + i].u] = true;
    }

    for (size_t i = 0; i != requests.size();)
        if (requests[i].L <= m - 1 and requests[i].R >= m) {
            answers[requests[i].ID] = (masks_r[requests[i].R - m] & masks_l[requests[i].L - l]).any();
            std::swap(requests[i], requests.back());
            requests.pop_back();
        } else {
            ++i;
        }
}

void solve(vector<Req>& requests, size_t l, size_t r) {
    if (l == r - 1) {
        for (auto& req: requests)
            answers[req.ID] = (req.S == list[l].v or req.S == list[l].u)
                          and (req.T == list[l].v or req.T == list[l].u);
        return;
    }
    size_t m = l + (r - l) / 2;
    // [l, m), [m, r).

    solve_layer(requests, l, m, r);

    vector<Req> right;
    for (size_t i = 0; i != requests.size();)
        if (requests[i].L >= m) {
            right.push_back(requests[i]);
            std::swap(requests[i], requests.back());
            requests.pop_back();
        } else {
            ++i;
        }

    requests.shrink_to_fit();
    solve(requests, l, m);
    solve(right, m, r);
}

int main() {
    size_t n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    assert(n <= MAXN);
    assert(q <= MAXQ);
    assert(m <= MAXM);
    
    std::fill(answers, answers + q, 16);
    
    for (size_t i = 0; i != m; ++i) {
        scanf("%d %d", &list[i].v, &list[i].u);
        --list[i].v, --list[i].u;
        list[i].prev1 = list[i].prev2 = list[i].next1 = list[i].next2 = std::numeric_limits<size_t>::max();
        
        if (not last[list[i].v].empty()) {
            list[i].prev1 = last[list[i].v].back();
            
            if (list[last[list[i].v].back()].v == list[i].v)
                list[last[list[i].v].back()].next1 = i;
            else {
                list[last[list[i].v].back()].next2 = i;
            }
        }

        if (not last[list[i].u].empty()) {
            list[i].prev2 = last[list[i].u].back();
            
            if (list[last[list[i].u].back()].v == list[i].u)
                list[last[list[i].u].back()].next1 = i;
            else {
                list[last[list[i].u].back()].next2 = i;
            }
        }
        
        last[list[i].v].push_back(i);
        last[list[i].u].push_back(i);
    }

    vector<Req> requests;
    for (size_t i = 0; i != q; ++i) {
        Req req;
        scanf("%d %d %d %d", &req.L, &req.R, &req.S, &req.T);
        --req.L, --req.R, --req.S, --req.T;
        req.ID = i;
        
        auto it1 = std::lower_bound(last[req.S].begin(), last[req.S].end(), req.L);
        auto it2 = std::upper_bound(last[req.T].begin(), last[req.T].end(), req.R);

        if (it1 == last[req.S].end() or it2 == last[req.T].begin())
            answers[i] = false;
        else {
            req.L = *it1;
            req.R = *std::prev(it2);
            if (req.L > req.R)
                answers[i] = false;
            else
                requests.push_back(req);
        }
    }
    
    solve(requests, 0, m);

    for (size_t i = 0; i != q; ++i) {
        printf("%s", (answers[i] ? "Yes\n" : "No\n"));
    }
    
    return 0;
}