//████████╗██╗███╗░░██╗ ██╗░░░░░███████╗
//╚══██╔══╝██║████╗░██║ ██║░░░░░██╔════╝
//░░░██║░░░██║██╔██╗██║ ██║░░░░░█████╗░░
//░░░██║░░░██║██║╚████║ ██║░░░░░██╔══╝░░
//░░░██║░░░██║██║░╚███║ ███████╗███████╗
//░░░╚═╝░░░╚═╝╚═╝░░╚══╝ ╚══════╝╚══════╝
// __________________
// | ________________ |
// || ____ ||
// || /\ | ||
// || /__\ | ||
// || / \ |____ ||
// ||________________||
// |__________________|
// \###################\
// \###################\
// \ ____ \
// \_______\___\_______\
// An AC a day keeps the doctor away.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#include <functional>
#include <numeric>
#include <stack>
#include <array>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define vt vector
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define ub upper_bound
#define lb lower_bound
#define db double
#define ld long db
#define ll long long
#define ull unsigned long long
#define vll vt<ll>
#define vvll vt<vll>
#define pll pair<ll, ll>
#define vpll vt<pll>
#define vvpll vt<vpll>
#define vc vt<char>
#define vvc vt<vc>
#define vi vt<int>
#define vvi vt<vi>
#define vvvi vt<vvi>
#define pii pair<int, int>
#define vpii vt<pii>
#define vs vt<string>
#define vvs vt<vs>
#define vb vt<bool>
#define vvb vt<vb>
#define vvpii vt<vpii>
#define vd vt<db>
#define ar(x) array<int, x>
#define var(x) vt<ar(x)>
#define vvar(x) vt<var(x)>
#define al(x) array<ll, x>
#define vall(x) vt<al(x)>
#define vvall(x) vt<vall(x)>
#define mset(m, v) memset(m, v, sizeof(m))
#define pb push_back
#define ff first
#define ss second
#define sv string_view
#define MP make_pair
#define MT make_tuple
#define rsz resize
#define sum(x) (ll)accumulate(all(x), 0LL)
#define srt(x) sort(all(x))
#define srtR(x) sort(allr(x))
#define srtU(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
#define SORTED(x) is_sorted(all(x))
#define rev(x) reverse(all(x))
#define MAX(a) *max_element(all(a))
#define MIN(a) *min_element(all(a))
#define ROTATE(a, p) rotate(begin(a), begin(a) + p, end(a))
#define i128 __int128
//SGT DEFINE
#define lc i * 2 + 1
#define rc i * 2 + 2
#define lp lc, left, middle
#define rp rc, middle + 1, right
#define entireTree 0, 0, n - 1
#define midPoint left + (right - left) / 2
#define pushDown push(i, left, right)
#define iter int i, int left, int right
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
struct custom {
static const uint64_t C = 0x9e3779b97f4a7c15; const uint32_t RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
size_t operator()(const std::string& s) const { size_t hash = std::hash<std::string>{}(s); return hash ^ RANDOM; } };
template <class K, class V> using umap = std::unordered_map<K, V, custom>; template <class K> using uset = std::unordered_set<K, custom>;
template<class T> using max_heap = priority_queue<T>;
template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& arr) {
for (size_t i = 0; i < N; i++) { is >> arr[i]; } return is;
}
template<typename T, size_t N>
istream& operator>>(istream& is, vector<array<T, N>>& vec) {
for (auto &arr : vec) { is >> arr; } return is;
}
inline std::ostream& operator<<(std::ostream& os, i128 x) {
if(x == 0) { os << '0'; return os; } if(x < 0) { os << '-'; x = -x; }
string s; while (x > 0) { int digit = int(x % 10); s.pb(char('0' + digit)); x /= 10; }
rev(s); os << s; return os;
}
template <typename T1, typename T2> istream &operator>>(istream& in, pair<T1, T2>& input) { return in >> input.ff >> input.ss; }
template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &el : v) in >> el; return in; }
template<class T>
void output_vector(vt<T>& a, int off_set = 0) {
int n = a.size();
for(int i = off_set; i < n; i++) {
cout << a[i] << (i == n - 1 ? '\n' : ' ');
}
}
template<typename T, typename Compare>
vi closest_left(const vt<T>& a, Compare cmp) {
int n = a.size(); vi closest(n); iota(all(closest), 0);
for (int i = 0; i < n; i++) {
auto& j = closest[i];
while(j && cmp(a[i], a[j - 1])) j = closest[j - 1];
}
return closest;
}
template<typename T, typename Compare> // auto right = closest_right<int>(a, std::less<int>());
vi closest_right(const vt<T>& a, Compare cmp) {
int n = a.size(); vi closest(n); iota(all(closest), 0);
for (int i = n - 1; i >= 0; i--) {
auto& j = closest[i];
while(j < n - 1 && cmp(a[i], a[j + 1])) j = closest[j + 1];
}
return closest;
}
template<typename T, typename V = string>
vt<pair<T, int>> encode(const V& s) {
vt<pair<T, int>> seg;
for(auto& ch : s) {
if(seg.empty() || ch != seg.back().ff) seg.pb({ch, 1});
else seg.back().ss++;
}
return seg;
}
template<typename K, typename V>
auto operator<<(std::ostream &o, const std::map<K, V> &m) -> std::ostream& {
o << "{"; int i = 0;
for (const auto &[key, value] : m) { if (i++) o << " , "; o << key << " : " << value; }
return o << "}";
}
#ifdef LOCAL
#define debug(x...) debug_out(#x, x)
void debug_out(const char* names) { std::cerr << std::endl; }
template <typename T, typename... Args>
void debug_out(const char* names, T value, Args... args) {
const char* comma = strchr(names, ',');
std::cerr << "[" << (comma ? std::string(names, comma) : names) << " = " << value << "]";
if (sizeof...(args)) { std::cerr << ", "; debug_out(comma + 1, args...); }
else { std::cerr << std::endl; }
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& o, const std::pair<T1, T2>& p) { return o << "{" << p.ff << " , " << p.ss << "}"; }
auto operator<<(auto &o, const auto &x) -> decltype(end(x), o) {
o << "{"; int i = 0; for (const auto &e : x) { if (i++) o << " , "; o << e; } return o << "}";
} // remove for leetcode
#include <sys/resource.h>
#include <sys/time.h>
void printMemoryUsage() {
struct rusage usage;
getrusage(RUSAGE_SELF, &usage);
double memoryMB = usage.ru_maxrss / 1024.0;
cerr << "Memory usage: " << memoryMB << " MB" << "\n";
}
#define startClock clock_t tStart = clock();
#define endClock std::cout << std::fixed << std::setprecision(10) << "\nTime Taken: " << (double)(clock() - tStart) / CLOCKS_PER_SEC << " seconds" << std::endl;
#else
#define debug(...)
#define startClock
#define endClock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define eps 1e-9
#define M_PI 3.14159265358979323846
const static string pi = "3141592653589793238462643383279";
const static ll INF = 1LL << 62;
const static int inf = 1e9 + 100;
const static int MK = 20;
const static int MX = 1e5 + 5;
ll gcd(ll a, ll b) { while (b != 0) { ll temp = b; b = a % b; a = temp; } return a; }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll floor(ll a, ll b) { if(b < 0) a = -a, b = -b; if (a >= 0) return a / b; return a / b - (a % b ? 1 : 0); }
ll ceil(ll a, ll b) { if (b < 0) a = -a, b = -b; if (a >= 0) return (a + b - 1) / b; return a / b; }
int pct(ll x) { return __builtin_popcountll(x); }
ll have_bit(ll x, int b) { return x & (1LL << b); }
int min_bit(ll x) { return __builtin_ctzll(x); }
int max_bit(ll x) { return 63 - __builtin_clzll(x); }
const vvi dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}}; // UP, DOWN, LEFT, RIGHT
const vvi knight_dirs = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; // knight dirs
const vc dirChar = {'U', 'D', 'L', 'R'};
int modExpo(ll base, ll exp, ll mod) { ll res = 1; base %= mod; while(exp) { if(exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; }
ll extended_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll d = extended_gcd(b, a % b, y, x); y -= (a / b) * x; return d; }
int modExpo_on_string(ll a, string exp, int mod) { ll b = 0; for(auto& ch : exp) b = (b * 10 + (ch - '0')) % (mod - 1); return modExpo(a, b, mod); }
ll sum_even_series(ll n) { return (n / 2) * (n / 2 + 1);}
ll sum_odd_series(ll n) {return n - sum_even_series(n);} // sum of first n odd number is n ^ 2
ll sum_of_square(ll n) { return n * (n + 1) * (2 * n + 1) / 6; } // sum of 1 + 2 * 2 + 3 * 3 + 4 * 4 + ... + n * n
string make_lower(const string& t) { string s = t; transform(all(s), s.begin(), [](unsigned char c) { return tolower(c); }); return s; }
string make_upper(const string&t) { string s = t; transform(all(s), s.begin(), [](unsigned char c) { return toupper(c); }); return s; }
ll sqrt(ll n) { ll t = sqrtl(n); while(t * t < n) t++; while(t * t > n) t--; return t;}
template<typename T> T geometric_sum(ll n, ll k) { return (1 - T(n).pow(k + 1)) / (1 - n); } // return n^1 + n^2 + n^3 + n^4 + n^5 + ... + n^k
template<typename T> T geometric_power(ll p, ll k) { return (T(p).pow(k + 1) - 1) / T(p - 1); } // p^1 + p^2 + p^3 + ... + p^k
bool is_perm(ll sm, ll square_sum, ll len) {return sm == len * (len + 1) / 2 && square_sum == len * (len + 1) * (2 * len + 1) / 6;} // determine if an array is a permutation base on sum and square_sum
bool is_vowel(char c) {return c == 'a' || c == 'e' || c == 'u' || c == 'o' || c == 'i';}
template<int N>
class Bitset {
private:
constexpr static ull LM = (1ull<<32) - 1;
constexpr static ull FM = ~0ull;
constexpr static int H = (N + 63) >> 6;
array<ull, H> bits;
static constexpr ull getBit(int i, ull v = 1) { return v << (i & 63); }
Bitset<N> shiftLeft(int d) {
Bitset<N> res(-1);
int s = min(d >> 6, H), r = d & 63;
for (int i = 0; i < s; ++i) res.bits[i] = 0;
if (r == 0) for (int i = s; i < H; ++i) res.bits[i] = bits[i - s];
else {
if (s < H) res.bits[s] = bits[0] << r;
for (int i = s + 1; i < H; ++i) res.bits[i] = (bits[i - s] << r) | (bits[i-1 - s] >> (64 - r));
}
return res;
}
Bitset<N> shiftRight(int d) {
Bitset<N> res(-1);
int s = min(d >> 6, H), r = d & 63;
for (int i = H-1; i >= H - (int)s; --i) res.bits[i] = 0;
if (r == 0) for (int i = H-1 - (int)s; i >= 0; --i) res.bits[i] = bits[i + s];
else {
if (s < H) res.bits[H-1-s] = bits[H-1] >> r;
for (int i = H-2 - (int)s; i >= 0; --i) res.bits[i] = (bits[i + s] >> r) | (bits[i+1 + s] << (64 - r));
}
return res;
}
// Lexicographic comparison on bits in bitset
bool lexCompare(const Bitset<N>& rhs) const {
for (int i = 0; i < H; ++i) {
if (bits[i] != rhs.bits[i]) {
ull tmp = bits[i] ^ rhs.bits[i];
int j = __builtin_ctzll(tmp);
if ((N & 63) && ((i << 6) + j >= N)) return false;
return rhs.bits[i] & (1ull << j);
}
}
return false;
}
// Numeric comparison on \sum_i 2^i bit[i]
bool numCompare(const Bitset<N>& rhs) const {
for (int i = H-1; i >= 0; --i) {
if (bits[i] != rhs.bits[i]) {
if ((N & 63) && (i == H-1)) {
ull mask = ((1ull << (N & 63)) - 1);
ull tmp1 = bits[H-1] & mask;
ull tmp2 = rhs.bits[H-1] & mask;
if (tmp1 != tmp2) return tmp1 < tmp2;
} else return bits[i] < rhs.bits[i];
}
}
return false;
}
public:
void clear() { for (ull& v : bits) v = 0; }
void set() { for (ull& v : bits) v = FM; }
void flip() { for (ull& v : bits) v = ~v; }
Bitset(int ini_v = 0) {
if (ini_v == 0) clear();
else if (ini_v == 1) set();
}
bool get(uint i) const { return bits[i>>6] & getBit(i); }
void set(uint i, ull v) { bits[i>>6] = (bits[i>>6] & ~getBit(i)) | getBit(i, v); }
void setZero(uint i) { bits[i>>6] &= ~getBit(i); }
void setOne(uint i) { bits[i>>6] |= getBit(i); }
// Sets bit[a + i] = ((v >> i) & 1) for 0 <= i <= b-a. MUST HAVE 0 <= v < 2^{b-a+1} AND 0 <= a <= b < min(a + 64, N)
void setRange(uint a, uint b, ull v) {
uint j = (a >> 6), r = (a & 63), len = b-a+1;
ull mask = FM >> (64 - len);
bits[j] = (bits[j] & ~(mask << r)) | (v << r);
if ((b >> 6) > j) bits[j + 1] = (bits[j + 1] & ~(mask >> (64 - r))) | (v >> (64 - r));
}
// Returns v = \sum_{i = 0}^{b-a} 2^i * bit[a + i]. MUST HAVE 0 <= a <= b < min(a + 64, N)
ull getRange(uint a, uint b) const {
uint j = (a >> 6), r = (a & 63), len = b-a+1;
ull mask = FM >> (64 - len);
if ((b >> 6) <= j) return (bits[j] >> r) & mask;
return ((bits[j] >> r) | (bits[j+1] << (64 - r))) & mask;
}
// Returns minimum a <= i <= b such that bit[i] = 1. Returns or b + 1 if none exist
int findNext(int a, int b = N-1) const {
int j = (a >> 6);
ull tmp = bits[j] >> (a & 63);
if (tmp != 0) return min(b + 1, a + __builtin_ctzll(tmp));
for (++j; (j << 6) <= b; ++j) {
if (bits[j]) return min(b + 1, (j << 6) + __builtin_ctzll(bits[j]));
}
return b + 1;
}
// Returns maximum i \in [a, b] such that bits[i] = 1, or a - 1 if none exist
int findPrev(int b, int a = 0) const {
int j = (b >> 6);
ull tmp = bits[j] << (63 - (b & 63));
if (tmp != 0) return (int)max(a, b+1 - __builtin_clzll(tmp)) - 1;
for (--j; ((j + 1) << 6) > a; --j) {
if (bits[j]) return (int)max(a, ((j + 1) << 6) - __builtin_clzll(bits[j])) - 1;
}
return (int)a - 1;
}
// Counts set bits in range [a, b]
int count(int a = 0, int b = N-1) const {
int res = 0;
if (a & 63) res -= __builtin_popcountll(bits[a >> 6] << (64 - (a & 63)));
if ((b + 1) & 63) res -= __builtin_popcountll(bits[b >> 6] >> ((b + 1) & 63));
for (int j = (a >> 6); j <= (b >> 6); ++j) res += __builtin_popcountll(bits[j]);
return res;
}
bool operator==(const Bitset<N>& rhs) const {
for (int i = 0; i < H; ++i) {
if (bits[i] != rhs.bits[i]) {
return !(N & 63) || (i < H-1) || !((bits[i] ^ rhs.bits[i]) & ((1ull << (N & 63)) - 1));
}
}
return false;
}
Bitset<N> operator~() const {
Bitset<N> res(-1);
for (int i = 0; i < H; ++i) res.bits[i] = ~bits[i];
return res;
}
Bitset<N> operator|(const Bitset& rhs) const {
Bitset<N> res(-1);
for (int i = 0; i < H; ++i) res.bits[i] = bits[i] | rhs.bits[i];
return res;
}
Bitset<N> operator&(const Bitset& rhs) const {
Bitset<N> res(-1);
for (int i = 0; i < H; ++i) res.bits[i] = bits[i] & rhs.bits[i];
return res;
}
Bitset<N> operator^(const Bitset& rhs) const {
Bitset<N> res(-1);
for (int i = 0; i < H; ++i) res.bits[i] = bits[i] ^ rhs.bits[i];
return res;
}
Bitset operator+(const Bitset& rhs) const {
Bitset<N> res(-1);
uint8_t carry = 0;
for (int i = 0; i < H; ++i) carry = _addcarry_u64(carry, bits[i], rhs.bits[i], res.bits[i]);
return res;
}
Bitset operator-(const Bitset& rhs) const {
Bitset<N> res(-1);
uint8_t borrow = 0;
for (int i = 0; i < H; ++i) borrow = _subborrow_u64(borrow, bits[i], rhs.bits[i], res.bits[i]);
return res;
}
/*
// To make this work like a bitset
bool operator<(const Bitset<N>& rhs) { return lexCompare(rhs); }
Bitset<N> operator<<(int d) const { return leftShift(d); }
Bitset<N> operator>>(int d) const { return rightShift(d); }
*/
/*
// To make this work like a bigint
bool operator<(const Bitset<N>& rhs) { return numCompare(rhs); }
Bitset<N> operator<<(int d) const { return rightShift(d); }
Bitset<N> operator>>(int d) const { return leftShift(d); }
*/
};
// van Emde Boas tree. Maintains a set of integers in range [0, 2^B) and supports operations
// findNext(i): returns minimum j >= i in set, or 2^B if none exist
// findPrev(i): returns maximum j <= i in set, or -1 if none exist
// insert(i), erase(i): insert/erase i into the set
// empty(): returns TRUE if the set is empty
// clear(): empties the set
// init(bts): inits the set, after the call i will be in the set if bts[i] = 1. bts should be a bitset, but can be a vector of 0/1
// All operations except empty, clear and init are O(log B) = O(log log 2^B) with good constants
template<int B, typename ENABLE = void>
class VEBTree {
private:
const static int K = B / 2, R = (B + 1) / 2, M = (1 << B);
const static int S = 1 << K, MASK = (1 << R) - 1;
array<VEBTree<R>, S> ch;
VEBTree<K> act;
int mi, ma;
public:
bool empty() const { return ma < mi; }
int findNext(int i) const {
if (i <= mi) return mi;
if (i > ma) return M;
int j = i >> R, x = i & MASK;
int res = ch[j].findNext(x);
if (res <= MASK) return (j << R) + res;
j = act.findNext(j + 1);
return (j >= S) ? ma : ((j << R) + ch[j].findNext(0));
}
int findPrev(int i) const {
if (i >= ma) return ma;
if (i < mi) return -1;
int j = i >> R, x = i & MASK;
int res = ch[j].findPrev(x);
if (res >= 0) return (j << R) + res;
j = act.findPrev(j - 1);
return (j < 0) ? mi : ((j << R) + ch[j].findPrev(MASK));
}
void insert(int i) {
if (i <= mi) {
if (i == mi) return;
swap(mi, i);
if (i == M) ma = mi; // we were empty
if (i >= ma) return; // we had mi == ma
} else if (i >= ma) {
if (i == ma) return;
swap(ma, i);
if (i <= mi) return; // we had mi == ma
}
int j = i >> R;
if (ch[j].empty()) act.insert(j);
ch[j].insert(i & MASK);
}
void erase(int i) {
if (i <= mi) {
if (i < mi) return;
i = mi = findNext(mi + 1);
if (i >= ma) {
if (i > ma) ma = -1; // we had mi == ma
return; // after erase we have mi == ma
}
} else if (i >= ma) {
if (i > ma) return;
i = ma = findPrev(ma - 1);
if (i <= mi) return; // after erase we have mi == ma
}
int j = i >> R;
ch[j].erase(i & MASK);
if (ch[j].empty()) act.erase(j);
}
void clear() {
mi = M, ma = -1;
act.clear();
for (int i = 0; i < S; ++i) ch[i].clear();
}
template<class T>
void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
s0 = -shift + bts.findNext(shift + s0, shift + M-1 - s1);
s1 = M-1 - (-shift + bts.findPrev(shift + M-1-s1, shift + s0));
if (s0 + s1 >= M) clear();
else {
act.clear();
mi = s0, ma = M-1 - s1;
++s0; ++s1;
for (int j = 0; j < S; ++j) {
ch[j].init(bts, shift + (j << R), max(0, s0 - (j << R)), max(0, s1 - ((S-1-j) << R)));
if (! ch[j].empty()) act.insert(j);
}
}
}
};
template<int B>
class VEBTree<B, enable_if_t<(B <= 6)>> {
private:
const static int M = (1 << B);
ull act;
public:
bool empty() const { return !act; }
void clear() { act = 0; }
int findNext(int i) const {
return ((i < M) && (act >> i)) ? i + __builtin_ctzll(act >> i) : M;
}
int findPrev(int i) const {
return ((i != -1) && (act << (63 - i))) ? i - __builtin_clzll(act << (63 - i)) : -1;
}
void insert(int i) { act |= 1ull << i; }
void erase(int i) { act &= ~(1ull << i); }
template<class T>
void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
if (s0 + s1 >= M) act = 0;
else act = bts.getRange(shift + s0, shift + M-1-s1) << s0;
}
};
struct FastIO {
private:
const static int K = 1 << 15;
array<array<char, 4>, 10000> num_strs;
array<int, 10000> skip_chs;
array<char, K> in_buf, out_buf;
int in_fd, out_fd, in_x = K, out_x = 0;
void refillBuffer() {
if (in_x < K) {
memmove(in_buf.data(), in_buf.data() + in_x, K - in_x);
in_x = K - in_x;
} else in_x = 0;
read(in_fd, in_buf.data() + in_x, K - in_x);
in_x = 0;
}
void flush() {
if (out_x) write(out_fd, out_buf.data(), out_x);
out_x = 0;
}
public:
FastIO(FILE* in = stdin, FILE* out = stdout) : in_fd(fileno(in)), out_fd(fileno(out)) {
for (int x = 0; x < num_strs.size(); ++x) {
skip_chs[x] = 0;
for (int i = 0, tmp = x; i < 4; ++i, tmp /= 10) {
if (tmp == 0 && (x > 0 || i > 0)) skip_chs[x] = max(skip_chs[x], 4-i);
num_strs[x][3-i] = ('0' + (tmp % 10));
}
}
}
~FastIO() { flush(); close(out_fd); }
int readInt() {
if (in_x >= K / 2) refillBuffer();
while(in_buf[in_x] < '-') ++in_x;
int res = 0, sg = 1;
if (in_buf[in_x] == '-') sg = -1, ++in_x;
for (; in_buf[in_x] > '-'; ++in_x) res = (10 * res + (in_buf[in_x] - '0'));
return sg * res;
}
template<int N>
Bitset<N> readBinaryString() {
if (in_x >= K / 2) refillBuffer();
while(in_buf[in_x] < '0' || in_buf[in_x] > '1') ++in_x;
int j = 0;
Bitset<N> res;
while('0' <= in_buf[in_x] && in_buf[in_x] <= '1') {
res.set(j, in_buf[in_x] == '1');
++in_x, ++j;
if (in_x >= K / 2) refillBuffer();
}
return res;
}
void printChar(char c) {
out_buf[out_x] = c;
++out_x;
if (out_x >= K / 2) flush();
}
// Works for |num| < 1e8. Add additional ifs for larger |num|
void printInt(int num) {
if (num < 0) {
out_buf[out_x] = '-';
++out_x;
num *= -1;
}
if (num >= 10000) {
int hi = num / 10000;
int lo = num % 10000;
for (int i = skip_chs[hi]; i < 4; ++i, ++out_x) out_buf[out_x] = num_strs[hi][i];
for (int i = 0; i < 4; ++i, ++out_x) out_buf[out_x] = num_strs[lo][i];
} else {
for (int i = skip_chs[num]; i < 4; ++i, ++out_x) out_buf[out_x] = num_strs[num][i];
}
if (out_x >= K / 2) flush();
}
};
template<typename T = int>
class GRAPH {
public:
int n, m;
vvi dp;
vi parent, subtree;
vi tin, tout, low, ord, depth;
int timer = 0;
vt<unsigned> in_label, ascendant;
vi par_head;
unsigned cur_lab = 1;
vt<vt<T>> adj;
GRAPH() {}
GRAPH(const vt<vt<T>>& graph, int root = 0) {
adj = graph;
n = graph.size();
m = log2(n) + 1;
dp.rsz(n, vi(m, -1));
depth.rsz(n);
parent.rsz(n, -1);
subtree.rsz(n, 1);
tin.rsz(n);
tout.rsz(n);
ord.rsz(n);
dfs(root);
in_label.rsz(n);
ascendant.rsz(n);
par_head.rsz(n + 1);
sv_dfs1(root);
ascendant[root] = in_label[root];
sv_dfs2(root);
}
void dfs(int node, int par = -1) {
tin[node] = timer++;
ord[tin[node]] = node;
for (auto& nei : adj[node]) {
if (nei == par) continue;
depth[nei] = depth[node] + 1;
dp[nei][0] = node;
parent[nei] = node;
dfs(nei, node);
subtree[node] += subtree[nei];
}
tout[node] = timer - 1;
}
bool is_ancestor(int par, int child) { return tin[par] <= tin[child] && tin[child] <= tout[par]; }
void sv_dfs1(int u, int p = -1) {
in_label[u] = cur_lab++;
for(auto& v : adj[u]) if (v != p) {
sv_dfs1(v, u);
if(std::__countr_zero(in_label[v]) > std::__countr_zero(in_label[u]))
in_label[u] = in_label[v];
}
}
void sv_dfs2(int u, int p = -1) {
for(auto& v : adj[u]) if (v != p) {
ascendant[v] = ascendant[u];
if(in_label[v] != in_label[u]) {
par_head[in_label[v]] = u;
ascendant[v] += in_label[v] & -in_label[v];
}
sv_dfs2(v, u);
}
}
int lift(int u, unsigned j) const {
unsigned k = std::__bit_floor(ascendant[u] ^ j);
return k == 0 ? u : par_head[(in_label[u] & -k) | k];
}
int lca(int a, int b) {
if(is_ancestor(a, b)) return a;
if(is_ancestor(b, a)) return b;
auto [x, y] = std::minmax(in_label[a], in_label[b]);
unsigned j = ascendant[a] & ascendant[b] & -std::__bit_floor((x - 1) ^ y);
a = lift(a, j);
b = lift(b, j);
return depth[a] < depth[b] ? a : b;
}
int dist(int u, int v) {
int a = lca(u, v);
return depth[u] + depth[v] - 2 * depth[a];
}
};
GRAPH<int> g;
vi tin, tout, ord;
FastIO io;
class MO {
public:
int n, q;
int block;
vi a;
var(3) Q;
MO(vi& a, var(3)& Q) { // 1 base index array
n = a.size();
q = Q.size();
this->a = a;
this->Q = Q;
block = max(1, n / (int)sqrt(q));
}
vll queries() {
// don't forget the sorting, you might accidentally remove it
auto cmp = [&](const ar(3)& a, const ar(3)& b) -> bool {
if(a[0] / block != b[0] / block) return a[0] / block < b[0] / block;
int d = a[0] / block;
if(d & 1) return a[1] > b[1];
return a[1] < b[1];
}; sort(all(Q), cmp);
vi f(MAX(a) + 1);
ll D = 0;
auto ini = io.readBinaryString<(1 << 20)>();
VEBTree<20> s;
s.init(ini);
int cnt = 0;
auto insert = [&](int u) -> void {
if(f[u]++) return;
cnt++;
int t = tin[u];
if(cnt == 1) {
s.insert(t);
return;
}
int pre, nxt;
{
pre = s.findPrev(t);
if(pre == -1) pre = s.findPrev(n);
}
{
nxt = s.findNext(t);
if(nxt == -1 || nxt > n) nxt = s.findNext(0);
}
pre = ord[pre], nxt = ord[nxt];
D -= g.dist(pre, nxt);
D += g.dist(pre, u) + g.dist(u, nxt);
s.insert(tin[u]);
};
auto remove = [&](int u) -> void {
if(--f[u]) return;
cnt--;
int t = tin[u];
s.erase(t);
if(cnt == 0) {
return;
}
int pre, nxt;
{
pre = s.findPrev(t);
if(pre == -1) pre = s.findPrev(n);
}
{
nxt = s.findNext(t);
if(nxt == -1 || nxt > n) nxt = s.findNext(0);
}
pre = ord[pre], nxt = ord[nxt];
D -= g.dist(pre, u) + g.dist(u, nxt);
D += g.dist(pre, nxt);
};
vll res(q);
int l = 0, r = -1; // modify to 0 as needed "left = 0"
for(auto& [ql, qr, id] : Q) { // 1 base index
while(r < qr) insert(a[++r]);
while(l > ql) insert(a[--l]);
while(r > qr) remove(a[r--]);
while(l < ql) remove(a[l++]);
res[id] = D / 2 + 1;
}
return res;
}
};
void solve() {
int n, m, q;
n = io.readInt();
m = io.readInt();
q = io.readInt();
vvi graph(n);
for(int i = 1; i < n; i++) {
int u, v;
u = io.readInt();
v = io.readInt();
u--, v--;
graph[u].pb(v);
graph[v].pb(u);
}
vi c(m);
for(auto& x : c) {
x = io.readInt();
x--;
}
var(3) Q(q);
for(int i = 0; i < q; i++) {
auto& [l, r, id] = Q[i];
l = io.readInt();
r = io.readInt();
l--, r--;
id = i;
}
g = GRAPH<int>(graph);
tin = g.tin, tout = g.tout, ord = g.ord;
for(auto& x : MO(c, Q).queries()) {
cout << x << '\n';
}
}
signed main() {
// careful for overflow, check for long long, use unsigned long long for random generator
// when mle, look if problem require read in file, typically old problems
IOS;
startClock
//generatePrime();
int t = 1;
//cin >> t;
for(int i = 1; i <= t; i++) {
//cout << "Case #" << i << ": ";
solve();
}
endClock
#ifdef LOCAL
printMemoryUsage();
#endif
return 0;
}
//███████████████████████████████████████████████████████████████████████████████████████████████████████
//█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█
//█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█
//█░░▄▀░░░░░░░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░░░░░░░█
//█░░▄▀░░█████████░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░█████████
//█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░█████████
//█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░░░░░█
//█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░█
//█░░▄▀░░█████████░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░█
//█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░▄▀░░█
//█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█
//█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█
//███████████████████████████████████████████████████████████████████████████████████████████████████████
