結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 f1b_maxbl00d
|
| 提出日時 | 2021-01-19 07:53:06 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,873 bytes |
| コンパイル時間 | 11,132 ms |
| コンパイル使用メモリ | 410,332 KB |
| 実行使用メモリ | 61,408 KB |
| 最終ジャッジ日時 | 2023-08-22 04:04:18 |
| 合計ジャッジ時間 | 16,668 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 124 ms
16,880 KB |
| testcase_02 | AC | 268 ms
61,376 KB |
| testcase_03 | AC | 1 ms
4,380 KB |
| testcase_04 | AC | 125 ms
16,860 KB |
| testcase_05 | AC | 265 ms
61,408 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,388 KB |
| testcase_08 | TLE | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
ソースコード
//#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;
}
while (j != i) {
int jconv = hld.in[j];
Matrix<Modint> res = seg.get(jconv);
ans = res * ans;
j = T[j].parent;
}
cout << ans[0][0] << " " << ans[0][1] << " " << ans[1][0] << " " << ans[1][1] << "\n";
}
}
}
void naive() {
}
void outputinput() {
}