/*
,----.. ____ ,----..
,--, ,--, / / \ .--.--. ,----.. ,---,. ,---, ,---,. ,' , `.,-.----. ,---,. / / \
|'. \ / .`| / . : / / '. / / \ ,' .' | .' .' `\ ,' .' | ,-+-,.' _ |\ / \ ,--, ,' .' | / . :
; \ `\ /' / ; . / ;. \ : /`. / / . : ,---.' |,---.' \ ,---.' | ,-+-. ; , ||; : \ ,'_ /|,---.' | . / ;. \
`. \ / / .'. ; / ` ; | |--` . / ;. \ | | .'| | .`\ || | .' ,--.'|' | ;|| | .\ : .--. | | :| | .'. ; / ` ;
\ \/ / ./ ; | ; \ ; | : ;_ . ; / ` ; : : |-,: : | ' |: : |-,| | ,', | ':. : |: | ,'_ /| : . |: : : ; | ; \ ; |
\ \.' / | : | ; | '\ \ `. ; | ; \ ; | : | ;/|| ' ' ; :: | ;/|| | / | | ||| | \ : | ' | | . .: | |-,| : | ; | '
\ ; ; . | ' ' ' : `----. \| : | ; | ' | : .'' | ; . || : .'' | : | : |,| : . / | | ' | | || : ;/|. | ' ' ' :
/ \ \ \ ' ; \; / | __ \ \ |. | ' ' ' : | | |-,| | : | '| | |-,; . | ; |--' ; | | \ : | | : ' ;| | .'' ; \; / |
; /\ \ \ \ \ ', / / /`--' /' ; \; / | ' : ;/|' : | / ; ' : ;/|| : | | , | | ;\ \| ; ' | | '' : ' \ \ ', /
./__; \ ; \ ; : / '--'. / \ \ ', . \| | \| | '` ,/ | | \| : ' |/ : ' | \.': | : ; ; || | | ; : /
| : / \ \ ; \ \ .' `--'---' ; : ; | : .'; : .' | : .'; | |`-' : : :-' ' : `--' \ : \ \ \ .'
; |/ \ ' | `---` \ \ .'`--"| | ,' | ,.' | | ,' | ;/ | |.' : , .-./ | ,' `---`
`---' `--` `---` `----' '---' `----' '---' `---' `--`----' `----' */
//Author RufatM
/*#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("inline")
#pragma GCC optimize("tree-vectorize")
#pragma GCC optimize("loop-vectorize")
#pragma GCC optimize("loop-interchange")
#pragma GCC optimize("loop-block")
#pragma GCC optimize("loop-strip-mine")
#pragma GCC optimize("loop-optimize")
#pragma GCC optimize("tree-loop-distribute-patterns")
#pragma GCC optimize("tree-loop-distribute-force")
#pragma GCC optimize("tree-loop-distribute")
#pragma GCC optimize("tree-loop-vectorize")
#pragma GCC optimize("tree-loop-ivcanon")
#pragma GCC optimize("tree-loop-ivopts")
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvp;
typedef vector<bool> vb;
typedef vector<string> vs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define mt19937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count())
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using max_heap = priority_queue<T>;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
template<typename T> bool isPrime(T n) { if (n <= 1)return false;if (n <= 3)return true;if (n % 2 == 0 || n % 3 == 0)return false;for (T i = 5;i * i <= n;i += 6)if (n % i == 0 || n % (i + 2) == 0)return false;return true; }
const int MOD = 998244353;
const int INF = 1e9 + 7;
const int LOG = 21;
const long long LINF = 1e18 + 7;
const int MAXN = 1e5 + 7;
const int MAXM = 1e6 + 7;
ll binpow(ll a, ll b, ll m = MOD) {
ll res = 1;
a %= m;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
ll modinv(ll a, ll m = MOD) {
return binpow(a, m - 2, m);
}
struct segment_tree {
int n;
vector<ll> t;
segment_tree(int _n) : n(_n) {
t.assign(4 * n, 0);
}
void build(int v, int tl, int tr, const vector<ll>& a) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm, a);
build(v * 2 + 1, tm + 1, tr, a);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
void update(int v, int tl, int tr, int pos, ll new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm, pos, new_val);
else
update(v * 2 + 1, tm + 1, tr, pos, new_val);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
ll query(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return query(v * 2, tl, tm, l, min(r, tm)) +
query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}
};
struct DSU {
vi parent, size;
DSU(int n) {
parent.resize(n);
iota(all(parent), 0);
size.assign(n, 1);
}
int find(int v) {
return v == parent[v] ? v : parent[v] = find(parent[v]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
return true;
}
};
struct Fenwick {
vi bit;
int n;
Fenwick(int _n) : n(_n) {
bit.assign(n + 1, 0);
}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
int sum(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx)
res += bit[idx];
return res;
}
int range_sum(int l, int r) {
return sum(r) - sum(l - 1);
}
};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
template<typename T>
void read(T &x) {
x = 0; char c = getchar(); bool neg = false;
while (c < '0' || c > '9') { if (c == '-') neg = true; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
if (neg) x = -x;
}
template<typename T>
void write(T x) {
if (x < 0) putchar('-'), x = -x;
char buf[20]; int i = 0;
do { buf[i++] = x % 10 + '0'; x /= 10; } while (i);
while (i--) putchar(buf[i]);
putchar('\n');
}
void bigwrite(ll x) {
if (x < 0) putchar('-'), x = -x;
char buf[20]; int i = 0;
do { buf[i++] = x % 10 + '0'; x /= 10; } while (i);
while (i--) putchar(buf[i]);
putchar('\n');
}
struct bignum {
static const int base = 1000000000, base_digits = 9;
vector<int> digits;
bool sign;
bignum() : sign(1) {}
bignum(long long v) { *this = v; }
bignum(const string &s) { read(s); }
void operator=(const bignum &v) { sign = v.sign; digits = v.digits; }
bignum& operator=(long long v) {
sign = v >= 0;
v = std::abs(v);
digits.clear();
while (v) {
digits.push_back(v % base);
v /= base;
}
return *this;
}
bignum& operator=(const string &s) { read(s); return *this; }
void trim() {
while (!digits.empty() && digits.back() == 0) digits.pop_back();
if (digits.empty()) sign = 1;
}
void read(const string &s) {
sign = 1;
digits.clear();
int pos = 0;
while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-') sign = 0;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = std::max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + (s[j] - '0');
digits.push_back(x);
}
trim();
}
string to_string() const {
if (digits.empty()) return "0";
string res = sign ? "" : "-";
res += std::to_string(digits.back());
for (int i = int(digits.size()) - 2; i >= 0; --i)
res += std::string(base_digits - std::to_string(digits[i]).size(), '0') + std::to_string(digits[i]);
return res;
}
friend ostream& operator<<(ostream &stream, const bignum &v) { return stream << v.to_string(); }
friend istream& operator>>(istream &stream, bignum &v) { string s; stream >> s; v.read(s); return stream; }
void print128(__int128 x) const {
if (x == 0) { cout << 0; return; }
if (x < 0) { cout << '-'; x = -x; }
char buf[50];
int p = 0;
while (x) {
buf[p++] = '0' + (x % 10);
x /= 10;
}
for (int i = p - 1; i >= 0; --i) cout << buf[i];
}
bool is_zero() const { return digits.empty(); }
int compare(const bignum &v) const {
if (sign != v.sign) return sign ? 1 : -1;
if (digits.size() != v.digits.size())
return (digits.size() > v.digits.size() ? 1 : -1) * (sign ? 1 : -1);
for (int i = int(digits.size()) - 1; i >= 0; --i)
if (digits[i] != v.digits[i]) return (digits[i] > v.digits[i] ? 1 : -1) * (sign ? 1 : -1);
return 0;
}
bool operator<(const bignum &v) const { return compare(v) < 0; }
bool operator>(const bignum &v) const { return compare(v) > 0; }
bool operator<=(const bignum &v) const { return compare(v) <= 0; }
bool operator>=(const bignum &v) const { return compare(v) >= 0; }
bool operator==(const bignum &v) const { return compare(v) == 0; }
bool operator!=(const bignum &v) const { return compare(v) != 0; }
bignum abs() const { bignum res = *this; res.sign = 1; return res; }
int size() const { return digits.size(); }
int digit_sum() const { int s = 0; for (auto d : digits) { int x = d; while (x) { s += x % 10; x /= 10; } } return s; }
int digits_count() const {
if (is_zero()) return 1;
int cnt = (digits.size() - 1) * base_digits;
int top = digits.back();
while (top) { ++cnt; top /= 10; }
return cnt;
}
int parity() const { return is_zero() ? 0 : digits[0] % 2; }
void shift_left(int n) {
if (is_zero() || n == 0) return;
digits.insert(digits.begin(), n, 0);
}
void shift_right(int n) {
if (n >= digits.size()) digits.clear();
else digits.erase(digits.begin(), digits.begin() + n);
trim();
}
bignum operator-() const { bignum res = *this; if (!is_zero()) res.sign = !sign; return res; }
bignum& operator+=(const bignum &v) { *this = *this + v; return *this; }
bignum& operator-=(const bignum &v) { *this = *this - v; return *this; }
bignum& operator*=(const bignum &v) { *this = *this * v; return *this; }
bignum& operator/=(const bignum &v) { *this = *this / v; return *this; }
bignum& operator%=(const bignum &v) { *this = *this % v; return *this; }
bignum operator+(const bignum &v) const {
if (!sign && !v.sign) return -((-*this) + (-v));
if (!sign) return v - (-*this);
if (!v.sign) return *this - (-v);
bignum res;
int carry = 0;
for (int i = 0; i < std::max(size(), v.size()) || carry; ++i) {
int x = carry;
if (i < size()) x += digits[i];
if (i < v.size()) x += v.digits[i];
res.digits.push_back(x % base);
carry = x / base;
}
res.trim();
return res;
}
bignum operator-(const bignum &v) const {
if (!v.sign) return *this + (-v);
if (!sign) return -((-*this) + v);
if (*this < v) return -(v - *this);
bignum res = *this;
int carry = 0;
for (int i = 0; i < v.size() || carry; ++i) {
res.digits[i] -= carry + (i < v.size() ? v.digits[i] : 0);
if (res.digits[i] < 0) {
res.digits[i] += base;
carry = 1;
} else carry = 0;
}
res.trim();
return res;
}
bignum operator*(long long v) const {
bignum res;
res.sign = (v >= 0) == sign;
v = std::abs(v);
__int128 carry = 0;
for (int i = 0; i < size() || carry; ++i) {
__int128 cur = carry;
if (i < size()) cur += (__int128)digits[i] * v;
res.digits.push_back(int(cur % base));
carry = cur / base;
}
res.trim();
return res;
}
bignum operator*(const bignum &v) const {
bignum res;
res.sign = (sign == v.sign);
res.digits.assign(size() + v.size(), 0);
for (int i = 0; i < size(); ++i) {
__int128 carry = 0;
for (int j = 0; j < v.size() || carry; ++j) {
__int128 cur = res.digits[i + j] + (__int128)digits[i] * (j < v.size() ? v.digits[j] : 0) + carry;
res.digits[i + j] = int(cur % base);
carry = cur / base;
}
}
res.trim();
return res;
}
bignum operator/(long long v) const {
bignum res = *this;
res.sign = (v >= 0) == sign;
v = std::abs(v);
__int128 rem = 0;
for (int i = int(res.size()) - 1; i >= 0; --i) {
__int128 cur = res.digits[i] + rem * base;
res.digits[i] = int(cur / v);
rem = cur % v;
}
res.trim();
return res;
}
pair<bignum, long long> divmod(long long v) const {
bignum res = *this;
res.sign = (v >= 0) == sign;
v = std::abs(v);
__int128 rem = 0;
for (int i = int(res.size()) - 1; i >= 0; --i) {
__int128 cur = res.digits[i] + rem * base;
res.digits[i] = int(cur / v);
rem = cur % v;
}
res.trim();
return {res, (long long)(sign ? rem : -rem)};
}
bignum operator/(const bignum &v) const { return divmod_bignum(v).first; }
bignum operator%(const bignum &v) const { return divmod_bignum(v).second; }
pair<bignum, bignum> divmod_bignum(const bignum &v) const {
int norm = base / (v.digits.back() + 1);
bignum a = abs() * norm;
bignum b = v.abs() * norm;
bignum q, r;
q.digits.resize(a.size());
for (int i = int(a.size()) - 1; i >= 0; --i) {
r.shift_left(1);
r.digits[0] = a.digits[i];
r.trim();
int s1 = r.size() <= b.size() ? 0 : r.digits[b.size()];
int s2 = r.size() <= b.size() - 1 ? 0 : r.digits[b.size() - 1];
long long d = ((long long)base * s1 + s2) / b.digits.back();
r = r - b * d;
while (r < 0) { r = r + b; --d; }
q.digits[i] = d;
}
q.trim();
r = r / norm;
if (!sign) q = -q;
if (!sign) r = -r;
return {q, r};
}
bignum pow(long long n) const {
bignum a = *this, res = 1;
while (n > 0) {
if (n & 1) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
bignum sqrt() const {
bignum left = 0, right = *this, ans = 0;
while (left <= right) {
bignum mid = (left + right) / 2;
if (mid * mid <= *this) {
ans = mid;
left = mid + 1;
} else right = mid - 1;
}
return ans;
}
bignum gcd(const bignum &v) const {
return v.is_zero() ? *this : v.gcd(*this % v);
}
bignum lcm(const bignum &v) const {
return (*this / gcd(v)) * v;
}
bignum abs_mod(long long v) const {
__int128 rem = 0;
for (int i = int(size()) - 1; i >= 0; --i)
rem = (rem * base + digits[i]) % v;
return rem;
}
void inc() { *this += 1; }
void dec() { *this -= 1; }
bignum max(const bignum &v) const { return (*this < v) ? v : *this; }
bignum min(const bignum &v) const { return (*this < v) ? *this : v; }
bignum next() const { bignum res = *this; res.inc(); return res; }
bignum prev() const { bignum res = *this; res.dec(); return res; }
vector<int> as_vector() const { return digits; }
int leading_digit() const { return is_zero() ? 0 : std::to_string(digits.back())[0] - '0'; }
int trailing_digit() const { return is_zero() ? 0 : digits[0] % 10; }
bignum powmod(long long n, long long mod) const {
bignum a = *this % mod, res = 1;
while (n > 0) {
if (n & 1) res = (res * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return res;
}
bool is_even() const { return is_zero() ? true : (digits[0] % 2 == 0); }
bool is_odd() const { return !is_even(); }
bignum factorial() const {
bignum res = 1;
for (bignum i = 2; i <= *this; i += 1) res *= i;
return res;
}
bignum binomial(const bignum &k) const {
bignum res = 1, x = *this, y = k;
for (bignum i = 1; i <= k; i += 1) {
res = res * (x - i + 1) / i;
}
return res;
}
bignum reverse_digits() const {
string s = to_string();
std::reverse(s.begin() + (sign ? 0 : 1), s.end());
return bignum(s);
}
int digit_at(int idx) const {
string s = to_string();
if (idx < 0 || idx >= s.size()) return 0;
return s[s.size() - 1 - idx] - '0';
}
bignum operator++() { *this += 1; return *this; }
bignum operator--() { *this -= 1; return *this; }
};
struct rabinkarp {
typedef long long ll;
static const ll mod1 = 1000000007;
static const ll mod2 = 1000000009;
static const ll base1 = 911;
static const ll base2 = 3571;
vector<ll> pow1, pow2, hash1, hash2;
string s;
rabinkarp(const string &_s) {
s = _s;
int n = s.size();
pow1.resize(n+1), pow2.resize(n+1), hash1.resize(n+1), hash2.resize(n+1);
pow1[0] = pow2[0] = 1;
for(int i=1;i<=n;++i) {
pow1[i] = (pow1[i-1]*base1)%mod1;
pow2[i] = (pow2[i-1]*base2)%mod2;
}
hash1[0] = hash2[0] = 0;
for(int i=0;i<n;++i) {
hash1[i+1] = (hash1[i]*base1 + s[i]) % mod1;
hash2[i+1] = (hash2[i]*base2 + s[i]) % mod2;
}
}
pair<ll,ll> get_hash(int l, int r) {
ll h1 = (hash1[r] - hash1[l]*pow1[r-l]%mod1 + mod1)%mod1;
ll h2 = (hash2[r] - hash2[l]*pow2[r-l]%mod2 + mod2)%mod2;
return {h1, h2};
}
vector<int> find_occurrences(const string &pat) {
int n = s.size(), m = pat.size();
rabinkarp pat_hash(pat);
pair<ll,ll> hpat = pat_hash.get_hash(0, m);
vector<int> occ;
for(int i=0;i+m<=n;++i)
if(get_hash(i,i+m)==hpat) occ.push_back(i);
return occ;
}
};
struct fft {
typedef complex<double> cd;
vector<cd> roots;
vector<int> rev;
void ensure_base(int nbase) {
int sz = 1 << nbase;
if((int)roots.size() >= sz) return;
roots.resize(sz);
rev.resize(sz);
for(int i=0;i<sz;++i) {
double angle = 2 * acos(-1) * i / sz;
roots[i] = cd(cos(angle), sin(angle));
}
}
void fft_rec(vector<cd> &a, int n, bool invert) {
int N = a.size();
int L = 0;
while((1 << L) < N) ++L;
rev.resize(N);
for(int i=0;i<N;++i) {
rev[i] = 0;
for(int j=0;j<L;++j)
if(i & (1 << j))
rev[i] |= 1 << (L-1-j);
}
for(int i=0;i<N;++i)
if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int len=2; len<=N; len<<=1) {
int half = len>>1;
int diff = (int)roots.size()/len;
for(int i=0;i<N;i+=len)
for(int j=0,k=0;j<half;++j,k+=diff) {
cd u = a[i+j];
cd v = a[i+j+half]*roots[k];
a[i+j] = u+v;
a[i+j+half] = u-v;
}
}
if(invert) {
for(int i=0;i<N;++i) a[i]/=N;
reverse(a.begin()+1, a.end());
}
}
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
int need = a.size() + b.size() - 1;
int nbase = 0;
while((1<<nbase) < need) ++nbase;
ensure_base(nbase);
int sz = 1 << nbase;
vector<cd> fa(sz), fb(sz);
for(int i=0;i<(int)a.size();++i) fa[i]=a[i];
for(int i=0;i<(int)b.size();++i) fb[i]=b[i];
fft_rec(fa, sz, false);
fft_rec(fb, sz, false);
for(int i=0;i<sz;++i) fa[i]*=fb[i];
fft_rec(fa, sz, true);
vector<int> res(need);
for(int i=0;i<need;++i) res[i] = int64_t(fa[i].real() + 0.5);
return res;
}
vector<int> multiply_str(const string& s, const string& t) {
vector<int> a, b;
for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');
for(int i=t.size()-1;i>=0;--i) b.push_back(t[i]-'0');
vector<int> res = multiply(a, b);
for(int i=0;i+1<res.size();++i) {
if(res[i]>=10) {
if(i+1==res.size()) res.push_back(0);
res[i+1] += res[i]/10;
res[i] %= 10;
}
}
return res;
}
};
struct trie {
static const int ALPHABET = 26;
struct node {
int cnt;
node *children[ALPHABET];
node() : cnt(0) { memset(children, 0, sizeof(children)); }
};
node *root;
trie() { root = new node(); }
void insert(const string &s) {
node *cur = root;
for (char c : s) {
int idx = c - 'a';
if (!cur->children[idx]) cur->children[idx] = new node();
cur = cur->children[idx];
cur->cnt++;
}
}
bool search(const string &s) {
node *cur = root;
for (char c : s) {
int idx = c - 'a';
if (!cur->children[idx]) return false;
cur = cur->children[idx];
}
return true;
}
int prefix_count(const string &s) {
node *cur = root;
for (char c : s) {
int idx = c - 'a';
if (!cur->children[idx]) return 0;
cur = cur->children[idx];
}
return cur->cnt;
}
void erase(const string &s) {
erase(root, s, 0);
}
bool erase(node *cur, const string &s, int d) {
if (d == s.size()) return true;
int idx = s[d] - 'a';
if (!cur->children[idx]) return false;
if (erase(cur->children[idx], s, d+1)) {
cur->children[idx]->cnt--;
if (cur->children[idx]->cnt == 0) {
delete cur->children[idx];
cur->children[idx] = nullptr;
}
}
return false;
}
};
struct hashtable {
static const int CAP = 200003;
vector<pair<int, int>> table;
vector<bool> used;
hashtable() : table(CAP, {-1, -1}), used(CAP, false) {}
int hash(int key) const {
return ((key % CAP) + CAP) % CAP;
}
void insert(int key, int value) {
int idx = hash(key);
while (used[idx] && table[idx].first != key) {
idx = (idx + 1) % CAP;
}
table[idx] = {key, value};
used[idx] = true;
}
bool contains(int key) const {
int idx = hash(key);
int start = idx;
while (used[idx]) {
if (table[idx].first == key)
return true;
idx = (idx + 1) % CAP;
if (idx == start) break;
}
return false;
}
int get(int key) const {
int idx = hash(key);
int start = idx;
while (used[idx]) {
if (table[idx].first == key)
return table[idx].second;
idx = (idx + 1) % CAP;
if (idx == start) break;
}
return -1;
}
void erase(int key) {
int idx = hash(key);
int start = idx;
while (used[idx]) {
if (table[idx].first == key) {
used[idx] = false;
table[idx] = {-1, -1};
return;
}
idx = (idx + 1) % CAP;
if (idx == start) break;
}
}
void clear() {
fill(table.begin(), table.end(), make_pair(-1, -1));
fill(used.begin(), used.end(), false);
}
int size() const {
int cnt = 0;
for (int i = 0; i < CAP; ++i) if (used[i]) cnt++;
return cnt;
}
};
struct redblacktree {
enum Color { RED, BLACK };
struct Node {
int key, count, subtree_size;
Color color;
Node *left, *right, *parent;
Node(int k) : key(k), count(1), subtree_size(1), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
Node* root;
redblacktree() : root(nullptr) {}
void update(Node* x) {
if (!x) return;
x->subtree_size = x->count;
if (x->left) x->subtree_size += x->left->subtree_size;
if (x->right) x->subtree_size += x->right->subtree_size;
}
void left_rotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left) y->left->parent = x;
y->parent = x->parent;
if (!x->parent) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
update(x);
update(y);
}
void right_rotate(Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right) x->right->parent = y;
x->parent = y->parent;
if (!y->parent) root = x;
else if (y == y->parent->left) y->parent->left = x;
else y->parent->right = x;
x->right = y;
y->parent = x;
update(y);
update(x);
}
void insert(int key) {
Node* z = root;
Node* p = nullptr;
while (z) {
p = z;
z->subtree_size++;
if (key == z->key) { z->count++; return; }
else if (key < z->key) z = z->left;
else z = z->right;
}
Node* n = new Node(key);
n->parent = p;
if (!p) root = n;
else if (key < p->key) p->left = n;
else p->right = n;
insert_fix(n);
}
void insert_fix(Node* z) {
while (z->parent && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
left_rotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(z->parent->parent);
}
} else {
Node* y = z->parent->parent->left;
if (y && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
Node* find(int key) const {
Node* x = root;
while (x) {
if (key == x->key) return x;
else if (key < x->key) x = x->left;
else x = x->right;
}
return nullptr;
}
void erase(int key) {
Node* z = find(key);
if (!z) return;
if (z->count > 1) { z->count--; erase_update_up(z); return; }
erase_update_up(z);
Node* y = z;
Color y_original = y->color;
Node* x;
if (!z->left) {
x = z->right;
transplant(z, z->right);
} else if (!z->right) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
y_original = y->color;
x = y->right;
if (y->parent == z) {
if (x) x->parent = y;
} else {
transplant(y, y->right);
y->right = z->right;
if (y->right) y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
if (y->left) y->left->parent = y;
y->color = z->color;
update(y);
}
if (y_original == BLACK) erase_fix(x, z->parent);
delete z;
}
void erase_update_up(Node* z) {
while (z) {
update(z);
z = z->parent;
}
}
void erase_fix(Node* x, Node* p) {
while ((x != root) && (!x || x->color == BLACK)) {
if (x == (p ? p->left : nullptr)) {
Node* w = (p ? p->right : nullptr);
if (w && w->color == RED) {
w->color = BLACK;
p->color = RED;
left_rotate(p);
w = (p ? p->right : nullptr);
}
if ((!w || ((!(w->left) || w->left->color == BLACK) && (!(w->right) || w->right->color == BLACK)))) {
if (w) w->color = RED;
x = p;
if (x) p = x->parent;
} else {
if (!(w->right) || w->right->color == BLACK) {
if (w && w->left) w->left->color = BLACK;
if (w) w->color = RED;
right_rotate(w);
w = (p ? p->right : nullptr);
}
if (w) w->color = p->color;
if (p) p->color = BLACK;
if (w && w->right) w->right->color = BLACK;
left_rotate(p);
x = root;
break;
}
} else {
Node* w = (p ? p->left : nullptr);
if (w && w->color == RED) {
w->color = BLACK;
p->color = RED;
right_rotate(p);
w = (p ? p->left : nullptr);
}
if ((!w || ((!(w->left) || w->left->color == BLACK) && (!(w->right) || w->right->color == BLACK)))) {
if (w) w->color = RED;
x = p;
if (x) p = x->parent;
} else {
if (!(w->left) || w->left->color == BLACK) {
if (w && w->right) w->right->color = BLACK;
if (w) w->color = RED;
left_rotate(w);
w = (p ? p->left : nullptr);
}
if (w) w->color = p->color;
if (p) p->color = BLACK;
if (w && w->left) w->left->color = BLACK;
right_rotate(p);
x = root;
break;
}
}
}
if (x) x->color = BLACK;
}
void transplant(Node* u, Node* v) {
if (!u->parent) root = v;
else if (u == u->parent->left) u->parent->left = v;
else u->parent->right = v;
if (v) v->parent = u->parent;
if (v) update(v);
if (u->parent) update(u->parent);
}
Node* minimum(Node* x) const {
while (x && x->left) x = x->left;
return x;
}
Node* maximum(Node* x) const {
while (x && x->right) x = x->right;
return x;
}
Node* lower_bound(int key) const {
Node* x = root;
Node* res = nullptr;
while (x) {
if (x->key >= key) { res = x; x = x->left; }
else x = x->right;
}
return res;
}
Node* upper_bound(int key) const {
Node* x = root;
Node* res = nullptr;
while (x) {
if (x->key > key) { res = x; x = x->left; }
else x = x->right;
}
return res;
}
Node* predecessor(Node* x) const {
if (x->left) return maximum(x->left);
Node* y = x->parent;
while (y && x == y->left) {
x = y;
y = y->parent;
}
return y;
}
Node* successor(Node* x) const {
if (x->right) return minimum(x->right);
Node* y = x->parent;
while (y && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
int next(int key) const {
Node* n = find(key);
Node* s = successor(n);
return s ? s->key : INT_MAX;
}
int prev(int key) const {
Node* n = find(key);
Node* p = predecessor(n);
return p ? p->key : INT_MIN;
}
int count(int key) const {
Node* n = find(key);
return n ? n->count : 0;
}
int size() const { return root ? root->subtree_size : 0; }
int rank(int key) const {
Node* x = root; int r = 0;
while (x) {
if (key < x->key) x = x->left;
else {
int left_size = x->left ? x->left->subtree_size : 0;
r += left_size + x->count * (x->key <= key);
x = x->right;
}
}
return r;
}
int select(int k) const {
Node* x = root;
while (x) {
int left_size = x->left ? x->left->subtree_size : 0;
if (k <= left_size) x = x->left;
else if (k > left_size + x->count) { k -= left_size + x->count; x = x->right; }
else return x->key;
}
return INT_MIN;
}
void inorder() const { inorder(root); cout << endl; }
void inorder(Node* x) const { if (!x) return; inorder(x->left); for (int i = 0; i < x->count; i++) cout << x->key << " "; inorder(x->right); }
void print_tree(Node* n, int depth = 0) const {
if (!n) return;
print_tree(n->right, depth + 1);
for (int i = 0; i < depth; ++i) cout << " ";
cout << n->key << (n->color == RED ? "R" : "B") << " (" << n->subtree_size << ")\n";
print_tree(n->left, depth + 1);
}
void print() const { print_tree(root); }
void clear() { clear(root); root = nullptr; }
void clear(Node* x) { if (!x) return; clear(x->left); clear(x->right); delete x; }
int range_count(int l, int r) const {
return rank(r) - rank(l - 1);
}
bool is_bst(Node* n, int mn, int mx) const {
if (!n) return true;
if (n->key < mn || n->key > mx) return false;
return is_bst(n->left, mn, n->key - 1) && is_bst(n->right, n->key + 1, mx);
}
bool is_bst() const { return is_bst(root, INT_MIN, INT_MAX); }
int height(Node* n = nullptr) const {
if (!n) n = root;
if (!n) return 0;
return 1 + max(height(n->left), height(n->right));
}
};
struct llint {
long long x;
llint(long long v = 0) : x(v) {}
operator long long() const { return x; }
llint& operator=(long long v) { x = v; return *this; }
llint operator+(const llint& b) const { return x + b.x; }
llint operator-(const llint& b) const { return x - b.x; }
llint operator*(const llint& b) const { return x * b.x; }
llint operator/(const llint& b) const { return x / b.x; }
llint operator%(const llint& b) const { return x % b.x; }
llint& operator+=(const llint& b) { x += b.x; return *this; }
llint& operator-=(const llint& b) { x -= b.x; return *this; }
llint& operator*=(const llint& b) { x *= b.x; return *this; }
llint& operator/=(const llint& b) { x /= b.x; return *this; }
llint& operator%=(const llint& b) { x %= b.x; return *this; }
llint operator-() const { return -x; }
llint operator++(int) { llint tmp = *this; ++x; return tmp; }
llint operator--(int) { llint tmp = *this; --x; return tmp; }
llint& operator++() { ++x; return *this; }
llint& operator--() { --x; return *this; }
bool operator==(const llint& b) const { return x == b.x; }
bool operator!=(const llint& b) const { return x != b.x; }
bool operator<(const llint& b) const { return x < b.x; }
bool operator>(const llint& b) const { return x > b.x; }
bool operator<=(const llint& b) const { return x <= b.x; }
bool operator>=(const llint& b) const { return x >= b.x; }
friend ostream& operator<<(ostream& os, const llint& v) { return os << v.x; }
llint abs() const { return x < 0 ? -x : x; }
llint pow(llint k) const { llint res = 1, a = x; while (k.x) { if (k.x & 1) res *= a; a *= a; k.x >>= 1; } return res; }
llint gcd(const llint& b) const { return b.x ? llint(__gcd(x, b.x)) : *this; }
llint lcm(const llint& b) const { return x / gcd(b).x * b.x; }
void swap(llint& b) { std::swap(x, b.x); }
};
inline istream& operator>>(istream& is, llint& v) { is >> v.x; return is; }
template<typename T>
bool chmin(T &a, const T &b) {
return (b < a) ? (a = b, true) : false;
}
template<typename T>
bool chmax(T &a, const T &b) {
return (b > a) ? (a = b, true) : false;
}
int divceil(int a, int b) {
return a / b + (a % b != 0);
}
int pct(int x) { return __builtin_popcount(x); }
int bits(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(pll x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first ^ (x.second << 1)) + FIXED_RANDOM;
}
};
template<typename T>
struct sparse_table {
vector<vector<T>> st;
vector<int> log;
T (*merge)(T, T);
sparse_table(const vector<T>& v, T (*f)(T, T)) : merge(f) {
int n = v.size();
int K = 32 - __builtin_clz(n);
st.assign(K, vector<T>(n));
log.assign(n + 1, 0);
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
st[0] = v;
for (int j = 1; j < K; j++)
for (int i = 0; i + (1 << j) <= n; i++)
st[j][i] = merge(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
T query(int l, int r) {
int j = log[r - l + 1];
return merge(st[j][l], st[j][r - (1 << j) + 1]);
}
};
struct Edge{
int u,v,w;
};
signed main(){
fastio;
int t = 1;
//cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<Edge> edges(m + 1);
vpii g[n + 1];
for (int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
edges[i] = {u, v, w};
g[u].pb({v, i});
g[v].pb({u, i});
}
int q;
cin >> q;
while(q--){
int type;
cin >> type;
if(type == 1){
int b, r;
cin >> b >> r;
edges[b].w = r;
}
else{
int s, w;
cin >> s >> w;
vb vis(n + 1, false);
queue<int> qu;
vis[s] = true;
qu.push(s);
int cnt = 0;
while(!qu.empty()){
int u = qu.front();
qu.pop();
cnt++;
for(auto &p : g[u]){
int v = p.ff;
int id = p.ss;
if(!vis[v] and edges[id].w >= w){
vis[v] = true;
qu.push(v);
}
}
}
cout << cnt << endl;
}
}
}
}
