#include<bits/stdc++.h>
#include <iostream>
#define ll long long
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define ll long long
#define pii pair<int, int>
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define MS(a, v) memset(a, v, sizeof a)
#define REP(i, n) for(int i = 0; i < n; ++ i)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
#define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".ans", "w", stdout)
ll Rand(ll l, ll r){
return l + 1ll * rd() % (r - l + 1) * rd() % (r - l + 1);
}
string s = "{}()[]";
int main(){
ios_base :: sync_with_stdio(0);
srand(time(NULL));
for(int test = 1; ; ++ test){
ofstream inp("test.inp");
int t = 1;
// inp << t << "\n";
while(t--){
int n = Rand(3, 10), m = Rand(n - 1, 2 * n), s = Rand(0, 10), c = Rand(1, 10);
inp << n << " " << m << " " << s << " " << c << '\n';
FOR(i, 1, n){
inp << Rand(1, 10) << ' ';
}
inp << "\n";
FOR(i, 1, m){
int l = Rand(1, n), r = Rand(l + 1, n), w = Rand(1, 10);
inp << l << " " << r << " " << w << "\n";
}
// inp << "\n";
}
inp.close();
// return 0;
system("test.exe");
system("test_trau.exe");
if(system("fc test.out test.ans") != 0){
printf("Test %d Wrong!\n", test);
return 0;
}
printf("Test %d Correct!\n", test);
// return 0;
}
return 0;
}
ICNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CiAjaW5jbHVkZSA8aW9zdHJlYW0+CiNkZWZpbmUgbGwgbG9uZyBsb25nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgptdDE5OTM3IHJkKGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGlpIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgU1ooYSkgaW50KGEuc2l6ZSgpKQojZGVmaW5lIEFMTChhKSBhLmJlZ2luKCksIGEuZW5kKCkKI2RlZmluZSBNUyhhLCB2KSBtZW1zZXQoYSwgdiwgc2l6ZW9mIGEpCiNkZWZpbmUgUkVQKGksIG4pIGZvcihpbnQgaSA9IDA7IGkgPCBuOyArKyBpKQojZGVmaW5lIEZPUihpLCBhLCBiKSBmb3IoaW50IGkgPSAoYSk7IGkgPD0gKGIpOyArKyBpKQojZGVmaW5lIEZPRChpLCBhLCBiKSBmb3IoaW50IGkgPSAoYSk7IGkgPj0gKGIpOyAtLSBpKQojZGVmaW5lIFRTdW4oVFopIGZyZW9wZW4oVFoiLmlucCIsICJyIiwgc3RkaW4pLCBmcmVvcGVuKFRaIi5hbnMiLCAidyIsIHN0ZG91dCkKCmxsIFJhbmQobGwgbCwgbGwgcil7CiAgICAgICAgcmV0dXJuIGwgKyAxbGwgKiByZCgpICUgKHIgLSBsICsgMSkgKiByZCgpICUgKHIgLSBsICsgMSk7Cn0Kc3RyaW5nIHMgPSAie30oKVtdIjsKaW50IG1haW4oKXsKCiAgICAgICAgaW9zX2Jhc2UgOjogc3luY193aXRoX3N0ZGlvKDApOwoKICAgICAgICBzcmFuZCh0aW1lKE5VTEwpKTsKCgogICAgICAgIGZvcihpbnQgdGVzdCA9IDE7IDsgKysgdGVzdCl7CgogICAgICAgICAgICAgICAgb2ZzdHJlYW0gaW5wKCJ0ZXN0LmlucCIpOwoKICAgICAgICAgICAgICAgIGludCB0ID0gMTsKLy8gICAgICAgICAgICAgICAgaW5wIDw8IHQgPDwgIlxuIjsKICAgICAgICAgICAgICAgIHdoaWxlKHQtLSl7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCBuID0gUmFuZCgzLCAxMCksIG0gPSBSYW5kKG4gLSAxLCAyICogbiksIHMgPSBSYW5kKDAsIDEwKSwgYyA9IFJhbmQoMSwgMTApOwogICAgICAgICAgICAgICAgICAgICAgICBpbnAgPDwgbiA8PCAiICIgPDwgbSA8PCAiICIgPDwgcyA8PCAiICIgPDwgYyA8PCAnXG4nOwogICAgICAgICAgICAgICAgICAgICAgICBGT1IoaSwgMSwgbil7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5wIDw8IFJhbmQoMSwgMTApIDw8ICcgJzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBpbnAgPDwgIlxuIjsKICAgICAgICAgICAgICAgICAgICAgICAgRk9SKGksIDEsIG0pewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGludCBsID0gUmFuZCgxLCBuKSwgciA9IFJhbmQobCArIDEsIG4pLCAgdyA9IFJhbmQoMSwgMTApOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlucCA8PCBsIDw8ICIgIiA8PCByIDw8ICIgIiA8PCB3IDw8ICJcbiI7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KLy8gICAgICAgICAgICAgICAgICAgICAgICBpbnAgPDwgIlxuIjsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBpbnAuY2xvc2UoKTsKLy8gICAgICAgICAgICAgICAgcmV0dXJuIDA7CgogICAgICAgICAgICAgICAgc3lzdGVtKCJ0ZXN0LmV4ZSIpOwogICAgICAgICAgICAgICAgc3lzdGVtKCJ0ZXN0X3RyYXUuZXhlIik7CgogICAgICAgICAgICAgICAgaWYoc3lzdGVtKCJmYyB0ZXN0Lm91dCB0ZXN0LmFucyIpICE9IDApewogICAgICAgICAgICAgICAgICAgICAgICBwcmludGYoIlRlc3QgJWQgV3JvbmchXG4iLCB0ZXN0KTsKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBwcmludGYoIlRlc3QgJWQgQ29ycmVjdCFcbiIsIHRlc3QpOwovLyAgICAgICAgICAgICAgICByZXR1cm4gMDsKCiAgICAgICAgfQogICAgICAgIHJldHVybiAwOwp9Cg==