結果

問題 No.650 行列木クエリ
ユーザー f1b_maxbl00df1b_maxbl00d
提出日時 2021-01-19 07:59:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,337 ms / 2,000 ms
コード長 18,978 bytes
コンパイル時間 4,418 ms
コンパイル使用メモリ 375,120 KB
最終ジャッジ日時 2025-01-18 02:31:07
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma warning(disable:4996)
//#include <Windows.h>
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;
template<class T>
using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;

template<class T>
inline void chmin(T& a, T b) {
	a = min(a, b);
}

template<class T>
inline void chmax(T& a, T b) {
	a = max(a, b);
}

void input();
void solve();

void daminput();
void naive();

void outputinput();

int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	input();
	//daminput();
	solve();
	//naive();
	//outputinput();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////

void input() {
}

void daminput() {
}

template<class K>
class Matrix {
public:
	vector<vector<K>> v;
	int H, W;
	Matrix(int h, int w) :H(h), W(w) {
		v.resize(h, vector<K>(w, K(0)));
	}
	Matrix(vector<K>& v0) {
		H = v0.size();
		W = 1;
		v.resize(H, vector<K>(1, K(0)));
		for (int y = 0; y < H; y++) {
			v[y][0] = v0[y];
		}
	}
	Matrix() :H(0), W(0) {}
	void resize(int h, int w) {
		H = h;
		W = w;
		v.resize(H, vector<K>(W, K(0)));
	}
	vector<K>& operator[](int y) {
		return v[y];
	}
	vector<K>& back() {
		return v.back();
	}
	Matrix<K>& operator+=(Matrix<K>& B);
	Matrix<K>& operator-=(Matrix<K>& B);
	Matrix<K>& operator*=(Matrix<K>& B);
	Matrix<K>& operator*=(K k);
	Matrix<K>& operator/=(K k);
};

template<class K>
Matrix<K> operator+(Matrix<K>& A, Matrix<K>& B) {
	assert(A.H == B.H && A.W == B.W);
	int H = A.H;
	int W = A.W;
	Matrix<K> C(H, W);
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			C[y][x] = A[y][x] + B[y][x];
		}
	}
	return C;
}

template<class K>
Matrix<K> operator-(Matrix<K>& A, Matrix<K>& B) {
	assert(A.H == B.H && A.W == B.W);
	int H = A.H;
	int W = A.W;
	Matrix<K> C(H, W);
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			C[y][x] = A[y][x] - B[y][x];
		}
	}
	return C;
}

template<class K>
Matrix<K> operator*(Matrix<K>& A, Matrix<K>& B) {
	assert(A.W == B.H);
	int H = A.H;
	int W = B.W;
	Matrix<K> C(H, W);
	for (int k = 0; k < A.W; k++) {
		for (int y = 0; y < H; y++) {
			for (int x = 0; x < W; x++) {
				C[y][x] += A[y][k] * B[k][x];
			}
		}
	}
	return C;
}

template<class K>
Matrix<K> operator*(Matrix<K>& A, K k) {
	int H = A.H;
	int W = A.W;
	Matrix<K> C(H, W);
	for (int y = 0; y < A.H; y++) {
		for (int x = 0; x < A.W; x++) {
			C[y][x] = A[y][x] * k;
		}
	}
	return C;
}

template<class K>
Matrix<K> operator*(K k, Matrix<K>& A) {
	int H = A.H;
	int W = A.W;
	Matrix<K> C(H, W);
	for (int y = 0; y < A.H; y++) {
		for (int x = 0; x < A.W; x++) {
			C[y][x] = A[y][x] * k;
		}
	}
	return C;
}

template<class K>
Matrix<K> operator/(Matrix<K>& A, K k) {
	int H = A.H;
	int W = A.W;
	Matrix<K> C(H, W);
	for (int y = 0; y < A.H; y++) {
		for (int x = 0; x < A.W; x++) {
			C[y][x] = A[y][x] / k;
		}
	}
	return C;
}

template<class K>
Matrix<K>& Matrix<K>::operator+=(Matrix<K>& B) {
	assert(H == B.H && W == B.W);
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			v[y][x] += B[y][x];
		}
	}
	return *this;
}

template<class K>
Matrix<K>& Matrix<K>::operator-=(Matrix<K>& B) {
	assert(H == B.H && W == B.W);
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			v[y][x] -= B[y][x];
		}
	}
	return *this;
}

template<class K>
Matrix<K>& Matrix<K>::operator*=(Matrix<K>& B) {
	*this = *this * B;
	return *this;
}

template<class K>
Matrix<K>& Matrix<K>::operator*=(K k) {
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			v[y][x] *= k;
		}
	}
	return *this;
}

template<class K>
Matrix<K>& Matrix<K>::operator/=(K k) {
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			v[y][x] /= k;
		}
	}
	return *this;
}

template<class K>
bool operator==(Matrix<K>& A, Matrix<K>& B) {
	if (A.H != B.H || A.W != B.W)return false;
	for (int y = 0; y < A.H; y++) {
		for (int x = 0; x < A.W; x++) {
			if (A[y][x] != B[y][x])return false;
		}
	}
	return true;
}

template<class K>
bool operator!=(Matrix<K>& A, Matrix<K>& B) {
	return !(A == B);
}

template<class K>
Matrix<K> pow(Matrix<K>& A, LL p) {
	assert(A.H == A.W);
	if (p == 1)return A;
	Matrix<K> temp = pow(A, p >> 1);
	temp *= temp;
	if (p == 1) {
		temp *= A;
	}
	return temp;
}

//行列Aを階段行列に変換する
//返り値:行列のランク
template<class K>
int ConvertToStair(Matrix<K>& A) {
	int H = A.H;
	int W = A.W;
	int x = 0, y = 0;
	while (true) {
		if (x >= W || y >= H)break;
		if (A[y][x] == K()) {
			int yy = y + 1;
			for (; yy < H; yy++) {
				if (A[yy][x] != K()) {
					swap(A[yy], A[y]);
					for (int xx = x; xx < W; xx++) {
						A[yy][xx] *= K(-1);
					}
					break;
				}
			}
			if (yy == H) {
				x++;
				continue;
			}
		}
		for (int yy = y + 1; yy < H; yy++) {
			K f = A[yy][x] / A[y][x];
			for (int xx = x; xx < W; xx++) {
				A[yy][xx] = A[yy][xx] - A[y][xx] * f;
			}
		}
		x++;
		y++;
	}
	return y;
}

//行列Aを階段行列に変換する
//conv[y][x] := 元の行列A_xを何回加えて今のA_yにしたか
//返り値:行列のランク
template<class K>
int ConvertToStair(Matrix<K>& A, vector<vector<K>>& conv) {
	int H = A.H;
	int W = A.W;
	int x = 0, y = 0;
	conv.resize(H, vector<K>(H, K()));
	for (int yy = 0; yy < H; yy++) {
		conv[yy][yy] = K(1);
	}
	while (true) {
		if (x >= W || y >= H)break;
		if (A[y][x] == K()) {
			int yy = y + 1;
			for (; yy < H; yy++) {
				if (A[yy][x] != K()) {
					swap(A[yy], A[y]);
					swap(conv[yy], conv[y]);
					for (int xx = x; xx < W; xx++) {
						A[yy][xx] *= K(-1);
					}
					for (int n = 0; n < H; n++) {
						conv[yy][n] *= K(-1);
					}
					break;
				}
			}
			if (yy == H) {
				x++;
				continue;
			}
		}
		for (int yy = y + 1; yy < H; yy++) {
			K f = A[yy][x] / A[y][x];
			for (int xx = x; xx < W; xx++) {
				A[yy][xx] = A[yy][xx] - A[y][xx] * f;
			}
			for (int n = 0; n < H; n++) {
				conv[yy][n] -= conv[y][n] * f;
			}
		}
		x++;
		y++;
	}
	return y;
}

//行列式を求める
template<class K>
K Determinant(Matrix<K>& A) {
	ConvertToStair(A);
	K ans(1);
	for (int y = 0; y < A.H; y++) {
		ans *= A[y][y];
	}
	return ans;
}

//線型方程式を解く
//返り値:解の有無
//particular:特殊解
//bases:解空間の基底
template<class K>
bool SolveLinearEquations(Matrix<K>& A, vector<K>& B, vector<vector<K>>& bases, vector<K>& particular) {
	int H = A.H;
	int W = A.W;
	int X = 0, Y = 0;
	//階段行列に変形
	while (true) {
		if (X >= W || Y >= H)break;
		if (A[Y][X] == K()) {
			int y = Y + 1;
			for (; y < H; y++) {
				if (A[y][X] != K()) {
					swap(A[y], A[Y]);
					swap(B[y], B[Y]);
					break;
				}
			}
			if (y == H) {
				X++;
				continue;
			}
		}
		for (int y = Y + 1; y < H; y++) {
			K f = A[y][X] / A[Y][X];
			for (int x = X; x < W; x++) {
				A[y][x] = A[y][x] - A[Y][x] * f;
			}
			B[y] -= B[Y] * f;
		}
		X++;
		Y++;
	}
	//元のAのランクと、AにBをくっつけた拡張行列のランクが等しいか確かめる
	for (int y = Y; y < H; y++) {
		if (B[y] != K(0)) {
			//解は存在しない
			return false;
		}
	}
	int rank = Y;
	bases.resize(W - rank, vector<K>(W, K(0)));
	//右上三角行列を作るように列を取っていく
	particular.resize(W, K(0));
	X = 0;
	Y = 0;
	VI use;   //取る列
	VI notuse;   //取らない列
	while (X < W && Y < rank) {
		if (A[Y][X] == K(0)) {
			notuse.push_back(X);
			X++;
		}
		else {
			use.push_back(X);
			X++;
			Y++;
		}
	}
	while (X < W) {
		notuse.push_back(X);
		X++;
	}
	//特殊解を求める
	for (int x : notuse) {
		particular[x] = K(0);
	}
	for (int y = rank - 1; y >= 0; y--) {
		K b = B[y];
		for (int x = y + 1; x < rank; x++) {
			b -= A[y][use[x]] * particular[use[x]];
		}
		particular[use[y]] = b / A[y][use[y]];
	}
	//解空間の基底
	for (int base = 0; base < W - rank; base++) {
		vector<K>& v = bases[base];
		for (int x : notuse) {
			v[x] = K(0);
		}
		v[notuse[base]] = K(1);
		for (int y = rank - 1; y >= 0; y--) {
			K b = -1 * A[y][notuse[base]];
			for (int x = y + 1; x < rank; x++) {
				b -= A[y][use[x]] * v[use[x]];
			}
			v[use[y]] = b / A[y][use[y]];
		}
	}
	return true;
}

//線型方程式を解く
//返り値:解空間の有無
//particular:特殊解
template<class K>
bool SolveLinearEquations(Matrix<K>& A, vector<K>& B, vector<K>& particular) {
	int H = A.H;
	int W = A.W;
	int X = 0, Y = 0;
	//階段行列に変形
	while (true) {
		if (X >= W || Y >= H)break;
		if (A[Y][X] == K()) {
			int y = Y + 1;
			for (; y < H; y++) {
				if (A[y][X] != K()) {
					swap(A[y], A[Y]);
					swap(B[y], B[Y]);
					break;
				}
			}
			if (y == H) {
				X++;
				continue;
			}
		}
		for (int y = Y + 1; y < H; y++) {
			K f = A[y][X] / A[Y][X];
			for (int x = X; x < W; x++) {
				A[y][x] = A[y][x] - A[Y][x] * f;
			}
			B[y] -= B[Y] * f;
		}
		X++;
		Y++;
	}
	//元のAのランクと、AにBをくっつけた拡張行列のランクが等しいか確かめる
	for (int y = Y; y < H; y++) {
		if (B[y] != K(0)) {
			//解は存在しない
			return false;
		}
	}
	int rank = Y;
	//右上三角行列を作るように列を取っていく
	particular.resize(W, K(0));
	X = 0;
	Y = 0;
	VI use;   //取る列
	VI notuse;   //取らない列
	while (X < W && Y < rank) {
		if (A[Y][X] == K(0)) {
			notuse.push_back(X);
			X++;
		}
		else {
			use.push_back(X);
			X++;
			Y++;
		}
	}
	while (X < W) {
		notuse.push_back(X);
		X++;
	}
	//特殊解を求める
	for (int x : notuse) {
		particular[x] = K(0);
	}
	for (int y = rank - 1; y >= 0; y--) {
		K b = B[y];
		for (int x = y + 1; x < rank; x++) {
			b -= A[y][use[x]] * particular[use[x]];
		}
		particular[use[y]] = b / A[y][use[y]];
	}
	return true;
}

template<class T>
struct Gedge {
	int src, to;
	T cost;
	int id;
	Gedge(int s, int t, T c, int i = -1) :src(s), to(t), cost(c), id(i) {}
	Gedge(int t, T c) :src(-1), to(t), cost(c), id(-1) {}
};

template<class T>
using WeightedGraph = vector<vector<Gedge<T>>>;
using UnweightedGraph = vector<vector<LL>>;
template<class T>
using Gedges = vector<Gedge<T>>;

template<class T>
struct TNode {
	int parent;
	VI childs;
	T cost;
	int id;
	TNode() :parent(-1), cost(0), id(-1) {};
};
template<class T>
using Tree = vector<TNode<T>>;

template<class T>
class HLD {
public:
	Tree<T>& tree;
	LL V;
	VLL depth;   //各頂点が属するHeavy集合の深さ
	VLL top;   //各頂点が属するHeavy集合の一番上の頂点
	VLL in;   //各頂点がEuler-Tourでどこにいるか
	VLL out;   //各頂点の部分木の終わり
	HLD(Tree<T>& t, LL root = 0) :tree(t) {
		V = t.size();
		VLL subtrees(V, -1);
		//各部分木のサイズを求める
		{
			stack<LL> order;
			stack<LL> hold;
			hold.push(root);
			while (!hold.empty()) {
				LL cur = hold.top();
				hold.pop();
				order.push(cur);
				for (LL ch : tree[cur].childs) {
					hold.push(ch);
				}
			}
			while (!order.empty()) {
				LL cur = order.top();
				order.pop();
				subtrees[cur] = 1;
				for (int& ch : tree[cur].childs) {
					subtrees[cur] += subtrees[ch];
					if (subtrees[ch] > subtrees[tree[cur].childs[0]]) {
						swap(ch, tree[cur].childs[0]);
					}
				}
			}
		}
		//HL分解 with eulertour
		{
			in.resize(V);
			out.resize(V);
			depth.resize(V);
			top.resize(V);
			LL cur = root;
			LL nextid = 0;
			dfs(cur, nextid);
		}
	}
	void dfs(LL cur, LL& nextind) {
		in[cur] = nextind++;
		for (auto ch : tree[cur].childs) {
			//0番目の子は同じHeavy集合
			if (ch == tree[cur].childs[0]) {
				top[ch] = top[cur];
				depth[ch] = depth[cur];
			}
			//それ以外は新しいHeavy集合
			else {
				top[ch] = ch;
				depth[ch] = depth[cur] + 1;
			}
			dfs(ch, nextind);
		}
		out[cur] = nextind - 1;
	}
	LL LCA(LL u, LL v) {
		//uの属するnode.depth >= vの属するnode.depthにする
		if (depth[u] < depth[v]) {
			swap(u, v);
		}
		while (depth[u] > depth[v]) {
			u = tree[top[u]].parent;
		}
		while (top[u] != top[v]) {
			u = tree[top[u]].parent;
			v = tree[top[v]].parent;
		}
		if (in[u] > in[v])return v;
		else return u;
	}
};

template<class Type>
void SetTree(WeightedGraph<Type>& G, Tree<Type>& T, int root = 0) {
	int N = G.size();
	T.resize(N);
	queue<int> q;
	q.push(root);
	T[root].parent = -1;
	T[root].id = -1;
	T[root].cost = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (Gedge<Type>& e : G[cur]) {
			if (e.to == T[cur].parent)continue;
			T[e.to].parent = cur;
			T[cur].childs.push_back(e.to);
			T[e.to].id = e.id;
			T[e.to].cost = e.cost;
			q.push(e.to);
		}
	}
}

//TT(T,T):=モノイドの乗算
//require Monoid
template<class T>
class Segtree {
private:
	vector<T> seg;
	LL RN;
	typedef function<T(T, T)> TT;
	TT f;
	T te;
public:
	Segtree(LL N, TT _f, T e) :te(e) {
		RN = 1;
		while (RN < N)RN *= 2;
		seg.resize(2 * RN, te);
		f = _f;
	}
	Segtree(vector<T>& V, TT _f, T e) :te(e) {
		LL N = V.size();
		RN = 1;
		while (RN < N)RN *= 2;
		seg.resize(2 * RN, te);
		f = _f;
		for (LL n = 0; n < N; n++) seg[RN + n] = V[n];
		for (LL k = RN - 1; k >= 1; k--) {
			seg[k] = f(seg[2 * k], seg[2 * k + 1]);
		}
	}
	//set n-th as x(0 index!!!!!)
	void set(LL n, T x) {
		seg[RN + n] = x;
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//change n-th number p to x*p(0 index!!!!!)
	void addl(LL n, T x) {
		seg[RN + n] = f(x, seg[RN + n]);
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//change n-th number p to p*x(0 index!!!!!)
	void addr(LL n, T x) {
		seg[RN + n] = f(seg[RN + n], x);
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//get [l,r] (0 index!!!!!)
	T get(LL l, LL r) {
		T ansl = te, ansr = te;
		r++;
		l += RN;
		r += RN;
		while (l < r) {
			if (l & 1) {
				ansl = f(ansl, seg[l]);
				l++;
			}
			if (r & 1) {
				r--;
				ansr = f(seg[r], ansr);
			}
			l >>= 1;
			r >>= 1;
		}
		return f(ansl, ansr);
	}
	//get n-th number(0 index!!!!!)
	T get(LL n) {
		return seg[RN + n];
	}
	T operator[](LL n) {
		return seg[RN + n];
	}
};

class Modint {
public:
	LL v;
	Modint(LL _v) {
		_v %= MOD;
		if (_v < 0)_v += MOD;
		v = _v;
	}
	Modint operator+=(Modint m);
	Modint operator-=(Modint m);
	Modint operator*=(Modint m);
	Modint operator/=(Modint m);
	friend ostream& operator<<(ostream& st, const Modint& m);
	friend istream& operator>>(istream& st, Modint& m);
	Modint() :v(0) {}
	static Modint one;
};
bool operator==(Modint a, Modint b) {
	return a.v == b.v;
}
bool operator!=(Modint a, Modint b) {
	return a.v != b.v;
}
Modint Modint::one = Modint(1);
template<class T>
T pow(T& base, LL p) {
	if (p == 0)return T();
	else if (p == 1)return base;
	T ret = pow(base, p / 2);
	ret *= ret;
	if (p & 1)ret *= base;
	return ret;
}
template<class T>
T modpow(T base, LL p) {
	if (p == 0)return T();
	else if (p == 1)return base;
	T ret = modpow(base, p / 2);
	ret *= ret;
	if (p & 1)ret *= base;
	return ret;
}
ostream& operator<<(ostream& st, const Modint& m) {
	cout << m.v;
	return st;
}
istream& operator>>(istream& st, Modint& m) {
	LL v;
	cin >> v;
	m.v = v % MOD;
	return st;
}
Modint operator+(Modint a, Modint b) {
	Modint r;
	r.v = a.v + b.v;
	if (r.v >= MOD)r.v -= MOD;
	return r;
}
Modint operator-(Modint a, Modint b) {
	Modint r;
	r.v = a.v - b.v;
	if (r.v < 0)r.v += MOD;
	return r;
}
Modint operator*(Modint a, Modint b) {
	return Modint((a.v * b.v) % MOD);
}
Modint operator+(Modint a, LL b) {
	return Modint(a.v + b);
}
Modint operator+(LL a, Modint b) {
	return Modint(a + b.v);
}
Modint operator-(Modint a, LL b) {
	return Modint(a.v - b);
}
Modint operator-(LL a, Modint b) {
	return Modint(a - b.v);
}
Modint operator*(Modint a, LL b) {
	return Modint(a.v * (b % MOD));
}
Modint operator*(LL a, Modint b) {
	return Modint((a % MOD) * b.v);
}
Modint operator/(Modint a, Modint b) {
	return a * modpow(b, MOD - 2);
}
Modint Modint::operator+=(Modint m) {
	*this = *this + m;
	return *this;
}
Modint Modint::operator-=(Modint m) {
	*this = *this - m;
	return *this;
}
Modint Modint::operator*=(Modint m) {
	*this = *this * m;
	return *this;
}
Modint Modint::operator/=(Modint m) {
	*this *= modpow(m, MOD - 2);
	return *this;
}
//O(min(N-R,R))
Modint Comb(LL N, LL R) {
	if (R > N - R)return Comb(N, N - R);
	Modint ans((LL)1);
	for (LL n = N; n > N - R; n--) {
		ans *= Modint(n);
	}
	for (LL n = R; n >= 1; n--) {
		ans *= modpow(Modint(n), MOD - 2);
	}
	return ans;
}

void solve() {
	int N;
	cin >> N;
	WeightedGraph<int> G(N);
	VI A(N-1), B(N-1);
	for (int n = 0; n < N - 1; n++) {
		int a, b;
		cin >> a >> b;
		A[n] = a;
		B[n] = b;
		G[a].push_back(Gedge<int>(a, b, 0, n));
		G[b].push_back(Gedge<int>(b, a, 0, n));
	}
	Tree<int> T;
	SetTree(G, T, 0);
	HLD<int> hld(T, 0);
	VI etov(N-1, -1);
	for (int n = 0; n < N - 1; n++) {
		int a = A[n];
		int b = B[n];
		if (T[a].parent == b) {
			etov[n] = a;
		}
		else {
			etov[n] = b;
		}
	}
	Matrix<Modint> E(2, 2);
	E[0][0] = 1;
	E[0][1] = 0;
	E[1][0] = 0;
	E[1][1] = 1;
	Segtree<Matrix<Modint>> seg(N, [](Matrix<Modint> a, Matrix<Modint> b) {
		return a * b;
	}, E);
	int Q;
	cin >> Q;
	for (int q = 0; q < Q; q++) {
		string type;
		cin >> type;
		if (type[0] == 'x') {
			int i;
			Modint x00, x01, x10, x11;
			cin >> i >> x00 >> x01 >> x10 >> x11;
			i = etov[i];
			Matrix<Modint> after(2, 2);
			after[0][0] = x00;
			after[0][1] = x01;
			after[1][0] = x10;
			after[1][1] = x11;
			int iconv = hld.in[i];
			seg.set(iconv, after);
		}
		else {
			int i, j;
			cin >> i >> j;
			Matrix<Modint> ans = E;
			while (hld.top[i] != hld.top[j]) {
				int jtop = hld.top[j];
				int jconv = hld.in[j];
				int jtopconv = hld.in[jtop];
				Matrix<Modint> res = seg.get(jtopconv, jconv);
				ans = res * ans;
				j = jtop;
				j = T[j].parent;
			}
			if (i != j) {
				int jmax = j;
				while (T[jmax].parent != i) {
					jmax = T[jmax].parent;
				}
				int jconv = hld.in[j];
				int jmaxconv = hld.in[jmax];
				Matrix<Modint> res = seg.get(jmaxconv, jconv);
				ans = res * ans;
			}
			cout << ans[0][0] << " " << ans[0][1] << " " << ans[1][0] << " " << ans[1][1] << "\n";
		}
	}
}

void naive() {
}

void outputinput() {
}
0