#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
typedef int Vert;
typedef int Cost;
typedef pair<Cost,Vert> Edge;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
static const Cost INF = 0x1fffffff;
vector<Cost> dijkstra(const Graph& G, int S)
{
priority_queue<Edge, vector<Edge>, greater<Edge>> Q;
Q.emplace(0, S);
vector<Cost> d(G.size(), INF);
while( !Q.empty() )
{
Vert v = Q.top().second;
Cost c = Q.top().first;
Q.pop();
if(d[v]<INF)
continue;
d[v] = c;
for(const Edge& cu: G[v])
if(d[cu.second]==INF)
Q.emplace(c+cu.first, cu.second);
}
return d;
}
class DrivingPlans { public:
int count(int N, vector <int> A, vector <int> B, vector <int> C)
{
vector<bool> inf_node(N);
for(int i=0; i<A.size(); ++i) {
Vert a = A[i] - 1;
Vert b = B[i] - 1;
Cost c = C[i];
if(c == 0)
inf_node[a] = inf_node[b] = true;
}
Graph G(N);
for(int i=0; i<A.size(); ++i) {
Vert a = A[i] - 1;
Vert b = B[i] - 1;
Cost c = C[i];
G[a].emplace_back(c, b);
G[b].emplace_back(c, a);
}
vector<Cost> ds = dijkstra(G, 0);
vector<Cost> dt = dijkstra(G, N-1);
Cost st = ds[N-1];
if(st == INF)
return 0;
for(Vert v=0; v<N; ++v)
if(inf_node[v] && ds[v]+dt[v]==st)
return -1;
vector<vector<int>> T(N);
for(int i=0; i<A.size(); ++i) {
Vert a = A[i] - 1;
Vert b = B[i] - 1;
Cost c = C[i];
if(ds[a]+c+dt[b] == st)
T[a].emplace_back(b);
if(ds[b]+c+dt[a] == st)
T[b].emplace_back(a);
}
vector<int> memo(N, -1);
const unsigned MODVAL = 1000000009;
function<int(Vert)> rec; rec = [&](Vert v) {
if(v == N-1)
return 1;
if(memo[v] >= 0)
return memo[v];
LL total = 0;
for(Vert u: T[v])
total += rec(u);
return memo[v] = int(total % MODVAL);
};
return rec(0);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, DrivingPlans().count(N, A, B, C));}
int main(){
CASE(0)
int N = 4;
int A_[] = {1,1,2,3};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,3,4,4};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int C_[] = {1,1,1,1};
vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
int _ = 2;
END
CASE(1)
int N = 4;
int A_[] = {1,1,2,3};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,3,4,4};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int C_[] = {1,1,1,0};
vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
int _ = -1;
END
CASE(2)
int N = 7;
int A_[] = {1,1,2,3,4,4,5,6};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,3,4,4,5,6,7,7};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int C_[] = {1,1,2,2,3,3,4,4};
vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
int _ = 4;
END
CASE(3)
int N = 1333;
int A_[] = {1,2,1,3,4,3,5,6,5,7,8,7,9,10,9,11,12,11,13,14,13,15,16,15,17,18,17,19,20,19,21,22,21,23,24,23,25,26,25,27,28,27,29,30,29,31,32,31,33,34,33,35,36,35,37,38,37,39,40,39,41,42,41,43,44,43,45,46,45,47,48,47,49,50,49,51,52,51,53,54,53,55,56,55,57,58,57,59,60,59,61,62,61,63,64,63,65,66,65,67,68,67,69,70,69,71,72,71,73,74,73,75,76,75,77,78,77,79,80,79,81,82,81,83,84,83,85,86,85,87,88,87,89,90,89,91,92,91,93,94,93,95,96,95,97,98,97,99,100,99,101,102,101,103,104,103,105,106,105,107,108,107,109,110,109,111,112,111,113,114,113,115,116,115,117,118,117,119,120,119,121,122,121,123,124,123,125,126,125,127,128,127,129,130,129,131,132,131,133,134,133,135,136,135,137,138,137,139,140,139,141,142,141,143,144,143,145,146,145,147,148,147,149,150,149,151,152,151,153,154,153,155,156,155,157,158,157,159,160,159,161,162,161,163,164,163,165,166,165,167,168,167,169,170,169,171,172,171,173,174,173,175,176,175,177,178,177,179,180,179,181,182,181,183,184,183,185,186,185,187,188,187,189,190,189,191,192,191,193,194,193,195,196,195,197,198,197,199,200,199,201,202,201,203,204,203,205,206,205,207,208,207,209,210,209,211,212,211,213,214,213,215,216,215,217,218,217,219,220,219,221,222,221,223,224,223,225,226,225,227,228,227,229,230,229,231,232,231,233,234,233,235,236,235,237,238,237,239,240,239,241,242,241,243,244,243,245,246,245,247,248,247,249,250,249,251,252,251,253,254,253,255,256,255,257,258,257,259,260,259,261,262,261,263,264,263,265,266,265,267,268,267,269,270,269,271,272,271,273,274,273,275,276,275,277,278,277,279,280,279,281,282,281,283,284,283,285,286,285,287,288,287,289,290,289,291,292,291,293,294,293,295,296,295,297,298,297,299,300,299,301,302,301,303,304,303,305,306,305,307,308,307,309,310,309,311,312,311,313,314,313,315,316,315,317,318,317,319,320,319,321,322,321,323,324,323,325,326,325,327,328,327,329,330,329,331,332,331,333,334,333,335,336,335,337,338,337,339,340,339,341,342,341,343,344,343,345,346,345,347,348,347,349,350,349,351,352,351,353,354,353,355,356,355,357,358,357,359,360,359,361,362,361,363,364,363,365,366,365,367,368,367,369,370,369,371,372,371,373,374,373,375,376,375,377,378,377,379,380,379,381,382,381,383,384,383,385,386,385,387,388,387,389,390,389,391,392,391,393,394,393,395,396,395,397,398,397,399,400,399,401,402,401,403,404,403,405,406,405,407,408,407,409,410,409,411,412,411,413,414,413,415,416,415,417,418,417,419,420,419,421,422,421,423,424,423,425,426,425,427,428,427,429,430,429,431,432,431,433,434,433,435,436,435,437,438,437,439,440,439,441,442,441,443,444,443,445,446,445,447,448,447,449,450,449,451,452,451,453,454,453,455,456,455,457,458,457,459,460,459,461,462,461,463,464,463,465,466,465,467,468,467,469,470,469,471,472,471,473,474,473,475,476,475,477,478,477,479,480,479,481,482,481,483,484,483,485,486,485,487,488,487,489,490,489,491,492,491,493,494,493,495,496,495,497,498,497,499,500,499,501,502,501,503,504,503,505,506,505,507,508,507,509,510,509,511,512,511,513,514,513,515,516,515,517,518,517,519,520,519,521,522,521,523,524,523,525,526,525,527,528,527,529,530,529,531,532,531,533,534,533,535,536,535,537,538,537,539,540,539,541,542,541,543,544,543,545,546,545,547,548,547,549,550,549,551,552,551,553,554,553,555,556,555,557,558,557,559,560,559,561,562,561,563,564,563,565,566,565,567,568,567,569,570,569,571,572,571,573,574,573,575,576,575,577,578,577,579,580,579,581,582,581,583,584,583,585,586,585,587,588,587,589,590,589,591,592,591,593,594,593,595,596,595,597,598,597,599,600,599,601,602,601,603,604,603,605,606,605,607,608,607,609,610,609,611,612,611,613,614,613,615,616,615,617,618,617,619,620,619,621,622,621,623,624,623,625,626,625,627,628,627,629,630,629,631,632,631,633,634,633,635,636,635,637,638,637,639,640,639,641,642,641,643,644,643,645,646,645,647,648,647,649,650,649,651,652,651,653,654,653,655,656,655,657,658,657,659,660,659,661,662,661,663,664,663,665,666,665,667,668,667,669,670,669,671,672,671,673,674,673,675,676,675,677,678,677,679,680,679,681,682,681,683,684,683,685,686,685,687,688,687,689,690,689,691,692,691,693,694,693,695,696,695,697,698,697,699,700,699,701,702,701,703,704,703,705,706,705,707,708,707,709,710,709,711,712,711,713,714,713,715,716,715,717,718,717,719,720,719,721,722,721,723,724,723,725,726,725,727,728,727,729,730,729,731,732,731,733,734,733,735,736,735,737,738,737,739,740,739,741,742,741,743,744,743,745,746,745,747,748,747,749,750,749,751,752,751,753,754,753,755,756,755,757,758,757,759,760,759,761,762,761,763,764,763,765,766,765,767,768,767,769,770,769,771,772,771,773,774,773,775,776,775,777,778,777,779,780,779,781,782,781,783,784,783,785,786,785,787,788,787,789,790,789,791,792,791,793,794,793,795,796,795,797,798,797,799,800,799,801,802,801,803,804,803,805,806,805,807,808,807,809,810,809,811,812,811,813,814,813,815,816,815,817,818,817,819,820,819,821,822,821,823,824,823,825,826,825,827,828,827,829,830,829,831,832,831,833,834,833,835,836,835,837,838,837,839,840,839,841,842,841,843,844,843,845,846,845,847,848,847,849,850,849,851,852,851,853,854,853,855,856,855,857,858,857,859,860,859,861,862,861,863,864,863,865,866,865,867,868,867,869,870,869,871,872,871,873,874,873,875,876,875,877,878,877,879,880,879,881,882,881,883,884,883,885,886,885,887,888,887,889,890,889,891,892,891,893,894,893,895,896,895,897,898,897,899,900,899,901,902,901,903,904,903,905,906,905,907,908,907,909,910,909,911,912,911,913,914,913,915,916,915,917,918,917,919,920,919,921,922,921,923,924,923,925,926,925,927,928,927,929,930,929,931,932,931,933,934,933,935,936,935,937,938,937,939,940,939,941,942,941,943,944,943,945,946,945,947,948,947,949,950,949,951,952,951,953,954,953,955,956,955,957,958,957,959,960,959,961,962,961,963,964,963,965,966,965,967,968,967,969,970,969,971,972,971,973,974,973,975,976,975,977,978,977,979,980,979,981,982,981,983,984,983,985,986,985,987,988,987,989,990,989,991,992,991,993,994,993,995,996,995,997,998,997,999,1000,999,1001,1002,1001,1003,1004,1003,1005,1006,1005,1007,1008,1007,1009,1010,1009,1011,1012,1011,1013,1014,1013,1015,1016,1015,1017,1018,1017,1019,1020,1019,1021,1022,1021,1023,1024,1023,1025,1026,1025,1027,1028,1027,1029,1030,1029,1031,1032,1031,1033,1034,1033,1035,1036,1035,1037,1038,1037,1039,1040,1039,1041,1042,1041,1043,1044,1043,1045,1046,1045,1047,1048,1047,1049,1050,1049,1051,1052,1051,1053,1054,1053,1055,1056,1055,1057,1058,1057,1059,1060,1059,1061,1062,1061,1063,1064,1063,1065,1066,1065,1067,1068,1067,1069,1070,1069,1071,1072,1071,1073,1074,1073,1075,1076,1075,1077,1078,1077,1079,1080,1079,1081,1082,1081,1083,1084,1083,1085,1086,1085,1087,1088,1087,1089,1090,1089,1091,1092,1091,1093,1094,1093,1095,1096,1095,1097,1098,1097,1099,1100,1099,1101,1102,1101,1103,1104,1103,1105,1106,1105,1107,1108,1107,1109,1110,1109,1111,1112,1111,1113,1114,1113,1115,1116,1115,1117,1118,1117,1119,1120,1119,1121,1122,1121,1123,1124,1123,1125,1126,1125,1127,1128,1127,1129,1130,1129,1131,1132,1131,1133,1134,1133,1135,1136,1135,1137,1138,1137,1139,1140,1139,1141,1142,1141,1143,1144,1143,1145,1146,1145,1147,1148,1147,1149,1150,1149,1151,1152,1151,1153,1154,1153,1155,1156,1155,1157,1158,1157,1159,1160,1159,1161,1162,1161,1163,1164,1163,1165,1166,1165,1167,1168,1167,1169,1170,1169,1171,1172,1171,1173,1174,1173,1175,1176,1175,1177,1178,1177,1179,1180,1179,1181,1182,1181,1183,1184,1183,1185,1186,1185,1187,1188,1187,1189,1190,1189,1191,1192,1191,1193,1194,1193,1195,1196,1195,1197,1198,1197,1199,1200,1199,1201,1202,1201,1203,1204,1203,1205,1206,1205,1207,1208,1207,1209,1210,1209,1211,1212,1211,1213,1214,1213,1215,1216,1215,1217,1218,1217,1219,1220,1219,1221,1222,1221,1223,1224,1223,1225,1226,1225,1227,1228,1227,1229,1230,1229,1231,1232,1231,1233,1234,1233,1235,1236,1235,1237,1238,1237,1239,1240,1239,1241,1242,1241,1243,1244,1243,1245,1246,1245,1247,1248,1247,1249,1250,1249,1251,1252,1251,1253,1254,1253,1255,1256,1255,1257,1258,1257,1259,1260,1259,1261,1262,1261,1263,1264,1263,1265,1266,1265,1267,1268,1267,1269,1270,1269,1271,1272,1271,1273,1274,1273,1275,1276,1275,1277,1278,1277,1279,1280,1279,1281,1282,1281,1283,1284,1283,1285,1286,1285,1287,1288,1287,1289,1290,1289,1291,1292,1291,1293,1294,1293,1295,1296,1295,1297,1298,1297,1299,1300,1299,1301,1302,1301,1303,1304,1303,1305,1306,1305,1307,1308,1307,1309,1310,1309,1311,1312,1311,1313,1314,1313,1315,1316,1315,1317,1318,1317,1319,1320,1319,1321,1322,1321,1323,1324,1323,1325,1326,1325,1327,1328,1327,1329,1330,1329,1331,1332,1331};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,3,3,4,5,5,6,7,7,8,9,9,10,11,11,12,13,13,14,15,15,16,17,17,18,19,19,20,21,21,22,23,23,24,25,25,26,27,27,28,29,29,30,31,31,32,33,33,34,35,35,36,37,37,38,39,39,40,41,41,42,43,43,44,45,45,46,47,47,48,49,49,50,51,51,52,53,53,54,55,55,56,57,57,58,59,59,60,61,61,62,63,63,64,65,65,66,67,67,68,69,69,70,71,71,72,73,73,74,75,75,76,77,77,78,79,79,80,81,81,82,83,83,84,85,85,86,87,87,88,89,89,90,91,91,92,93,93,94,95,95,96,97,97,98,99,99,100,101,101,102,103,103,104,105,105,106,107,107,108,109,109,110,111,111,112,113,113,114,115,115,116,117,117,118,119,119,120,121,121,122,123,123,124,125,125,126,127,127,128,129,129,130,131,131,132,133,133,134,135,135,136,137,137,138,139,139,140,141,141,142,143,143,144,145,145,146,147,147,148,149,149,150,151,151,152,153,153,154,155,155,156,157,157,158,159,159,160,161,161,162,163,163,164,165,165,166,167,167,168,169,169,170,171,171,172,173,173,174,175,175,176,177,177,178,179,179,180,181,181,182,183,183,184,185,185,186,187,187,188,189,189,190,191,191,192,193,193,194,195,195,196,197,197,198,199,199,200,201,201,202,203,203,204,205,205,206,207,207,208,209,209,210,211,211,212,213,213,214,215,215,216,217,217,218,219,219,220,221,221,222,223,223,224,225,225,226,227,227,228,229,229,230,231,231,232,233,233,234,235,235,236,237,237,238,239,239,240,241,241,242,243,243,244,245,245,246,247,247,248,249,249,250,251,251,252,253,253,254,255,255,256,257,257,258,259,259,260,261,261,262,263,263,264,265,265,266,267,267,268,269,269,270,271,271,272,273,273,274,275,275,276,277,277,278,279,279,280,281,281,282,283,283,284,285,285,286,287,287,288,289,289,290,291,291,292,293,293,294,295,295,296,297,297,298,299,299,300,301,301,302,303,303,304,305,305,306,307,307,308,309,309,310,311,311,312,313,313,314,315,315,316,317,317,318,319,319,320,321,321,322,323,323,324,325,325,326,327,327,328,329,329,330,331,331,332,333,333,334,335,335,336,337,337,338,339,339,340,341,341,342,343,343,344,345,345,346,347,347,348,349,349,350,351,351,352,353,353,354,355,355,356,357,357,358,359,359,360,361,361,362,363,363,364,365,365,366,367,367,368,369,369,370,371,371,372,373,373,374,375,375,376,377,377,378,379,379,380,381,381,382,383,383,384,385,385,386,387,387,388,389,389,390,391,391,392,393,393,394,395,395,396,397,397,398,399,399,400,401,401,402,403,403,404,405,405,406,407,407,408,409,409,410,411,411,412,413,413,414,415,415,416,417,417,418,419,419,420,421,421,422,423,423,424,425,425,426,427,427,428,429,429,430,431,431,432,433,433,434,435,435,436,437,437,438,439,439,440,441,441,442,443,443,444,445,445,446,447,447,448,449,449,450,451,451,452,453,453,454,455,455,456,457,457,458,459,459,460,461,461,462,463,463,464,465,465,466,467,467,468,469,469,470,471,471,472,473,473,474,475,475,476,477,477,478,479,479,480,481,481,482,483,483,484,485,485,486,487,487,488,489,489,490,491,491,492,493,493,494,495,495,496,497,497,498,499,499,500,501,501,502,503,503,504,505,505,506,507,507,508,509,509,510,511,511,512,513,513,514,515,515,516,517,517,518,519,519,520,521,521,522,523,523,524,525,525,526,527,527,528,529,529,530,531,531,532,533,533,534,535,535,536,537,537,538,539,539,540,541,541,542,543,543,544,545,545,546,547,547,548,549,549,550,551,551,552,553,553,554,555,555,556,557,557,558,559,559,560,561,561,562,563,563,564,565,565,566,567,567,568,569,569,570,571,571,572,573,573,574,575,575,576,577,577,578,579,579,580,581,581,582,583,583,584,585,585,586,587,587,588,589,589,590,591,591,592,593,593,594,595,595,596,597,597,598,599,599,600,601,601,602,603,603,604,605,605,606,607,607,608,609,609,610,611,611,612,613,613,614,615,615,616,617,617,618,619,619,620,621,621,622,623,623,624,625,625,626,627,627,628,629,629,630,631,631,632,633,633,634,635,635,636,637,637,638,639,639,640,641,641,642,643,643,644,645,645,646,647,647,648,649,649,650,651,651,652,653,653,654,655,655,656,657,657,658,659,659,660,661,661,662,663,663,664,665,665,666,667,667,668,669,669,670,671,671,672,673,673,674,675,675,676,677,677,678,679,679,680,681,681,682,683,683,684,685,685,686,687,687,688,689,689,690,691,691,692,693,693,694,695,695,696,697,697,698,699,699,700,701,701,702,703,703,704,705,705,706,707,707,708,709,709,710,711,711,712,713,713,714,715,715,716,717,717,718,719,719,720,721,721,722,723,723,724,725,725,726,727,727,728,729,729,730,731,731,732,733,733,734,735,735,736,737,737,738,739,739,740,741,741,742,743,743,744,745,745,746,747,747,748,749,749,750,751,751,752,753,753,754,755,755,756,757,757,758,759,759,760,761,761,762,763,763,764,765,765,766,767,767,768,769,769,770,771,771,772,773,773,774,775,775,776,777,777,778,779,779,780,781,781,782,783,783,784,785,785,786,787,787,788,789,789,790,791,791,792,793,793,794,795,795,796,797,797,798,799,799,800,801,801,802,803,803,804,805,805,806,807,807,808,809,809,810,811,811,812,813,813,814,815,815,816,817,817,818,819,819,820,821,821,822,823,823,824,825,825,826,827,827,828,829,829,830,831,831,832,833,833,834,835,835,836,837,837,838,839,839,840,841,841,842,843,843,844,845,845,846,847,847,848,849,849,850,851,851,852,853,853,854,855,855,856,857,857,858,859,859,860,861,861,862,863,863,864,865,865,866,867,867,868,869,869,870,871,871,872,873,873,874,875,875,876,877,877,878,879,879,880,881,881,882,883,883,884,885,885,886,887,887,888,889,889,890,891,891,892,893,893,894,895,895,896,897,897,898,899,899,900,901,901,902,903,903,904,905,905,906,907,907,908,909,909,910,911,911,912,913,913,914,915,915,916,917,917,918,919,919,920,921,921,922,923,923,924,925,925,926,927,927,928,929,929,930,931,931,932,933,933,934,935,935,936,937,937,938,939,939,940,941,941,942,943,943,944,945,945,946,947,947,948,949,949,950,951,951,952,953,953,954,955,955,956,957,957,958,959,959,960,961,961,962,963,963,964,965,965,966,967,967,968,969,969,970,971,971,972,973,973,974,975,975,976,977,977,978,979,979,980,981,981,982,983,983,984,985,985,986,987,987,988,989,989,990,991,991,992,993,993,994,995,995,996,997,997,998,999,999,1000,1001,1001,1002,1003,1003,1004,1005,1005,1006,1007,1007,1008,1009,1009,1010,1011,1011,1012,1013,1013,1014,1015,1015,1016,1017,1017,1018,1019,1019,1020,1021,1021,1022,1023,1023,1024,1025,1025,1026,1027,1027,1028,1029,1029,1030,1031,1031,1032,1033,1033,1034,1035,1035,1036,1037,1037,1038,1039,1039,1040,1041,1041,1042,1043,1043,1044,1045,1045,1046,1047,1047,1048,1049,1049,1050,1051,1051,1052,1053,1053,1054,1055,1055,1056,1057,1057,1058,1059,1059,1060,1061,1061,1062,1063,1063,1064,1065,1065,1066,1067,1067,1068,1069,1069,1070,1071,1071,1072,1073,1073,1074,1075,1075,1076,1077,1077,1078,1079,1079,1080,1081,1081,1082,1083,1083,1084,1085,1085,1086,1087,1087,1088,1089,1089,1090,1091,1091,1092,1093,1093,1094,1095,1095,1096,1097,1097,1098,1099,1099,1100,1101,1101,1102,1103,1103,1104,1105,1105,1106,1107,1107,1108,1109,1109,1110,1111,1111,1112,1113,1113,1114,1115,1115,1116,1117,1117,1118,1119,1119,1120,1121,1121,1122,1123,1123,1124,1125,1125,1126,1127,1127,1128,1129,1129,1130,1131,1131,1132,1133,1133,1134,1135,1135,1136,1137,1137,1138,1139,1139,1140,1141,1141,1142,1143,1143,1144,1145,1145,1146,1147,1147,1148,1149,1149,1150,1151,1151,1152,1153,1153,1154,1155,1155,1156,1157,1157,1158,1159,1159,1160,1161,1161,1162,1163,1163,1164,1165,1165,1166,1167,1167,1168,1169,1169,1170,1171,1171,1172,1173,1173,1174,1175,1175,1176,1177,1177,1178,1179,1179,1180,1181,1181,1182,1183,1183,1184,1185,1185,1186,1187,1187,1188,1189,1189,1190,1191,1191,1192,1193,1193,1194,1195,1195,1196,1197,1197,1198,1199,1199,1200,1201,1201,1202,1203,1203,1204,1205,1205,1206,1207,1207,1208,1209,1209,1210,1211,1211,1212,1213,1213,1214,1215,1215,1216,1217,1217,1218,1219,1219,1220,1221,1221,1222,1223,1223,1224,1225,1225,1226,1227,1227,1228,1229,1229,1230,1231,1231,1232,1233,1233,1234,1235,1235,1236,1237,1237,1238,1239,1239,1240,1241,1241,1242,1243,1243,1244,1245,1245,1246,1247,1247,1248,1249,1249,1250,1251,1251,1252,1253,1253,1254,1255,1255,1256,1257,1257,1258,1259,1259,1260,1261,1261,1262,1263,1263,1264,1265,1265,1266,1267,1267,1268,1269,1269,1270,1271,1271,1272,1273,1273,1274,1275,1275,1276,1277,1277,1278,1279,1279,1280,1281,1281,1282,1283,1283,1284,1285,1285,1286,1287,1287,1288,1289,1289,1290,1291,1291,1292,1293,1293,1294,1295,1295,1296,1297,1297,1298,1299,1299,1300,1301,1301,1302,1303,1303,1304,1305,1305,1306,1307,1307,1308,1309,1309,1310,1311,1311,1312,1313,1313,1314,1315,1315,1316,1317,1317,1318,1319,1319,1320,1321,1321,1322,1323,1323,1324,1325,1325,1326,1327,1327,1328,1329,1329,1330,1331,1331,1332,1333,1333};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int C_[] = {1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2};
vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
int _ = -1;
END
CASE(4)
int N = 4;
int A_[] = {1, 1, 2};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {4, 2, 3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int C_[] = {1, 2, 0};
vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
int _ = 1;
END
}
// END CUT HERE