Description：

一个 $9$ 个点的图有 $n$ 条有向边，每条边有优先级 $p$ 和距离 $w$ ，要求在移动时经过的边优先级不降，每次询问会给出 $k_i$ 个区间，询问优先级在这 $k_i$ 个区间中的边能用的时候从 $s_i$ 到 $t_i$ 的最短路。

$1\leqslant n\leqslant10^5,1\leqslant\sum s_i\leqslant 10^4,1\leqslant p_i\leqslant 2000$

Solution：

图只有 $9$ 个点，这一定是这道题的入手点，又发现题意给出的是若干个区间，这就不难想到线段树维护最短路矩阵乘积，可以考虑建一个 $[1,2000]$ 的线段树，先把所有边按 $p_i$ 分类加进去但不做任何处理，全部做完后在每个点跑 $floyed$ ，然后向上 $pushup$ ， $pushup$ 的过程就是矩阵乘法，由于要求经过的边优先级不降，所以乘的时候左区间的边优先级小要在左边，好像优先级能降就不能这么做了，然后询问时把所有询问区间排序依次把转移矩阵乘起来即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXM 100010

#define MAXN 10

int n = 9,m,q;

#define MAXP 2010

typedef long long ll;

#define INF 0x3f3f3f3f3f3f3f3f

struct matrix

{

	ll m[MAXN][MAXN];

	matrix()

	{

		memset(m,0x3f,sizeof(m));

		for(int i = 1;i <= n;++i)m[i][i] = 0;

		return;

	}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int k = 1;k <= n;++k)

			for(int i = 1;i <= n;++i)

				for(int j = 1;j <= n;++j)

					c.m[i][j] = min(c.m[i][j],a.m[i][k] + b.m[k][j]);

		return c;

	}

	void floyed()

	{

		for(int k = 1;k <= n;++k)

			for(int i = 1;i <= n;++i)

				for(int j = 1;j <= n;++j)

					m[i][j] = min(m[i][j],m[i][k] + m[k][j]);

		return;

	}

};

struct node

{

	int lc,rc;

	matrix s;

}t[MAXP << 1];

#define NEG 1

#define POS 2000

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int p,int u,int v,ll w,int l,int r)

{

	if(l == r)

	{

		t[rt].s.m[u][v] = min(t[rt].s.m[u][v],w);

		return;

	}

	if(p <= mid)add(t[rt].lc,p,u,v,w,l,mid);

	else add(t[rt].rc,p,u,v,w,mid + 1,r);

	return;

}

void reset(int rt,int l,int r)

{

	if(l == r)

	{

		t[rt].s.floyed();

		return;

	}

	reset(t[rt].lc,l,mid);

	reset(t[rt].rc,mid + 1,r);

	t[rt].s = t[t[rt].lc].s * t[t[rt].rc].s;

	return;

}

matrix query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].s;

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	return (query(t[rt].lc,L,R,l,mid) * query(t[rt].rc,L,R,mid + 1,r));

}

struct seg

{

	int l,r;

	bool operator < (seg b)const

	{

		return l < b.l;

	}

}s[MAXN];

int main()

{

	freopen("tesseract.in","r",stdin);

	freopen("tesseract.out","w",stdout);

	m = read();read();

	int p,u,v;

	ll w;

	build(root,NEG,POS);

	for(int i = 1;i <= m;++i)

	{

		p = read();u = read() + 1;v = read() + 1;w = read();

		add(root,p,u,v,w,NEG,POS);

	}

	reset(root,NEG,POS);

	scanf("%d",&q);

	int l,r;

	for(int i = 1;i <= q;++i)

	{

		matrix res;

		u = read() + 1;v = read() + 1;p = read();

		for(int k = 1;k <= p;++k)

		{

			s[k].l = read();s[k].r = read();

		}

		sort(s + 1,s + 1 + p);

		for(int k = 1;k <= p;++k)

		{

			res = res * query(root,s[k].l,s[k].r,NEG,POS);

		}

		if(res.m[u][v] != INF)printf("%lld\n",res.m[u][v]);

		else puts("-1");

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}