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