#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include<stack>
#include<bitset>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include<unordered_map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(r,v) for(auto r:v)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define pc() pop_back()
#define ull unsigned long long
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
#define ll long long
#define endl '\n'
#define st stack<int>
#define vl vector<long long>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvi vector<vi>
#define vs vector<string>
#define mod 1000000007
#define un unordered_map<int,int>
#define mii map<int,int>
#define Sort(a) sort(all(a))
#define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define MaxP(a) max_element(all(a)) - a.begin()
#define MinP(a) min_element(all(a)) - a.begin()
#define allUpper(a) transform(all(a), a.begin(), :: toupper)
#define allLower(a) transform(all(a), a.begin(), :: tolower)
#define rev(a) reverse(all(a))
#define ub(v,k) upper_bound(all(v), k) - v.begin()
#define lb(v,k) lower_bound(all(v), k) - v.begin()
#define adv(a,n) advance(auto it:a,n)
#define RSort(a) sort(a.rbegin(),a.rend()) //decending order
#define cnt(v,a) count(all(v),a)
#define bs(v,a) binary_search(all(v),a)
#define mmax(v) *max_element(all(v))
#define mmin(v) *min_element(all(v))
#define popcount(mask) __builtin_popcount(mask) // count set bit
#define popcountLL(mask) __builtin_popcountll(mask) // for long long
#define X real() // useful for working with #include <complex> for computational geometry
#define Y imag()
#define ss second
#define ff first
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
template <typename T> T gcd(T a, T b) { while (b) b ^= a ^= b ^= a %= b; return a; }
template <typename T> T setbit(T mask, T pos) { return mask |= (1 << pos); }
template <typename T> T resetbit(T mask, T pos) { return mask &= ~(1 << pos); }
template <typename T> T togglebit(T mask, T pos) { return mask ^= (1 << pos); }
template <typename T> T checkbit(T mask, T pos) { return (bool)(mask & (1 << pos)); }
template <typename T> T lcm(T a, T b) { return (a / gcd(a, b)) * b; }
template <typename T> T modu(T a, T b) { return (a < b ? a : a % b); }
template<typename T> T mod_neg(T a, T b) { a = mod(a, b); if (a < 0) { a += b; } return a; }
template <typename T>T expo(T e, T n) { T x = 1, p = e; while (n) { if (n & 1)x = x * p; p = p * p; n >>= 1; } return x; }
template<typename T> T mod_inverse(T a, T n) { T x, y; T d = extended_euclid(a, n, x, y); return (d > 1 ? -1 : mod_neg(x, n)); }
template <typename T>T power(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mod(x * p, m); p = mod(p * p, m); n >>= 1; } return x; }
template <typename T>T powerL(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mulmod(x, p, m); p = mulmod(p, p, m); n >>= 1; } return x; }
bool Pow2(int n) {
return n && (!(n & (n - 1)));
}
void printc(vc& result) {
aut(r, result) cout << r << " ";
cout << endl;
}
void printl(vl& result) {
aut(r, result) cout << r << " ";
cout << endl;
}
void print(vi& result) {
aut(r, result) cout << r << " ";
cout << endl;
}
bool comp(pair<ll, ll>p1, pair<ll, ll>p2) { return p1.second < p2.second; }
bool isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
ll power(ll a, ll b) {
if (a == 1)
return 1;
if (b == 0)
return 1;
ll c = power(a, b / 2);
ll res = 1;
if (b % 2) {
res = (c * c) % mod;
res *= a;
res %= mod;
}
else
res = ((c * c) % mod);
return res;
}
ll modInv(ll a) { return power(a, mod - 2) % mod; }
ll fact[1], inv[1];
void factorial(ll n) {
fact[0] = 1;
for (ll i = 1; i <= n; i++) {
fact[i] = fact[i - 1] * i;
fact[i] %= mod;
}
}
void InvFactorial(ll n) {
inv[0] = 1;
for (ll i = 1; i <= n; i++)
inv[i] = modInv(fact[i]);
}
ll ncr(ll n, ll r) {
if (n < r || n < 0 || r < 0)
return 0;
ll b = inv[n - r];
ll c = inv[r];
ll a = fact[n] * b;
a %= mod;
a *= c;
a %= mod;
return a;
}
//ifstream cin("b_read_on.txt"); ofstream cout("output3.txt");
//Use (<<) for multiplication
//Use (>>) for division
//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed;cerr.tie(NULL);
// find_by_order -> value at index
// order_of_key -> index of value
// while using (1<<i) use ((ll)1<<(ll)i)
// in Floyd-Warshall Algo, k is outer loop
// If an element was not initially in map and if asked mp[a],the element gets inserted
// a%=mod take a lot of time... try to use it minimum and use memset as it reduces a lot of time usage...use if(a>=mod) a%=mod
//cout<<(double) can be harmful , always use printf(%.9llf)...take scanf("%lf",&p[i][j]) as input , not llf;
//use s.erase(it++) for erasing iterator and then moving to the next one
//never use adj.resize(n) as value is persistent, always erase
//use __builtin_popcountll() for ll
// no of prime numbers in range : (70,19) , (1000,168) , (100000,1229) , (sqrt(10^9),3409) ;
//always check the use of segment tree using bottom-up dp
/*
Try the solution
10^8 O(N) Border case
10^7 O(N) Might be accepted
10^6 O(N) Perfect
10^5 O(N * logN)
10^3 O(N ^ 2)
10^2 O(N ^ 3)
10^9 O(logN) or Sqrt(N)
*/
vi par(1000001, -1);
vi ran(1000001, 1);
int find(int a) {
if (par[a] < 0) return a;
return par[a] = find(par[a]);
}
void uni(int a, int b) {
if (ran[a] > ran[b]) {
par[b] = a;
ran[a] += ran[b];
}
else {
par[a] = b;
ran[b] += ran[a];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test;
//test = 1;
cin >> test;
while (test--) {
int n, e;
cin >> n >> e;
int flag = 0;
while (e--) {
int n1, n2;
string c;
cin >> n1 >> c >> n2;
n1 = find(n1);
n2 = find(n2);
if (n1 == n2 && c == "!=") {
flag = 1;
}
else if (n1 != n2 && c == "=") uni(n1, n2);
}
if (flag ) cout << "NO" << endl;
else cout << "YES" << endl;
}
}
I2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxxdWV1ZT4KCiNpbmNsdWRlPHN0YWNrPgojaW5jbHVkZTxiaXRzZXQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxsaW1pdHM+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZTx1bm9yZGVyZWRfbWFwPgoKI2RlZmluZSByZXAoaSxuKSBmb3IoaW50IChpKT0wOyhpKTwoaW50KShuKTsrKyhpKSkKI2RlZmluZSByZXIoaSxsLHUpIGZvcihpbnQgKGkpPShpbnQpKGwpOyhpKTw9KGludCkodSk7KysoaSkpCiNkZWZpbmUgcmV1KGksbCx1KSBmb3IoaW50IChpKT0oaW50KShsKTsoaSk8KGludCkodSk7KysoaSkpCiNkZWZpbmUgYXV0KHIsdikgZm9yKGF1dG8gcjp2KQoKI2RlZmluZSBlYWNoKGl0LG8pIGZvcihhdXQoaXQsIChvKS5iZWdpbigpKTsgaXQgIT0gKG8pLmVuZCgpOyArKyBpdCkKI2RlZmluZSBhbGwobykgKG8pLmJlZ2luKCksIChvKS5lbmQoKQojZGVmaW5lIHBiKHgpIHB1c2hfYmFjayh4KQojZGVmaW5lIHBjKCkgIHBvcF9iYWNrKCkKCiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIG1wKHgseSkgbWFrZV9wYWlyKCh4KSwoeSkpCiNkZWZpbmUgbXNldChtLHYpIG1lbXNldChtLHYsc2l6ZW9mKG0pKQoKI2RlZmluZSBJTkYgMHgzZjNmM2YzZgojZGVmaW5lIElORkwgMHgzZjNmM2YzZjNmM2YzZjNmTEwKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBlbmRsICdcbicKCiNkZWZpbmUgc3Qgc3RhY2s8aW50PgoKCgojZGVmaW5lIHZsIHZlY3Rvcjxsb25nIGxvbmc+CiNkZWZpbmUgdmkgdmVjdG9yPGludD4KI2RlZmluZSB2YiB2ZWN0b3I8Ym9vbD4KI2RlZmluZSB2YyB2ZWN0b3I8Y2hhcj4KI2RlZmluZSBwaWkgcGFpcjxpbnQsaW50PgojZGVmaW5lIHZwaWkgdmVjdG9yPHBpaT4KI2RlZmluZSB2dmkgdmVjdG9yPHZpPgojZGVmaW5lIHZzIHZlY3RvcjxzdHJpbmc+CgojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CgojZGVmaW5lIHVuICB1bm9yZGVyZWRfbWFwPGludCxpbnQ+CiNkZWZpbmUgbWlpIG1hcDxpbnQsaW50PgoKI2RlZmluZSBTb3J0KGEpIHNvcnQoYWxsKGEpKQojZGVmaW5lIEVEKGEpIFNvcnQoYSksIGEuZXJhc2UodW5pcXVlKGFsbChhKSksIGEuZW5kKCkpLy9yZW1vdmluZyBhbGwgZHVwbGljYXRlcwoKI2RlZmluZSBtYXgzKGEsIGIsIGMpICAgbWF4KGEsIG1heChiLCBjKSkKI2RlZmluZSBtaW4zKGEsIGIsIGMpICAgbWluKGEsIG1pbihiLCBjKSkKI2RlZmluZSBNYXgoYSkgICAgICAgKm1heF9lbGVtZW50KGFsbChhKSkKI2RlZmluZSBNaW4oYSkgICAgICAgKm1pbl9lbGVtZW50KGFsbChhKSkKI2RlZmluZSBNYXhQKGEpICAgICAgIG1heF9lbGVtZW50KGFsbChhKSkgLSBhLmJlZ2luKCkKI2RlZmluZSBNaW5QKGEpICAgICAgICBtaW5fZWxlbWVudChhbGwoYSkpIC0gYS5iZWdpbigpCgojZGVmaW5lIGFsbFVwcGVyKGEpICAgICB0cmFuc2Zvcm0oYWxsKGEpLCBhLmJlZ2luKCksIDo6IHRvdXBwZXIpCiNkZWZpbmUgYWxsTG93ZXIoYSkgICAgIHRyYW5zZm9ybShhbGwoYSksIGEuYmVnaW4oKSwgOjogdG9sb3dlcikKCiNkZWZpbmUgcmV2KGEpICAgICAgICAgIHJldmVyc2UoYWxsKGEpKQojZGVmaW5lIHViKHYsaykgICAgICAgICAgdXBwZXJfYm91bmQoYWxsKHYpLCBrKSAtIHYuYmVnaW4oKQojZGVmaW5lIGxiKHYsaykgICAgICAgICAgbG93ZXJfYm91bmQoYWxsKHYpLCBrKSAtIHYuYmVnaW4oKQojZGVmaW5lIGFkdihhLG4pICAgICAgICBhZHZhbmNlKGF1dG8gaXQ6YSxuKQojZGVmaW5lIFJTb3J0KGEpICAgICAgICAgc29ydChhLnJiZWdpbigpLGEucmVuZCgpKSAvL2RlY2VuZGluZyBvcmRlcgojZGVmaW5lIGNudCh2LGEpICAgICAgICAgICAgIGNvdW50KGFsbCh2KSxhKQojZGVmaW5lIGJzKHYsYSkgICAgICAgICAgIGJpbmFyeV9zZWFyY2goYWxsKHYpLGEpCiNkZWZpbmUgbW1heCh2KSAgICAgICAgICAgKm1heF9lbGVtZW50KGFsbCh2KSkKI2RlZmluZSBtbWluKHYpICAgICAgICAgICAqbWluX2VsZW1lbnQoYWxsKHYpKQojZGVmaW5lIHBvcGNvdW50KG1hc2spICAgICAgICAgICAgICAgICAgICAgICBfX2J1aWx0aW5fcG9wY291bnQobWFzaykgLy8gY291bnQgc2V0IGJpdAojZGVmaW5lIHBvcGNvdW50TEwobWFzaykgICAgICAgICAgICAgICAgICAgICBfX2J1aWx0aW5fcG9wY291bnRsbChtYXNrKSAvLyBmb3IgbG9uZyBsb25nCiNkZWZpbmUgWCByZWFsKCkgLy8gdXNlZnVsIGZvciB3b3JraW5nIHdpdGggI2luY2x1ZGUgPGNvbXBsZXg+IGZvciBjb21wdXRhdGlvbmFsIGdlb21ldHJ5CiNkZWZpbmUgWSBpbWFnKCkKCiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgZmYgZmlyc3QKCiNkZWZpbmUgdHJhY2UxKHgpICAgICAgICAgICAgICAgICAgICAgICAgICAgY2VyciA8PCAjeCA8PCAiOiAiIDw8IHggPDwgZW5kbDsKI2RlZmluZSB0cmFjZTIoeCwgeSkgICAgICAgICAgICAgICAgICAgICAgICBjZXJyIDw8ICN4IDw8ICI6ICIgPDwgeCA8PCAiIHwgIiA8PCAjeSA8PCAiOiAiIDw8IHkgPDwgZW5kbDsKI2RlZmluZSB0cmFjZTMoeCwgeSwgeikgICAgICAgICAgICAgICAgICAgICBjZXJyIDw8ICN4IDw8ICI6ICIgPDwgeCA8PCAiIHwgIiA8PCAjeSA8PCAiOiAiIDw8IHkgPDwgIiB8ICIgPDwgI3ogPDwgIjogIiA8PCB6IDw8IGVuZGw7CiNkZWZpbmUgdHJhY2U0KGEsIGIsIGMsIGQpICAgICAgICAgICAgICAgICAgY2VyciA8PCAjYSA8PCAiOiAiIDw8IGEgPDwgIiB8ICIgPDwgI2IgPDwgIjogIiA8PCBiIDw8ICIgfCAiIDw8ICNjIDw8ICI6ICIgPDwgYyA8PCAiIHwgIiA8PCAjZCA8PCAiOiAiIDw8IGQgPDwgZW5kbDsKI2RlZmluZSB0cmFjZTUoYSwgYiwgYywgZCwgZSkgICAgICAgICAgICAgICBjZXJyIDw8ICNhIDw8ICI6ICIgPDwgYSA8PCAiIHwgIiA8PCAjYiA8PCAiOiAiIDw8IGIgPDwgIiB8ICIgPDwgI2MgPDwgIjogIiA8PCBjIDw8ICIgfCAiIDw8ICNkIDw8ICI6ICIgPDwgZCA8PCAiIHwgIiA8PCAjZSA8PCAiOiAiIDw8IGUgPDwgZW5kbDsKI2RlZmluZSB0cmFjZTYoYSwgYiwgYywgZCwgZSwgZikgICAgICAgICAgICBjZXJyIDw8ICNhIDw8ICI6ICIgPDwgYSA8PCAiIHwgIiA8PCAjYiA8PCAiOiAiIDw8IGIgPDwgIiB8ICIgPDwgI2MgPDwgIjogIiA8PCBjIDw8ICIgfCAiIDw8ICNkIDw8ICI6ICIgPDwgZCA8PCAiIHwgIiA8PCAjZSA8PCAiOiAiIDw8IGUgPDwgIiB8ICIgPDwgI2YgPDwgIjogIiA8PCBmIDw8IGVuZGw7Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4gVCBnY2QoVCBhLCBUIGIpIHsgd2hpbGUgKGIpIGIgXj0gYSBePSBiIF49IGEgJT0gYjsgcmV0dXJuIGE7IH0KdGVtcGxhdGUgPHR5cGVuYW1lIFQ+IFQgc2V0Yml0KFQgbWFzaywgVCBwb3MpIHsgcmV0dXJuIG1hc2sgfD0gKDEgPDwgcG9zKTsgfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4gVCByZXNldGJpdChUIG1hc2ssIFQgcG9zKSB7IHJldHVybiBtYXNrICY9IH4oMSA8PCBwb3MpOyB9CnRlbXBsYXRlIDx0eXBlbmFtZSBUPiBUIHRvZ2dsZWJpdChUIG1hc2ssIFQgcG9zKSB7IHJldHVybiBtYXNrIF49ICgxIDw8IHBvcyk7IH0KdGVtcGxhdGUgPHR5cGVuYW1lIFQ+IFQgY2hlY2tiaXQoVCBtYXNrLCBUIHBvcykgeyByZXR1cm4gKGJvb2wpKG1hc2sgJiAoMSA8PCBwb3MpKTsgfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4gVCBsY20oVCBhLCBUIGIpIHsgcmV0dXJuIChhIC8gZ2NkKGEsIGIpKSAqIGI7IH0KCgoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+IFQgbW9kdShUIGEsIFQgYikgeyByZXR1cm4gKGEgPCBiID8gYSA6IGEgJSBiKTsgfQp0ZW1wbGF0ZTx0eXBlbmFtZSBUPiBUIG1vZF9uZWcoVCBhLCBUIGIpIHsgYSA9IG1vZChhLCBiKTsgaWYgKGEgPCAwKSB7IGEgKz0gYjsgfSByZXR1cm4gYTsgfQoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+VCBleHBvKFQgZSwgVCBuKSB7IFQgeCA9IDEsIHAgPSBlOyB3aGlsZSAobikgeyBpZiAobiAmIDEpeCA9IHggKiBwOyBwID0gcCAqIHA7IG4gPj49IDE7IH0gcmV0dXJuIHg7IH0KdGVtcGxhdGU8dHlwZW5hbWUgVD4gVCBtb2RfaW52ZXJzZShUIGEsIFQgbikgeyBUIHgsIHk7IFQgZCA9IGV4dGVuZGVkX2V1Y2xpZChhLCBuLCB4LCB5KTsgcmV0dXJuIChkID4gMSA/IC0xIDogbW9kX25lZyh4LCBuKSk7IH0KCnRlbXBsYXRlIDx0eXBlbmFtZSBUPlQgcG93ZXIoVCBlLCBUIG4sIFQgbSkgeyBUIHggPSAxLCBwID0gZTsgd2hpbGUgKG4pIHsgaWYgKG4gJiAxKXggPSBtb2QoeCAqIHAsIG0pOyBwID0gbW9kKHAgKiBwLCBtKTsgbiA+Pj0gMTsgfSByZXR1cm4geDsgfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD5UIHBvd2VyTChUIGUsIFQgbiwgVCBtKSB7IFQgeCA9IDEsIHAgPSBlOyB3aGlsZSAobikgeyBpZiAobiAmIDEpeCA9IG11bG1vZCh4LCBwLCBtKTsgcCA9IG11bG1vZChwLCBwLCBtKTsgbiA+Pj0gMTsgfSByZXR1cm4geDsgfQoKYm9vbCBQb3cyKGludCBuKSB7CiAgICByZXR1cm4gbiAmJiAoIShuICYgKG4gLSAxKSkpOwp9CnZvaWQgcHJpbnRjKHZjJiByZXN1bHQpIHsKICAgIGF1dChyLCByZXN1bHQpIGNvdXQgPDwgciA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7Cn0Kdm9pZCBwcmludGwodmwmIHJlc3VsdCkgewogICAgYXV0KHIsIHJlc3VsdCkgY291dCA8PCByIDw8ICIgIjsKICAgIGNvdXQgPDwgZW5kbDsKfQp2b2lkIHByaW50KHZpJiByZXN1bHQpIHsKICAgIGF1dChyLCByZXN1bHQpIGNvdXQgPDwgciA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7Cn0KYm9vbCBjb21wKHBhaXI8bGwsIGxsPnAxLCBwYWlyPGxsLCBsbD5wMikgeyByZXR1cm4gcDEuc2Vjb25kIDwgcDIuc2Vjb25kOyB9CmJvb2wgaXNQcmltZShpbnQgbikKewogICAgLy8gQ29ybmVyIGNhc2VzIAogICAgaWYgKG4gPD0gMSkgIHJldHVybiBmYWxzZTsKICAgIGlmIChuIDw9IDMpICByZXR1cm4gdHJ1ZTsKCiAgICAvLyBUaGlzIGlzIGNoZWNrZWQgc28gdGhhdCB3ZSBjYW4gc2tpcCAgCiAgICAvLyBtaWRkbGUgZml2ZSBudW1iZXJzIGluIGJlbG93IGxvb3AgCiAgICBpZiAobiAlIDIgPT0gMCB8fCBuICUgMyA9PSAwKSByZXR1cm4gZmFsc2U7CgogICAgZm9yIChpbnQgaSA9IDU7IGkgKiBpIDw9IG47IGkgPSBpICsgNikKICAgICAgICBpZiAobiAlIGkgPT0gMCB8fCBuICUgKGkgKyAyKSA9PSAwKQogICAgICAgICAgICByZXR1cm4gZmFsc2U7CgogICAgcmV0dXJuIHRydWU7Cn0KbGwgcG93ZXIobGwgYSwgbGwgYikgewogICAgaWYgKGEgPT0gMSkKICAgICAgICByZXR1cm4gMTsKICAgIGlmIChiID09IDApCiAgICAgICAgcmV0dXJuIDE7CiAgICBsbCBjID0gcG93ZXIoYSwgYiAvIDIpOwogICAgbGwgcmVzID0gMTsKICAgIGlmIChiICUgMikgewogICAgICAgIHJlcyA9IChjICogYykgJSBtb2Q7CiAgICAgICAgcmVzICo9IGE7CiAgICAgICAgcmVzICU9IG1vZDsKICAgIH0KICAgIGVsc2UKICAgICAgICByZXMgPSAoKGMgKiBjKSAlIG1vZCk7CiAgICByZXR1cm4gcmVzOwp9CmxsIG1vZEludihsbCBhKSB7IHJldHVybiBwb3dlcihhLCBtb2QgLSAyKSAlIG1vZDsgfQpsbCBmYWN0WzFdLCBpbnZbMV07CnZvaWQgZmFjdG9yaWFsKGxsIG4pIHsKICAgIGZhY3RbMF0gPSAxOwogICAgZm9yIChsbCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICBmYWN0W2ldID0gZmFjdFtpIC0gMV0gKiBpOwogICAgICAgIGZhY3RbaV0gJT0gbW9kOwogICAgfQp9CnZvaWQgSW52RmFjdG9yaWFsKGxsIG4pIHsKICAgIGludlswXSA9IDE7CiAgICBmb3IgKGxsIGkgPSAxOyBpIDw9IG47IGkrKykKICAgICAgICBpbnZbaV0gPSBtb2RJbnYoZmFjdFtpXSk7Cn0KbGwgbmNyKGxsIG4sIGxsIHIpIHsKICAgIGlmIChuIDwgciB8fCBuIDwgMCB8fCByIDwgMCkKICAgICAgICByZXR1cm4gMDsKICAgIGxsIGIgPSBpbnZbbiAtIHJdOwogICAgbGwgYyA9IGludltyXTsKICAgIGxsIGEgPSBmYWN0W25dICogYjsKICAgIGEgJT0gbW9kOwogICAgYSAqPSBjOwogICAgYSAlPSBtb2Q7CiAgICByZXR1cm4gYTsKfQovL2lmc3RyZWFtIGNpbigiYl9yZWFkX29uLnR4dCIpOyBvZnN0cmVhbSBjb3V0KCJvdXRwdXQzLnR4dCIpOwovL1VzZSAoPDwpIGZvciBtdWx0aXBsaWNhdGlvbgovL1VzZSAoPj4pIGZvciBkaXZpc2lvbgovL2lvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCk7Y291dC50aWUoTlVMTCk7Y291dDw8Zml4ZWQ7Y2Vyci50aWUoTlVMTCk7Ci8vIGZpbmRfYnlfb3JkZXIgLT4gdmFsdWUgYXQgaW5kZXgKLy8gb3JkZXJfb2Zfa2V5IC0+IGluZGV4IG9mIHZhbHVlCi8vIHdoaWxlIHVzaW5nICgxPDxpKSB1c2UgKChsbCkxPDwobGwpaSkgCi8vIGluIEZsb3lkLVdhcnNoYWxsIEFsZ28sIGsgaXMgb3V0ZXIgbG9vcCAKLy8gSWYgYW4gZWxlbWVudCB3YXMgbm90IGluaXRpYWxseSBpbiBtYXAgYW5kIGlmIGFza2VkIG1wW2FdLHRoZSBlbGVtZW50IGdldHMgaW5zZXJ0ZWQgCi8vIGElPW1vZCB0YWtlIGEgbG90IG9mIHRpbWUuLi4gdHJ5IHRvIHVzZSBpdCBtaW5pbXVtIGFuZCB1c2UgbWVtc2V0IGFzIGl0IHJlZHVjZXMgYSBsb3Qgb2YgdGltZSB1c2FnZS4uLnVzZSBpZihhPj1tb2QpIGElPW1vZAovL2NvdXQ8PChkb3VibGUpIGNhbiBiZSBoYXJtZnVsICwgYWx3YXlzIHVzZSBwcmludGYoJS45bGxmKS4uLnRha2Ugc2NhbmYoIiVsZiIsJnBbaV1bal0pIGFzIGlucHV0ICwgbm90IGxsZjsKLy91c2Ugcy5lcmFzZShpdCsrKSBmb3IgZXJhc2luZyBpdGVyYXRvciBhbmQgdGhlbiBtb3ZpbmcgdG8gdGhlIG5leHQgb25lCi8vbmV2ZXIgdXNlIGFkai5yZXNpemUobikgYXMgdmFsdWUgaXMgcGVyc2lzdGVudCwgYWx3YXlzIGVyYXNlCi8vdXNlIF9fYnVpbHRpbl9wb3Bjb3VudGxsKCkgZm9yIGxsCi8vIG5vIG9mIHByaW1lIG51bWJlcnMgaW4gcmFuZ2UgOiAoNzAsMTkpICwgKDEwMDAsMTY4KSAsICgxMDAwMDAsMTIyOSkgLCAoc3FydCgxMF45KSwzNDA5KSA7Ci8vYWx3YXlzIGNoZWNrIHRoZSB1c2Ugb2Ygc2VnbWVudCB0cmVlIHVzaW5nIGJvdHRvbS11cCBkcAovKgogICBUcnkgdGhlIHNvbHV0aW9uCgogICAxMF44ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTyhOKSBCb3JkZXIgY2FzZQogICAxMF43ICAgICAgICAgICAgICAgICAgICAgICAgIE8oTikgTWlnaHQgYmUgYWNjZXB0ZWQKICAgMTBeNiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIE8oTikgUGVyZmVjdAogICAxMF41ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTyhOICogbG9nTikKICAgMTBeMyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIE8oTiBeIDIpCiAgIDEwXjIgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBPKE4gXiAzKQogICAxMF45ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTyhsb2dOKSBvciBTcXJ0KE4pCgoqLwp2aSBwYXIoMTAwMDAwMSwgLTEpOwp2aSByYW4oMTAwMDAwMSwgMSk7CmludCBmaW5kKGludCBhKSB7CiAgICBpZiAocGFyW2FdIDwgMCkgcmV0dXJuIGE7CiAgICByZXR1cm4gcGFyW2FdID0gZmluZChwYXJbYV0pOwp9CnZvaWQgdW5pKGludCBhLCBpbnQgYikgewogICAgaWYgKHJhblthXSA+IHJhbltiXSkgewogICAgICAgIHBhcltiXSA9IGE7CiAgICAgICAgcmFuW2FdICs9IHJhbltiXTsKICAgIH0KICAgIGVsc2UgewogICAgICAgIHBhclthXSA9IGI7CiAgICAgICAgcmFuW2JdICs9IHJhblthXTsKICAgIH0KCgp9CgoKaW50IG1haW4oKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKICAgIGludCB0ZXN0OwogICAgLy90ZXN0ID0gMTsKICAgIGNpbiA+PiB0ZXN0OwogICAgCiAgICB3aGlsZSAodGVzdC0tKSB7CiAgICAgICAgaW50IG4sIGU7CiAgICAgICAgY2luID4+IG4gPj4gZTsKICAgICAgICBpbnQgZmxhZyA9IDA7CiAgICAgICAgd2hpbGUgKGUtLSkgewogICAgICAgICAgICBpbnQgbjEsIG4yOwogICAgICAgICAgICBzdHJpbmcgYzsKICAgICAgICAgICAgY2luID4+IG4xID4+IGMgPj4gbjI7CiAgICAgICAgICAgIG4xID0gZmluZChuMSk7CiAgICAgICAgICAgIG4yID0gZmluZChuMik7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZiAobjEgPT0gbjIgJiYgYyA9PSAiIT0iKSB7CiAgICAgICAgICAgICAgICBmbGFnID0gMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChuMSAhPSBuMiAmJiBjID09ICI9IikgdW5pKG4xLCBuMik7CiAgICAgICAgICAgCgoKICAgICAgICB9CiAgICAgICAgaWYgKGZsYWcgKSBjb3V0IDw8ICJOTyIgPDwgZW5kbDsKICAgICAgICBlbHNlIGNvdXQgPDwgIllFUyIgPDwgZW5kbDsKCiAgICAgICAgCiAgICB9Cgp9CgoKCgoKCgoKCg==