#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
string inp = R"(
364
14 102 64 63 107 52 38 38 107 116 29 17 107 38 29 17 43 27 116 52 17 92 9 9 38 111 17 94 112 31 27 22 110 17 92 3 3 87 62 87 17 17 111 0 55 116 45 17 107 118 22 17 3 17 17 116 18 31 98 116 94 2 98 16 16 22 94 94 98 108 63 38 112 118 87 38 112 62 107 3 29 3 87 89 107 38 38 29 105 94 116 94 105 38 119 94 43 41 112 21 17 118 116 52 9 111 17 112 94 55 107 62 3 94 118 116 38 9 21 16 16 98 102 3 1 113 94 112 17 111 92 116 116 64 29 29 17 38 112 116 98 10 78 4 17 94 16 4 110 17 1 95 65 94 110 18 64 116 17 113 15 38 17 111 112 105 38 3 16 105 38 22 16 105 62 62 29 1 110 118 16 16 108 87 17 16 87 17 116 16 19 110 62 16 16 108 87 94 16 63 94 98 16 87 107 116 38 4 111 116 38 38 111 52 4 4 29 42 116 112 94 94 23 94 4 92 75 17 110 94 54 10 62 4 3 116 62 94 94 63 16 98 94 102 70 67 63 110 110 17 83 9 9 38 90 87 87 17 67 116 15 15 38 22 52 38 5 90 87 87 17 87 31 116 94 92 44 38 38 92 90 21 21 99 94 116 17 38 29 3 117 38 9 3 51 111 16 38 91 75 116 116 16 52 17 118 3 78 26 111 16 91 52 17 116 16 111 22 3 3 3 111 111 98 83 79 87 119 119 15 29 3 62 9 4 38 38 94 111 62 4 29 110 110 62 87 62 33 87 16 16 79 29 16 98 15 5 3 87 62 33 38 38 94
0 1 1
0 4 122
0 0 243
1 5 2
1 3 42
1 2 82
2 1 3
2 3 16
2 2 29
3 1 4
3 2 8
3 3 12
4 5 5
4 2 6
4 3 7
8 2 9
8 3 10
8 5 11
12 3 13
12 2 14
12 5 15
16 0 17
16 3 21
16 4 25
17 2 18
17 3 19
17 0 20
21 4 22
21 5 23
21 1 24
25 2 26
25 5 27
25 4 28
29 0 30
29 2 34
29 4 38
30 2 31
30 3 32
30 0 33
34 4 35
34 5 36
34 1 37
38 1 39
38 3 40
38 2 41
42 2 43
42 5 56
42 4 69
43 2 44
43 1 48
43 0 52
44 0 45
44 5 46
44 4 47
48 2 49
48 5 50
48 3 51
52 2 53
52 0 54
52 1 55
56 5 57
56 1 61
56 0 65
57 0 58
57 2 59
57 4 60
61 1 62
61 2 63
61 0 64
65 5 66
65 0 67
65 1 68
69 5 70
69 2 74
69 4 78
70 1 71
70 3 72
70 2 73
74 1 75
74 3 76
74 5 77
78 2 79
78 3 80
78 5 81
82 1 83
82 3 96
82 5 109
83 1 84
83 5 88
83 3 92
84 3 85
84 5 86
84 2 87
88 3 89
88 5 90
88 2 91
92 3 93
92 5 94
92 2 95
96 0 97
96 4 101
96 3 105
97 0 98
97 5 99
97 2 100
101 3 102
101 5 103
101 4 104
105 2 106
105 4 107
105 5 108
109 0 110
109 4 114
109 5 118
110 5 111
110 2 112
110 3 113
114 5 115
114 3 116
114 4 117
118 5 119
118 0 120
118 1 121
122 5 123
122 3 163
122 2 203
123 0 124
123 2 137
123 1 150
124 0 125
124 2 129
124 1 133
125 5 126
125 4 127
125 2 128
129 4 130
129 5 131
129 2 132
133 2 134
133 3 135
133 1 136
137 2 138
137 0 142
137 5 146
138 2 139
138 5 140
138 4 141
142 3 143
142 1 144
142 4 145
146 0 147
146 4 148
146 1 149
150 0 151
150 2 155
150 1 159
151 4 152
151 1 153
151 5 154
155 5 156
155 1 157
155 0 158
159 5 160
159 4 161
159 2 162
163 4 164
163 2 177
163 5 190
164 2 165
164 5 169
164 4 173
165 2 166
165 5 167
165 3 168
169 5 170
169 2 171
169 3 172
173 2 174
173 5 175
173 3 176
177 0 178
177 1 182
177 2 186
178 4 179
178 5 180
178 2 181
182 5 183
182 2 184
182 4 185
186 3 187
186 1 188
186 5 189
190 0 191
190 1 195
190 5 199
191 4 192
191 2 193
191 5 194
195 2 196
195 5 197
195 4 198
199 3 200
199 1 201
199 2 202
203 1 204
203 3 217
203 5 230
204 3 205
204 5 209
204 2 213
205 3 206
205 4 207
205 5 208
209 5 210
209 4 211
209 3 212
213 3 214
213 5 215
213 0 216
217 4 218
217 3 222
217 0 226
218 4 219
218 5 220
218 3 221
222 1 223
222 5 224
222 0 225
226 2 227
226 1 228
226 5 229
230 5 231
230 4 235
230 0 239
231 1 232
231 3 233
231 0 234
235 4 236
235 3 237
235 5 238
239 2 240
239 1 241
239 3 242
243 5 244
243 3 284
243 2 324
244 4 245
244 1 258
244 2 271
245 1 246
245 4 250
245 2 254
246 2 247
246 3 248
246 1 249
250 4 251
250 3 252
250 1 253
254 5 255
254 4 256
254 1 257
258 1 259
258 4 263
258 2 267
259 3 260
259 4 261
259 5 262
263 1 264
263 5 265
263 0 266
267 5 268
267 1 269
267 4 270
271 3 272
271 1 276
271 5 280
272 0 273
272 4 274
272 2 275
276 0 277
276 3 278
276 4 279
280 5 281
280 4 282
280 1 283
284 5 285
284 4 298
284 1 311
285 3 286
285 4 290
285 5 294
286 4 287
286 0 288
286 1 289
290 5 291
290 4 292
290 3 293
294 0 295
294 5 296
294 3 297
298 1 299
298 4 303
298 5 307
299 2 300
299 5 301
299 1 302
303 3 304
303 0 305
303 5 306
307 4 308
307 3 309
307 1 310
311 1 312
311 4 316
311 5 320
312 3 313
312 0 314
312 5 315
316 2 317
316 5 318
316 4 319
320 0 321
320 1 322
320 2 323
324 4 325
324 3 338
324 1 351
325 1 326
325 4 330
325 3 334
326 3 327
326 5 328
326 1 329
330 2 331
330 0 332
330 3 333
334 1 335
334 2 336
334 0 337
338 5 339
338 4 343
338 2 347
339 3 340
339 1 341
339 2 342
343 5 344
343 4 345
343 2 346
347 0 348
347 2 349
347 4 350
351 1 352
351 4 356
351 3 360
352 2 353
352 0 354
352 3 355
356 1 357
356 2 358
356 0 359
360 2 361
360 4 362
360 0 363
)";
#define tiii tuple<int,int,int>
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6+10;
const int N = 6;
int tp[mxn];
vector<pii> tree[mxn];
int pw[N+1];
int ep = 0;
const int lim = 10000;
vector<short> param[mxn];
const short C = 6;
int encode(vector<short> v){
assert(v.size() == N);
int re = 0;
for(int i = 0;i<v.size();i++){
re += pw[i]*v[i];
}
return re;
}
vector<short> decode(int k){
vector<short> re(N);
for(short i = 0;i<N;i++){
re[i] = k%N;
k/=N;
}
return re;
}
short f(int opid,int val,bool p = false){
auto v = param[opid];
auto arr = decode(val);
sort(v.begin(),v.begin()+3,[&](short a,short b){return arr[a]<arr[b];});
assert(arr[v[1]]>arr[v[0]]&&arr[v[2]]>arr[v[1]]);
short re = -1;
if(v.back() == 1)re = v[2];
else if(v.back() == 2)re = v[0];
else if(v.back() == 3)re = v[1];
else{
for(short i = 0;i<3;i++){
if(arr[v[i]]>arr[v[3]]){
re = v[i];
break;
}
if(i == 2)re = v[0];
}
}
if(p){
cerr<<"F: ";for(auto &i:arr)cerr<<i<<' ';cerr<<"::"<<endl;
for(auto &i:v)cerr<<i<<',';cerr<<endl;
cerr<<re<<endl;
}
return re;
}
void makeparam(){
int pt = 0;
for(short i = 0;i<N;i++){
for(short j = i+1;j<N;j++){
for(short k = j+1;k<N;k++){
param[pt] = {i,j,k,1};
pt++;
param[pt] = {i,j,k,2};
pt++;
param[pt] = {i,j,k,3};
pt++;
for(short l = 0;l<N;l++){
if(l == i||l == j||l == k)continue;
param[pt] = {i,j,k,l,4};
pt++;
}
}
}
}
cerr<<"PARAM = "<<pt<<endl;
}
void extend(vector<short> &v){
int now = 0;
int val = encode(v);
while(tp[now] != -1){
int tar = f(tp[now],val);
for(auto [id,nxt]:tree[now]){
if(id == tar){
now = nxt;
break;
}
}
}
assert(tp[now] == -1);
tp[now] = val;
return;
}
void init(int T) {
memset(tp,-1,sizeof(tp));
pw[0] = 1;
for(int i = 1;i<=N;i++)pw[i] = pw[i-1]*N;
makeparam();
stringstream ss(inp);
int n;
ss>>n;
for(int i = 0;i<n;i++)ss>>tp[i];
for(int i = 1;i<n;i++){
int a,b,c;
ss>>a>>b>>c;
tree[a].push_back(pii(b,c));
}
int ptr = n;
//cout<<"n = "<<n<<endl;
for(int i = 0;i<n;i++){
cerr<<i<<endl;
assert(tp[i] != -1);
if(tree[i].empty()){
auto tv = param[tp[i]];
tree[i].push_back(pii(tv[0],ptr++));
tree[i].push_back(pii(tv[1],ptr++));
tree[i].push_back(pii(tv[2],ptr++));
}
}
cerr<<"TREE IN! "<<endl;
vector<short> perm;
for(int i = 0;i<N;i++)perm.push_back(i);
do{
extend(perm);
}while(next_permutation(perm.begin(),perm.end()));
}
int ask(int opid){
assert(opid>=0);
auto v = param[opid];
//cerr<<"ASK: ";for(auto &i:v)cerr<<i<<':';
if(v.back() == 1)return getHeaviest(v[0]+1,v[1]+1,v[2]+1)-1;
else if(v.back() == 2)return getLightest(v[0]+1,v[1]+1,v[2]+1)-1;
else if(v.back() == 3)return getMedian(v[0]+1,v[1]+1,v[2]+1)-1;
else return getNextLightest(v[0]+1,v[1]+1,v[2]+1,v[3]+1)-1;
}
void orderCoins() {
int now = 0;
while(!tree[now].empty()){
//cerr<<tp[now]<<"::";
int tmp = ask(tp[now]);
//cerr<<":::"<<tmp<<endl;
for(auto &j:tree[now]){
if(j.fs == tmp){
now = j.sc;
break;
}
}
}
//cerr<<"f(0,tp[now]): "<<TREE::f(0,tp[now],true)<<endl;
auto tmp = decode(tp[now]);
//cerr<<"TMP: ";for(auto &i:tmp)cerr<<i<<' ';cerr<<endl;
auto ans = tmp;
for(int i = 0;i<N;i++)ans[tmp[i]] = i;
//cerr<<"ANSWEr: ";for(auto &i:ans)cerr<<i<<' ';cerr<<endl;
int re[N];
for(int i = 0;i<N;i++)re[i] = ans[i]+1;
answer(re);
return;
}
