#include <bits/stdc++.h>
using namespace std;
using Tableau = vector<vector<int>>;

// Calculates the Robinson–Schensted–Knuth mapping in O(n^2)
pair<Tableau, Tableau> rskMapping(const vector<int>& pi) {
	Tableau p, q;
	for (int ind = 0; ind < pi.size(); ++ind) {
		int cur = pi[ind];
		bool found = 0;
		for (int i = 0; i < p.size() && !found; ++i) {
			int j = upper_bound(p[i].begin(), p[i].end(), cur) - p[i].begin();
			if (j == p[i].size()) {
				p[i].push_back(cur);
				q[i].push_back(ind);
				found = 1;
			} else {
				swap(p[i][j], cur);
			}
		}
		if (! found) {
			p.emplace_back(vector<int>(1, cur));
			q.emplace_back(vector<int>(1, ind));
		}
	}
	return {p, q};
}

// Calculates the inverse of the Robinson–Schensted–Knuth mapping in O(n^2)
vector<int> rskInverse(int n, Tableau p, Tableau q) {
	vector<int> pi(n);
	for (int ind = n-1; ind >= 0; --ind) {
		int i = 0, j = 0;
		for (; i < q.size(); ++i) {
			for (j = 0; j < q[i].size() && q[i][j] != ind; ++j) {}
			if (j < q[i].size()) break;
		}

		int cur = p[i][j];
		p[i].pop_back();
		q[i].pop_back();

		for (--i; i >= 0; --i) {
			j = upper_bound(p[i].begin(), p[i].end(), cur) - p[i].begin();
			swap(p[i][j - 1], cur);
		}
		pi[ind] = cur;
	}
	return pi;
}

#include <bits/stdc++.h>
using namespace std;
using Tableau = vector<vector<int>>;

// Calculates the first k rows of P in the Robinson-Schensted-Knuth mapping in O(nk)
Tableau partialRSK(const vector<int>& pi, int k) {
	Tableau p(k);
	for (int ind = 0; ind < pi.size(); ++ind) {
		int cur = pi[ind];
		for (int i = 0; i < k; ++i) {
			int j = upper_bound(p[i].begin(), p[i].end(), cur) - p[i].begin();
			if (j < p[i].size()) swap(p[i][j], cur);
			else {
				p[i].push_back(cur);
				break;
			}
		}
	}
	while(p.back().empty()) p.pop_back();
	return p;
}

// Calculates the Robinson-Schensted-Knuth mapping in O(n sqrt(n) log(n)) time
pair<Tableau, Tableau> fastRSKMapping(vector<int> pi) {
	int n = pi.size(), k = 1;
	while(k*k < n) ++k;

	vector<int> inv_pi(n);
	for (int i = 0; i < n; ++i) inv_pi[pi[i]] = i;

	Tableau p = partialRSK(pi, k), q = partialRSK(inv_pi, k);
	reverse(pi.begin(), pi.end()); reverse(inv_pi.begin(), inv_pi.end());
	Tableau p_cols = partialRSK(pi, k), q_cols = partialRSK(inv_pi, k);

	p.resize(p_cols[0].size()); q.resize(q_cols[0].size());
	for (int i = k; i < p.size(); ++i) {
		for (int j = 0; j < p_cols.size() && p_cols[j].size() > i; ++j) {
			p[i].emplace_back(p_cols[j][i]);
			q[i].emplace_back(q_cols[j][i]);
		}
	}
	return {p, q};
}

#include <bits/stdc++.h>
using namespace std;
using Tableau = vector<vector<int>>;
using ll = long long;
const ll MOD = (ll)1e9 + 7;
ll modPow(ll a, ll b) { return (b == 0) ? 1 : ((b & 1) ? a * modPow(a, b ^ 1) % MOD : modPow(a*a % MOD, b >> 1)); }

// Calculates the number of standard Young tableau of shape lambda in O(n) using the hook-length formula
ll hookLength(int n, const vector<int>& lambda) {
	vector<int> lambda_t(lambda[0]);
	for (int i = 0, j = lambda[0]; i < n; ++i) {
		while(j >= 0 && (i + 1 == n || lambda[i+1] <= j)) lambda_t[j] = i + 1;
	}

	ll num = 1, div = 1;
	for (int i = 0; i < n; ++i) num = num * n % MOD;
	for (int i = 0; i < lambda.size(); ++i) {
		for (int j = 0; j < lambda[i]; ++j) {
			ll mult = 1 + (lambda[i] - j - 1) + (lambda_t[j] - i - 1);
			div = div * mult % MOD;
		}
	}
	return num * modPow(div, MOD - 2) % MOD;
}

Denote by $$$\lambda^-$$$ the set of partitions $$$\mu$$$ of $$$n-1$$$ such that $$$Y(\mu) \subseteq Y(\lambda)$$$. These partitions have the same Young diagram as $$$\lambda$$$ with one corner square removed.

Note that $$$c(\lambda)$$$ satisfies the recurrence $$$c(\lambda) = \sum_{\mu \in \lambda^-} c(\mu)$$$ as the maximum value has to occur in some corner cell.

We define a random walk on the Young diagram $$$Y(\lambda)$$$ of the partition. The random walk starts at a uniformly random square of $$$Y(\lambda)$$$, and in every step moves from $$$(i, j)$$$ to a uniformly random square in $$$H_\lambda(i, j) \setminus \{(i, j)\}$$$ where $$$H_\lambda(i, j)$$$ is the set of squares in $$$Y(\lambda)$$$ directly below or to the right of $$$(i, j)$$$. Thus the probability of ending up in square $$$(i', j') \in H_\lambda(i, j) \setminus \{(i, j)\}$$$ is $$$\frac{1}{h_\lambda(i, j) - 1}$$$. When $$$h_\lambda(i, j) = 1$$$, the random walk stops.

After the random walk stops, remove the square it ended up at from $$$Y$$$. We'll show that the probability that the resulting partition corresponding to the diagram after removing the square is $$$\mu \in \lambda^-$$$ with probability $$$t(\mu) / t(\lambda)$$$. Since the process always results in some $$$\mu \in \lambda^-$$$, the probabilities must sum to one, so we must then have $$$t(\lambda) = \sum_{\mu \in \lambda^-} t(\mu)$$$. Since $$$t(\mu) = c(\mu) = 1$$$ for the only partition $$$\mu$$$ of $$$1$$$, the result follows by induction.

First, note that if $$$Y(\lambda) = Y(\mu) + (i, j)$$$, we have \begin{equation} \frac{t(\mu)}{t(\lambda)} = \frac{1}{n} \prod_{k < i} \frac{h_\lambda(k, j)}{h_\lambda(k, j) — 1} \prod_{k < j} \frac{h_\lambda(i, k)}{h_\lambda(i, k) — 1} = \frac{1}{n} \prod_{k < i} \left(1 + \frac{1}{h_\lambda(k, j) — 1}\right) \prod_{k < j} \left(1 + \frac{1}{h_\lambda(i, k) — 1}\right) \end{equation}

For a random walk $$$((a_1, b_1), \dots, (a_k, b_k))$$$, let $$$A = \{a_1, \dots, a_k\}$$$ be the set of visited $$$y$$$-coordinates, and $$$B = \{b_1, \dots, b_k\}$$$ be the set of visited $$$x$$$-coordinates. Since the square the walk ends up in is $$$(a_k, b_k) = (\max A, \max B)$$$, the pair $$$(A, B)$$$ uniquely determines where the cell ends up in (though it does not uniquely determine the walk).

By $$$p(A, B | a, b)$$$, denote the probability that a random walk starting at $$$(a, b)$$$ has the given sets $$$A$$$ and $$$B$$$. If $$$\alpha = \max A$$$ and $$$\beta = \max B$$$, we claim that \begin{equation} p(A, B\ | a, b) = \prod_{i \in A \setminus \{\alpha\}} \frac{1}{h_\lambda(i, \beta) — 1} \prod_{j \in B \setminus \{\beta\}} \frac{1}{h_\lambda(\alpha, j) — 1} \end{equation} this is a easy proof by induction on $$$|A| + |B|$$$: if $$$A = \{a_1, \dots, a_k\}$$$ and $$$b = \{b_1, \dots, b_k\}$$$, $$$a_1 = a, b_1 = b$$$ and $$$a_k = \alpha, b_k = \beta$$$, \begin{equation} p(A, B\ | a, b) = \frac{1}{h_\lambda(a, b) — 1} \left(p(A \setminus \{a\}, B | a_2, b) + p(A, B \setminus \{b\} | a, b_2)\right) \end{equation} which by induction equals \begin{equation} \frac{1}{h_\lambda(a, b) — 1} \left((h_\lambda(a, \beta) — 1) + (h_\lambda(\alpha, b) — 1)\right)\prod_{i \in A \setminus \{\alpha\}} \frac{1}{h_\lambda(i, \beta) — 1} \prod_{j \in B \setminus \{\beta\}} \frac{1}{h_\lambda(\alpha, j) — 1} \end{equation} We have $$$h_\lambda(a, b) - 1 = (h_\lambda(a, \beta) - 1) + (h_\lambda(\alpha, b) - 1)$$$, thus the claimed equation for $$$p(A, B\ | a, b)$$$ holds.

Now, we are done, as \begin{equation} \sum_{a \leq \alpha, b \leq \beta} \frac{1}{n} \sum_{\stackrel{A \subseteq [n]}{\stackrel{min A = a}{max A = \alpha}}} \sum_{\stackrel{B \subseteq [n]}{\stackrel{min B = b}{max B = \beta}}} p(A, B | a, b) = \frac{1}{n} \prod_{k < \alpha} \left(1 + \frac{1}{h_\lambda(k, \beta) — 1}\right) \prod_{k < \beta} \left(1 + \frac{1}{h_\lambda(\alpha, k) — 1}\right) \end{equation} you can see this by looping $$$y$$$ from $$$\alpha$$$ to $$$1$$$ and deciding if $$$y$$$ should be in $$$A$$$, then doing the same for $$$x, \beta$$$ and $$$B$$$. The $$$\frac{1}{n}$$$ factor comes from the random selection of the starting square.

Given an array of size $$$n$$$, for $$$k = \lceil \log n \rceil$$$ we can, in $$$\mathcal{O}(n)$$$ preprocessing time, and $$$\mathcal{O}(1)$$$ query time answer range AND and range OR queries, such that the range we are querying contains at least one multiple of $$$k$$$.

To do this, we make blocks of the numbers, each containing $$$k$$$ consecutive numbers. Index the blocks as $$$0, 1, \dots, \lceil n / k \rceil$$$, and calculate $$$\text{DP-AND}[i][h] = \land_{j = i}^{i + 2^h - 1} \text{block-and}[j]$$$ and $$$\text{DP-OR}[i][h]$$$ similarly for OR. Then the AND or OR over the fully contained blocks is the AND or OR of at most two values of DP. We also calculate prefix ANDs and prefix ORs inside every block, to compute the parts from the two not-entirely-contained blocks.

Then, we apply the four Russians trick again inside the intervals of length $$$k$$$ to get intervals of length $$$k_2 = \lceil \log k \rceil$$$, then again inside those intervals to get intervals of length $$$k_3 = \lceil \log k_2 \rceil$$$, and so on.

Iterating this $$$t$$$ times gives the $$$\mathcal{O}(n)$$$ precalc $$$\mathcal{O}(\log \dots \log n)$$$ per query ($$$\log$$$ iterated some fixed number of times) algorithm. If no multiple of $$$k$$$ is contained in the query interval, we can just loop through it naively.

Since $$$k_{\log^* n} = \mathcal{O}(1)$$$, iterating $$$\mathcal{O}(\log^* n)$$$ times gives an algorithm that does $$$\mathcal{O}(\log^* n)$$$ precalculation, and answers queries in $$$\mathcal{O}(1)$$$. We do need to find the first $$$t$$$ s.t. the interval contains a multiple of $$$k_t$$$. To do this, we require $$$n$$$ to be a power of two, and all $$$k_t$$$ to also be a power of two. Then we can figure out the correct $$$t$$$ and find the location of the block in $$$\mathcal{O}(1)$$$ time by finding the highest bit that changes between the start $$$a$$$ of the query range and the end $$$b$$$ of the query range (assuming we can find the lowest set bit in $$$\mathcal{O}(1)$$$).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<ll, ll> extEucMod(ll a, ll b, ll p) {
	if (b == 0) return {1, 0};
	ll m = a / b;
	auto sub = extEucMod(b, a - b * m, p);
	return {sub.second, (sub.first - m*sub.second) % p};
}
ll modInv(ll a, ll p) {
	ll res = extEucMod(p, a, p).second;
	return (res < 0 ? res + p : res);
}
ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
ll mSub(ll a, ll b, ll m) { return (a >= b ? a - b : a - b + m); }
ll posMod(ll a, ll m) { ll res = a % m; return (res < 0 ? res + m : res); }
ll getSteps(ll t, ll ia, ll b, ll m) { return mSub(t, b, m) * ia % m; }

// Returns minimum value of ax + b (mod m) for x \in [0, k]. O(log m) time
ll minRem(ll a, ll b, ll m, ll k) {
	for (ll g = gcd(a, m); g > 1;) return g * minRem(a/g, b/g, m/g, k) + (b % g);
	for (ll b0 = b, m0 = m, ia0 = modInv(a, m), na, nb, nm; a; a = na, b = nb, m = nm) {
		if (a > m - a) {
			na = a % (m - a);
			nb = b % (m - a);
			nm = m - a;
			for (ll steps = getSteps(nb, ia0, b0, m0); steps > k;) {
				ll add = steps - getSteps(nb + nm, ia0, b0, m0);
				return nb + nm * ((steps - k + (add - 1)) / add);
			}
		} else {
			na = posMod(-m, a);
			nb = (b < a ? b : posMod(b - m, a));
			nm = a;
			if (getSteps(nb, ia0, b0, m0) > k) break;
		}
	}
	return b;
}

// Returns minimum x such that ax + b (mod m) \in [le, ri] or -1 if there is no such x. O(log m) time
ll firstInRange(ll a, ll b, ll m, ll le, ll ri) {
	for (ll g = gcd(a, m); g > 1;) return firstInRange(a/g, b/g, m/g, le/g + (le % g > b % g), ri/g - (ri % g < b % g));
	if (le > ri) return -1; // impossible
	ll ia = modInv(a, m);
	return minRem(ia, mSub(le, b, m) * ia % m, m, ri - le);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll a, b, m, le, ri;
	cin >> a >> b >> m >> le >> ri;
	cout << firstInRange(a, b, m, le, ri) << '\n';
}

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = (int)1e9 + 7;

bool findCycle(int i, vector<int>& cycle, vector<int>& par, const vector<vector<int>>& conns) {
	for (auto t : conns[i]) {
		if (par[i] == t) continue;
		if (par[t] != -1) {
			if (par[t] == i) swap(t, i);
			while(i != t) {
				cycle.push_back(i);
				i = par[i];
			}
			cycle.push_back(i);
			return true;
		} else {
			par[t] = i;
			bool found = findCycle(t, cycle, par, conns);
			if (found) return true;
		}
	}
	return false;
}

void dfs(int i, vector<int>& par, vector<int>& ban, const vector<vector<int>>& conns) {
	for (auto t : conns[i]) {
		if (par[t] != -1) continue;
		if (ban[t] != -1) continue;
		par[t] = i;
		dfs(t, par, ban, conns);
	}
}
vector<int> getDists(int s, const vector<vector<int>>& conns) {
	int n = conns.size();
	vector<int> dist(n, INF);
	dist[s] = 0;

	vector<int> que = {s};
	for (int j = 0; j < que.size(); ++j) {
		int i = que[j];
		for (auto t : conns[i]) {
			if (dist[t] == INF) {
				dist[t] = dist[i] + 1;
				que.push_back(t);
			}
		}
	}
	return dist;
}

int findClosest(const vector<int>& list, const vector<int>& dist) {
	int rd = INF;
	int ri = -1;
	for (int i = 0; i < list.size(); ++i) {
		if (dist[list[i]] < rd) {
			rd = dist[list[i]];
			ri = i;
		}
	}
	return ri;
}

void solve(int ti) {
	int n;
	cin >> n;
	vector<vector<int>> conns(n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		conns[a].push_back(b);
		conns[b].push_back(a);
	}
	int m;
	cin >> m;
	vector<int> dest(m);
	for (int i = 0; i < m; ++i) {
		cin >> dest[i];
		--dest[i];
	}

	int a, b;
	cin >> a >> b;
	--a; --b;

	vector<int> cycle;
	vector<int> par(n, -1);

	par[0] = 0;
	findCycle(0, cycle, par, conns);

	int k = cycle.size();
	vector<int> cyc_ind(n, -1);
	for (int j = 0; j < k; ++j) cyc_ind[cycle[j]] = j;

	// See if A can win without doing anything related to the cycle
	bool win = false;
	vector<int> a_dists = getDists(a, conns);
	vector<int> b_dists = getDists(b, conns);
	for (auto i : dest) {
		if (a_dists[i] <= b_dists[i]) win = true;
	}

	// See if A can win by playing in the cycle
	if (! win) {
		for (int i = 0; i < n; ++i) par[i] = -1;
		for (auto i : cycle) {
			par[i] = i;
			dfs(i, par, cyc_ind, conns);
		}
		// cyc_win[i] = true for i in cycle if branch leading to win starts from i
		vector<bool> cyc_win(n, false);
		for (auto i : dest) {
			for (int j = i; !cyc_win[j]; j = par[j]) {
				cyc_win[j] = true;
			}
		}

		// Find closest nodes in cycle for a and b
		int cai = findClosest(cycle, a_dists);
		int cbi = findClosest(cycle, b_dists);
		int ca = cycle[cai];
		int cb = cycle[cbi];
		int da = a_dists[ca];
		int db = b_dists[cb];

		// Find closest cyc_win to the left and to the right of ca
		int le_win = -1;
		int ri_win = -1;
		for (int j = cai;; j = (j-1+k)%k) {
			if (cyc_win[cycle[j]]) {
				le_win = j;
				break;
			}
		}
		for (int j = cai;; j = (j+1)%k) {
			if (cyc_win[cycle[j]]) {
				ri_win = j;
				break;
			}
		}
		
		//     A
		//     |da
		// x - x - x
		// | da1   | da2
		// lw      rw
		// | db1   | db2
		// x - x - x
		//     | db
		//     B

		int da1 = (cai - le_win + k) % k;
		int da2 = (ri_win - cai + k) % k;
		int db1 = (le_win - cbi + k) % k;
		int db2 = (cbi - ri_win + k) % k;

		if (db1 + db2 > k) {
			// A and B are on the same side
			// We need to figure out which side of A B is in
			db1 = (k - db1) % k;
			db2 = (k - db2) % k;
			int dab = abs(da1 - db1);

			if (db + dab < da) {
				win = false; // B can block A from entering cycle
			} else {
				if (db1 <= da1) {
					if (db + (k - db2) < da + da2) {
						win = false; // B can go all the way around
					} else {
						win = true;
					}
				} else {
					if (db + (k - db1) < da + da1) {
						win = false; // B can go all the way around
					} else {
						win = true;
					}
				}
			}
		} else {
			// A and B are on opposite sides
			if (db + min(da1 + db1, da2 + db2) < da) {
				win = false; // B can block A from entering cycle
			} else if (le_win == ri_win) {
				win = false; // Block messages
			} else {
				// Can B get into a position where it can get to 
				int ddif1 = db1 - da1 + 1; // Move this many times left for standstill
				int ddif2 = db2 - da2 + 1; // Move this many times right for standstill
				if (ddif1 + ddif2 <= 0 && min(0, max(ddif1, ddif2)) + db <= da) {
					win = false; // B can get to standstill
				} else {
					win = true; // A can escape standstill
				}
			}
		}
	}

	// Output result
	cout << "Case " << (ti+1) << ": ";
	if (win) cout << "Panda" << '\n';
	else cout << "Sheep\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) solve(ti);
}

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = (int)1e9 + 7;

const int N = 1010;
int win[2][N][N];
int rem[2][N][N];
vector<pair<int, pair<int, int>>> que;

void resolve(int s, int i, int j, int r) {
	if (rem[s][i][j] <= 0) return;
	win[s][i][j] = r;
	rem[s][i][j] = 0;
	que.push_back({s, {i, j}});
}

void solve(int ti) {
	int n;
	cin >> n;

	que.clear();
	for (int s = 0; s < 2; ++s) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				win[s][i][j] = 0;
				rem[s][i][j] = 0;
			}
		}
	}

	vector<vector<int>> conns(n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		conns[a].push_back(b);
		conns[b].push_back(a);
	}
	for (int i = 0; i < n; ++i) conns[i].push_back(i);

	int m;
	cin >> m;
	vector<int> dest(m);
	for (int i = 0; i < m; ++i) {
		cin >> dest[i];
		--dest[i];
	}

	int a, b;
	cin >> a >> b;
	--a; --b;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			rem[0][i][j] = conns[i].size();
			rem[1][i][j] = conns[j].size();
		}
	}

	for (auto i : dest) {
		for (int j = 0; j < n; ++j) {
			resolve(0, i, j, 1);
			if (i != j) resolve(1, i, j, 1);
		}
	}
	for (int i = 0; i < n; ++i) {
		resolve(1, i, i, -1);
	}
	for (int x = 0; x < que.size(); ++x) {
		int s = que[x].first;
		int i = que[x].second.first;
		int j = que[x].second.second;
		int r = (s ? 1 : -1);

		if (s == 0) {
			if (win[s][i][j] == r) {
				for (auto t : conns[j]) {
					resolve(s^1, i, t, r);
				}
			} else {
				for (auto t : conns[j]) {
					if (rem[s^1][i][t] == 1) resolve(s^1, i, t, -r);
					else --rem[s^1][i][t];
				}
			}
		} else {
			if (win[s][i][j] == r) {
				for (auto t : conns[i]) {
					resolve(s^1, t, j, r);
				}
			} else {
				for (auto t : conns[i]) {
					if (rem[s^1][t][j] == 1) resolve(s^1, t, j, -r);
					else --rem[s^1][t][j];
				}
			}

		}
	}

	// Output result
	bool ans = (win[0][a][b] == 1);
	cout << "Case " << (ti+1) << ": ";
	if (ans) cout << "Panda" << '\n';
	else cout << "Sheep\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) solve(ti);
}

#include <iostream>
#include <vector>
using namespace std;

struct HLD {
	vector<int> par; // Parent
	vector<int> pp; // Path parent (Highest ancestor in same heavy-edge segment)
	vector<int> ind; // HLD index (Index in the array HLD maps nodes to)

	// p: parent of node i. Must have p[i] < i (p[0] = -1).
	HLD(const vector<int>& p) : par(p), pp(p.size()), ind(p.size(), -1) {
		int n = p.size();
		vector<int> siz(n, 1); // subtree size
		for (int i = n-1; i > 0; --i) siz[par[i]] += siz[i];

		vector<int> pc(n, -1); // Preferred child
		for (int i = n-1; i > 0; --i) {
			if (2*siz[i] >= siz[par[i]]) pc[par[i]] = i;
		}

		int cur = 0; // Current position in array
		for (int i = 0; i < n; ++i) {
			if (ind[i] != -1) continue;
			for (int j = i; j != -1; j = pc[j], ++cur) {
				ind[j] = cur;
				pp[j] = i;
			}
		}
	}
	// Get intervals corresponding to path between a and b
	vector<pair<int, int>> get(int a, int b) {
		vector<pair<int, int>> res;
		while(true) {
			if (ind[b] < ind[a]) swap(a, b);
			if (ind[pp[b]] <= ind[a]) {
				res.push_back({ind[a], ind[b]});
				return res;
			} else {
				res.push_back({ind[pp[b]], ind[b]});
				b = par[pp[b]];
			}
		}
	}
};

        // Get LCA of a and b
        int lca(int a, int b) {
                while(true) {
                        if (ind[b] < ind[a]) swap(a, b); 
                        if (ind[pp[b]] <= ind[a]) return a;
                        else b = par[pp[b]];
                }
        }

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct HLD {
	vector<int> par; // Parent
	vector<int> pp; // Path parent
	vector<int> ind; // HLD index

	// p: parent of node i. Must have p[i] < i (p[0] = -1).
	HLD(const vector<int>& p) : par(p), pp(p.size()), ind(p.size(), -1) {
		int n = p.size();
		vector<int> siz(n, 1); // subtree size
		for (int i = n-1; i > 0; --i) siz[par[i]] += siz[i];

		vector<int> pc(n, -1); // Preferred child
		for (int i = n-1; i > 0; --i) {
			if (2*siz[i] >= siz[par[i]]) pc[par[i]] = i;
		}

		int cur = 0; // Current position in array
		for (int i = 0; i < n; ++i) {
			if (ind[i] != -1) continue;
			for (int j = i; j != -1; j = pc[j], ++cur) {
				ind[j] = cur;
				pp[j] = i;
			}
		}
	}
	// Get intervals corresponding to path between a and b
	vector<pair<int, int>> get(int a, int b) {
		vector<pair<int, int>> res;
		while(true) {
			if (ind[b] < ind[a]) swap(a, b);
			if (ind[pp[b]] <= ind[a]) {
				res.push_back({ind[a], ind[b]});
				return res;
			} else {
				res.push_back({ind[pp[b]], ind[b]});
				b = par[pp[b]];
			}
		}
	}
};

struct SegTree {
	vector<ll> seg;
	int h = 1;

	SegTree(int n) {
		while(h < n) h <<= 1;
		seg.resize(2*h, 0);
	}
	ll recGet(int a, int b, int i, int ia, int ib) const {
		if (b < ia || ib < a) return 0;
		if (a <=ia && ib <=b) return seg[i];
		int im = (ia + ib) >> 1;
		ll res = 0;
		res = max(res, recGet(a, b, 2*i, ia, im));
		res = max(res, recGet(a, b, 2*i+1, im+1, ib));
		return res;
	}
	ll get(int a, int b) const {
		return recGet(a, b, 1, 0, h-1);
	}
	void add(int i, int v) {
		i += h;
		seg[i] += v;
		for (i >>= 1; i >= 1; i >>= 1) {
			seg[i] = max(seg[2*i], seg[2*i+1]);
		}
	}
};

const int N = 1e5;
vector<int> conns[N];
int ord[N];

int dfs(int i, int p = -1, int j = 0) {
	ord[i] = j;
	j += 1;
	for (auto t : conns[i]) {
		if (t != p) j = dfs(t, i, j);
	}
	return j;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n-1; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		conns[a].push_back(b);
		conns[b].push_back(a);
	}

	dfs(0);
	vector<int> par(n, -1);
	for (int i = 0; i < n; ++i) {
		for (auto t : conns[i]) {
			if (ord[t] < ord[i]) par[ord[i]] = ord[t];
		}
	}

	HLD hld(par);
	SegTree seg(n);

	int q;
	cin >> q;
	for (int j = 0; j < q; ++j) {
		char t;
		cin >> t;
		if (t == 'I') {
			int i, v;
			cin >> i >> v;
			i = ord[i-1];
			seg.add(hld.ind[i], v);
		} else {
			int a, b;
			cin >> a >> b;
			a = ord[a-1]; b = ord[b-1];

			auto ints = hld.get(a, b);
			ll res = 0;
			for (auto pr : ints) {
				res = max(res, seg.get(pr.first, pr.second));
			}
			cout << res << '\n';
		}
	}
}