CameraService: Add unit tests for DistortionMapper
- Make cameraserver_test test module reachable by build system
- Fix minor compilation error in CameraProviderManagerTest
- Add tests to verify:
- Initialization of DistortionMapper
- Transforms with an identity distortion function
- Round-trip transform ~1e6 points with a large distortion function
- Raw to corrected transform compared against OpenCV undistortPoints,
using python to generate the comparison coordinate lists as a C++
header
Test: atest cameraservice_test
Bug: 79885994
Change-Id: Iae3d6f9de2e6c79dd5cea5ca35ee5100b38441f4
diff --git a/services/camera/libcameraservice/Android.mk b/services/camera/libcameraservice/Android.mk
index 5697a87..96261ab 100644
--- a/services/camera/libcameraservice/Android.mk
+++ b/services/camera/libcameraservice/Android.mk
@@ -97,3 +97,8 @@
LOCAL_MODULE:= libcameraservice
include $(BUILD_SHARED_LIBRARY)
+
+# Build tests too
+
+include $(LOCAL_PATH)/tests/Android.mk
+
diff --git a/services/camera/libcameraservice/device3/DistortionMapper.cpp b/services/camera/libcameraservice/device3/DistortionMapper.cpp
index 82923bd..9229079 100644
--- a/services/camera/libcameraservice/device3/DistortionMapper.cpp
+++ b/services/camera/libcameraservice/device3/DistortionMapper.cpp
@@ -195,6 +195,7 @@
}
mValidMapping = true;
+ // Need to recalculate grid
mValidGrids = false;
return OK;
diff --git a/services/camera/libcameraservice/tests/Android.mk b/services/camera/libcameraservice/tests/Android.mk
index 37a05c2..f77069c 100644
--- a/services/camera/libcameraservice/tests/Android.mk
+++ b/services/camera/libcameraservice/tests/Android.mk
@@ -18,6 +18,7 @@
LOCAL_SRC_FILES:= $(call all-cpp-files-under, .)
LOCAL_SHARED_LIBRARIES := \
+ libbase \
libcutils \
libcameraservice \
libhidlbase \
diff --git a/services/camera/libcameraservice/tests/CameraProviderManagerTest.cpp b/services/camera/libcameraservice/tests/CameraProviderManagerTest.cpp
index c1d6e85..ef93d9a 100644
--- a/services/camera/libcameraservice/tests/CameraProviderManagerTest.cpp
+++ b/services/camera/libcameraservice/tests/CameraProviderManagerTest.cpp
@@ -190,6 +190,7 @@
hardware::camera::common::V1_0::CameraDeviceStatus) override {}
void onTorchStatusChanged(const String8 &,
hardware::camera::common::V1_0::TorchModeStatus) override {}
+ void onNewProviderRegistered() override {}
};
TEST(CameraProviderManagerTest, InitializeTest) {
diff --git a/services/camera/libcameraservice/tests/DistortionMapperComp.py b/services/camera/libcameraservice/tests/DistortionMapperComp.py
new file mode 100644
index 0000000..dea36a7
--- /dev/null
+++ b/services/camera/libcameraservice/tests/DistortionMapperComp.py
@@ -0,0 +1,47 @@
+# Calculates comparison output values for DistortionMapperTest.cpp:CompareToOpenCV
+#
+# Assumes a python that has numpy and cv2 (OpenCV) available
+
+import numpy as np
+import cv2
+
+Fx = 1000
+Fy = 1000
+Cx = 500
+Cy = 500
+# s = 0 - not supported by OpenCV
+
+K = np.array([[Fx, 0, Cx],[0, Fy, Cy],[0, 0, 1]])
+
+# Order is k1, k2, t1, t2, k3
+dist = np.array([0.1, -0.003, 0.02, 0.01, 0.004])
+
+np.random.seed(1234)
+
+activeArray = np.array([[1000, 750]])
+
+rawCoords = np.floor(np.random.rand(1000,2) * activeArray)
+
+# OpenCV needs either row count or col count = 1 for some reason
+rawCoords2 = rawCoords.reshape(-1, 1, 2)
+
+# P is the output camera matrix, K is the input; use the same for both
+expCoords = cv2.undistortPoints(rawCoords2, K, dist, P = K)
+
+with open('DistortionMapperTest_OpenCvData.h','w') as f:
+ f.write('// Generated by DistortionMapperComp.py\n');
+ f.write('// for use by DistortionMapperTest.cpp\n\n');
+
+ f.write('namespace openCvData {\n')
+ f.write('std::array<int32_t, %d> rawCoords = {\n' % (rawCoords.shape[0] * rawCoords.shape[1]))
+ for i in range(rawCoords.shape[0]):
+ f.write(' %d, %d,\n' % (rawCoords[i][0], rawCoords[i][1]))
+ f.write('};\n')
+
+ f.write('std::array<int32_t, %d> expCoords = {\n' % (expCoords.shape[0] * expCoords.shape[2]))
+ for i in range(expCoords.shape[0]):
+ f.write(' %d, %d,\n' % (expCoords[i][0][0], expCoords[i][0][1]))
+ f.write('};\n')
+ f.write('} // namespace openCvData\n')
+
+print "DistortionMapperTest_OpenCvData.h generated"
diff --git a/services/camera/libcameraservice/tests/DistortionMapperTest.cpp b/services/camera/libcameraservice/tests/DistortionMapperTest.cpp
new file mode 100644
index 0000000..b489931
--- /dev/null
+++ b/services/camera/libcameraservice/tests/DistortionMapperTest.cpp
@@ -0,0 +1,278 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_NDEBUG 0
+#define LOG_TAG "DistortionMapperTest"
+
+#include <random>
+
+#include <gtest/gtest.h>
+#include <android-base/stringprintf.h>
+#include <android-base/chrono_utils.h>
+
+#include "../device3/DistortionMapper.h"
+
+using namespace android;
+using namespace android::camera3;
+
+
+int32_t testActiveArray[] = {100, 100, 1000, 750};
+
+float testICal[] = { 1000.f, 1000.f, 500.f, 500.f, 0.f };
+
+float identityDistortion[] = { 0.f, 0.f, 0.f, 0.f, 0.f};
+
+std::array<int32_t, 12> basicCoords = {
+ 0, 0,
+ testActiveArray[2] - 1, 0,
+ testActiveArray[2] - 1, testActiveArray[3] - 1,
+ 0, testActiveArray[3] - 1,
+ testActiveArray[2] / 2, testActiveArray[3] / 2,
+ 251, 403 // A particularly bad coordinate for current grid count/array size
+};
+
+
+void setupTestMapper(DistortionMapper *m, float distortion[5]) {
+ CameraMetadata deviceInfo;
+
+ deviceInfo.update(ANDROID_SENSOR_INFO_PRE_CORRECTION_ACTIVE_ARRAY_SIZE,
+ testActiveArray, 4);
+
+ deviceInfo.update(ANDROID_LENS_INTRINSIC_CALIBRATION,
+ testICal, 5);
+
+ deviceInfo.update(ANDROID_LENS_DISTORTION,
+ distortion, 5);
+
+ m->setupStaticInfo(deviceInfo);
+}
+
+TEST(DistortionMapperTest, Initialization) {
+ CameraMetadata deviceInfo;
+
+ ASSERT_FALSE(DistortionMapper::isDistortionSupported(deviceInfo));
+
+ uint8_t distortionModes[] =
+ {ANDROID_DISTORTION_CORRECTION_MODE_OFF,
+ ANDROID_DISTORTION_CORRECTION_MODE_FAST,
+ ANDROID_DISTORTION_CORRECTION_MODE_HIGH_QUALITY};
+
+ deviceInfo.update(ANDROID_DISTORTION_CORRECTION_AVAILABLE_MODES,
+ distortionModes, 1);
+
+ ASSERT_FALSE(DistortionMapper::isDistortionSupported(deviceInfo));
+
+ deviceInfo.update(ANDROID_DISTORTION_CORRECTION_AVAILABLE_MODES,
+ distortionModes, 3);
+
+ ASSERT_TRUE(DistortionMapper::isDistortionSupported(deviceInfo));
+
+ DistortionMapper m;
+
+ ASSERT_FALSE(m.calibrationValid());
+
+ ASSERT_NE(m.setupStaticInfo(deviceInfo), OK);
+
+ ASSERT_FALSE(m.calibrationValid());
+
+ deviceInfo.update(ANDROID_SENSOR_INFO_PRE_CORRECTION_ACTIVE_ARRAY_SIZE,
+ testActiveArray, 4);
+
+ deviceInfo.update(ANDROID_LENS_INTRINSIC_CALIBRATION,
+ testICal, 5);
+
+ deviceInfo.update(ANDROID_LENS_DISTORTION,
+ identityDistortion, 5);
+
+ ASSERT_EQ(m.setupStaticInfo(deviceInfo), OK);
+
+ ASSERT_TRUE(m.calibrationValid());
+
+ CameraMetadata captureResult;
+
+ ASSERT_NE(m.updateCalibration(captureResult), OK);
+
+ captureResult.update(ANDROID_LENS_INTRINSIC_CALIBRATION,
+ testICal, 5);
+ captureResult.update(ANDROID_LENS_DISTORTION,
+ identityDistortion, 5);
+
+ ASSERT_EQ(m.updateCalibration(captureResult), OK);
+
+}
+
+TEST(DistortionMapperTest, IdentityTransform) {
+ status_t res;
+
+ DistortionMapper m;
+ setupTestMapper(&m, identityDistortion);
+
+ auto coords = basicCoords;
+ res = m.mapCorrectedToRaw(coords.data(), 5);
+ ASSERT_EQ(res, OK);
+
+ for (size_t i = 0; i < coords.size(); i++) {
+ EXPECT_EQ(coords[i], basicCoords[i]);
+ }
+
+ res = m.mapRawToCorrected(coords.data(), 5);
+ ASSERT_EQ(res, OK);
+
+ for (size_t i = 0; i < coords.size(); i++) {
+ EXPECT_EQ(coords[i], basicCoords[i]);
+ }
+
+ std::array<int32_t, 8> rects = {
+ 0, 0, 100, 100,
+ testActiveArray[2] - 100, testActiveArray[3]-100, 100, 100
+ };
+
+ auto rectsOrig = rects;
+ res = m.mapCorrectedRectToRaw(rects.data(), 2);
+ ASSERT_EQ(res, OK);
+
+ for (size_t i = 0; i < rects.size(); i++) {
+ EXPECT_EQ(rects[i], rectsOrig[i]);
+ }
+
+ res = m.mapRawRectToCorrected(rects.data(), 2);
+ ASSERT_EQ(res, OK);
+
+ for (size_t i = 0; i < rects.size(); i++) {
+ EXPECT_EQ(rects[i], rectsOrig[i]);
+ }
+}
+
+TEST(DistortionMapperTest, LargeTransform) {
+ status_t res;
+ constexpr int maxAllowedPixelError = 2; // Maximum per-pixel error allowed
+ constexpr int bucketsPerPixel = 3; // Histogram granularity
+
+ unsigned int seed = 1234; // Ensure repeatability for debugging
+ const size_t coordCount = 1e6; // Number of random test points
+
+ float bigDistortion[] = {0.1, -0.003, 0.004, 0.02, 0.01};
+
+ DistortionMapper m;
+ setupTestMapper(&m, bigDistortion);
+
+ std::default_random_engine gen(seed);
+
+ std::uniform_int_distribution<int> x_dist(0, testActiveArray[2] - 1);
+ std::uniform_int_distribution<int> y_dist(0, testActiveArray[3] - 1);
+
+ std::vector<int32_t> randCoords(coordCount * 2);
+
+ for (size_t i = 0; i < randCoords.size(); i += 2) {
+ randCoords[i] = x_dist(gen);
+ randCoords[i + 1] = y_dist(gen);
+ }
+
+ randCoords.insert(randCoords.end(), basicCoords.begin(), basicCoords.end());
+
+ auto origCoords = randCoords;
+
+ base::Timer correctedToRawTimer;
+ res = m.mapCorrectedToRaw(randCoords.data(), randCoords.size() / 2);
+ auto correctedToRawDurationMs = correctedToRawTimer.duration();
+ EXPECT_EQ(res, OK);
+
+ base::Timer rawToCorrectedTimer;
+ res = m.mapRawToCorrected(randCoords.data(), randCoords.size() / 2);
+ auto rawToCorrectedDurationMs = rawToCorrectedTimer.duration();
+ EXPECT_EQ(res, OK);
+
+ float correctedToRawDurationPerCoordUs =
+ (std::chrono::duration_cast<std::chrono::duration<double, std::micro>>(
+ correctedToRawDurationMs) / (randCoords.size() / 2) ).count();
+ float rawToCorrectedDurationPerCoordUs =
+ (std::chrono::duration_cast<std::chrono::duration<double, std::micro>>(
+ rawToCorrectedDurationMs) / (randCoords.size() / 2) ).count();
+
+ RecordProperty("CorrectedToRawDurationPerCoordUs",
+ base::StringPrintf("%f", correctedToRawDurationPerCoordUs));
+ RecordProperty("RawToCorrectedDurationPerCoordUs",
+ base::StringPrintf("%f", rawToCorrectedDurationPerCoordUs));
+
+ // Calculate mapping errors after round trip
+ float totalErrorSq = 0;
+ // Basic histogram; buckets go from [N to N+1)
+ std::array<int, maxAllowedPixelError * bucketsPerPixel> histogram = {0};
+ int outOfHistogram = 0;
+
+ for (size_t i = 0; i < randCoords.size(); i += 2) {
+ int xOrig = origCoords[i];
+ int yOrig = origCoords[i + 1];
+ int xMapped = randCoords[i];
+ int yMapped = randCoords[i + 1];
+
+ float errorSq = (xMapped - xOrig) * (xMapped - xOrig) +
+ (yMapped - yOrig) * (yMapped - yOrig);
+
+ EXPECT_LE(errorSq, maxAllowedPixelError * maxAllowedPixelError) << "( " <<
+ xOrig << "," << yOrig << ") -> (" << xMapped << "," << yMapped << ")";
+
+ // Note: Integer coordinates, so histogram will be clumpy; error distances can only be of
+ // form sqrt(X^2+Y^2) where X, Y are integers, so:
+ // 0, 1, sqrt(2), 2, sqrt(5), sqrt(8), 3, sqrt(10), sqrt(13), 4 ...
+ totalErrorSq += errorSq;
+ float errorDist = std::sqrt(errorSq);
+ if (errorDist < maxAllowedPixelError) {
+ int histBucket = static_cast<int>(errorDist * bucketsPerPixel); // rounds down
+ histogram[histBucket]++;
+ } else {
+ outOfHistogram++;
+ }
+ }
+
+ float rmsError = std::sqrt(totalErrorSq / randCoords.size());
+ RecordProperty("RmsError", base::StringPrintf("%f", rmsError));
+ for (size_t i = 0; i < histogram.size(); i++) {
+ std::string label = base::StringPrintf("HistogramBin[%f,%f)",
+ (float)i/bucketsPerPixel, (float)(i + 1)/bucketsPerPixel);
+ RecordProperty(label, histogram[i]);
+ }
+ RecordProperty("HistogramOutOfRange", outOfHistogram);
+}
+
+// Compare against values calculated by OpenCV
+// undistortPoints() method, which is the same as mapRawToCorrected
+// See script DistortionMapperComp.py
+#include "DistortionMapperTest_OpenCvData.h"
+
+TEST(DistortionMapperTest, CompareToOpenCV) {
+ status_t res;
+
+ float bigDistortion[] = {0.1, -0.003, 0.004, 0.02, 0.01};
+
+ // Expect to match within sqrt(2) radius pixels
+ const int32_t maxSqError = 2;
+
+ DistortionMapper m;
+ setupTestMapper(&m, bigDistortion);
+
+ using namespace openCvData;
+
+ res = m.mapRawToCorrected(rawCoords.data(), rawCoords.size() / 2);
+
+ for (size_t i = 0; i < rawCoords.size(); i+=2) {
+ int32_t dist = (rawCoords[i] - expCoords[i]) * (rawCoords[i] - expCoords[i]) +
+ (rawCoords[i + 1] - expCoords[i + 1]) * (rawCoords[i + 1] - expCoords[i + 1]);
+ EXPECT_LE(dist, maxSqError)
+ << "(" << rawCoords[i] << ", " << rawCoords[i + 1] << ") != ("
+ << expCoords[i] << ", " << expCoords[i + 1] << ")";
+ }
+}
diff --git a/services/camera/libcameraservice/tests/DistortionMapperTest_OpenCvData.h b/services/camera/libcameraservice/tests/DistortionMapperTest_OpenCvData.h
new file mode 100644
index 0000000..f996bd5
--- /dev/null
+++ b/services/camera/libcameraservice/tests/DistortionMapperTest_OpenCvData.h
@@ -0,0 +1,2009 @@
+// Generated by DistortionMapperComp.py
+// for use by DistortionMapperTest.cpp
+
+namespace openCvData {
+std::array<int32_t, 2000> rawCoords = {
+ 191, 466,
+ 437, 589,
+ 779, 204,
+ 276, 601,
+ 958, 656,
+ 357, 375,
+ 683, 534,
+ 370, 420,
+ 503, 10,
+ 772, 661,
+ 364, 461,
+ 75, 276,
+ 933, 488,
+ 397, 591,
+ 316, 426,
+ 869, 327,
+ 802, 107,
+ 704, 528,
+ 218, 693,
+ 442, 681,
+ 59, 138,
+ 47, 506,
+ 594, 399,
+ 43, 421,
+ 329, 377,
+ 111, 455,
+ 565, 5,
+ 617, 684,
+ 790, 744,
+ 958, 593,
+ 285, 468,
+ 478, 146,
+ 382, 40,
+ 451, 736,
+ 123, 89,
+ 738, 440,
+ 471, 80,
+ 229, 674,
+ 416, 401,
+ 6, 225,
+ 436, 459,
+ 918, 469,
+ 705, 112,
+ 746, 623,
+ 633, 328,
+ 152, 426,
+ 528, 713,
+ 480, 376,
+ 536, 614,
+ 57, 502,
+ 767, 531,
+ 796, 418,
+ 965, 110,
+ 29, 445,
+ 114, 713,
+ 325, 145,
+ 457, 690,
+ 879, 189,
+ 348, 136,
+ 901, 529,
+ 726, 675,
+ 779, 449,
+ 291, 113,
+ 335, 493,
+ 73, 41,
+ 323, 442,
+ 853, 215,
+ 173, 100,
+ 994, 134,
+ 317, 426,
+ 9, 675,
+ 977, 417,
+ 84, 249,
+ 728, 106,
+ 552, 204,
+ 974, 500,
+ 255, 81,
+ 776, 586,
+ 761, 685,
+ 658, 426,
+ 201, 523,
+ 952, 667,
+ 993, 614,
+ 545, 338,
+ 890, 729,
+ 593, 274,
+ 323, 653,
+ 215, 551,
+ 365, 601,
+ 782, 526,
+ 622, 370,
+ 840, 534,
+ 443, 23,
+ 363, 548,
+ 475, 258,
+ 640, 94,
+ 171, 552,
+ 127, 277,
+ 604, 77,
+ 802, 709,
+ 979, 660,
+ 627, 697,
+ 724, 537,
+ 41, 329,
+ 282, 251,
+ 83, 570,
+ 509, 495,
+ 630, 278,
+ 446, 311,
+ 480, 737,
+ 373, 9,
+ 921, 654,
+ 351, 472,
+ 357, 159,
+ 223, 314,
+ 72, 488,
+ 755, 699,
+ 376, 222,
+ 371, 620,
+ 901, 320,
+ 2, 31,
+ 141, 448,
+ 106, 222,
+ 58, 465,
+ 22, 641,
+ 306, 569,
+ 563, 28,
+ 565, 494,
+ 183, 598,
+ 612, 416,
+ 629, 514,
+ 240, 590,
+ 856, 545,
+ 692, 354,
+ 856, 498,
+ 333, 388,
+ 394, 23,
+ 576, 637,
+ 951, 512,
+ 76, 307,
+ 41, 130,
+ 565, 129,
+ 566, 385,
+ 868, 540,
+ 903, 208,
+ 256, 524,
+ 901, 737,
+ 640, 247,
+ 606, 616,
+ 627, 88,
+ 285, 740,
+ 431, 430,
+ 527, 148,
+ 165, 375,
+ 990, 295,
+ 714, 131,
+ 70, 118,
+ 161, 212,
+ 536, 579,
+ 880, 478,
+ 852, 448,
+ 693, 402,
+ 889, 39,
+ 783, 108,
+ 58, 44,
+ 51, 386,
+ 404, 749,
+ 108, 245,
+ 997, 300,
+ 883, 426,
+ 953, 664,
+ 779, 23,
+ 962, 389,
+ 207, 656,
+ 224, 103,
+ 725, 730,
+ 535, 333,
+ 22, 454,
+ 964, 725,
+ 930, 138,
+ 622, 309,
+ 363, 27,
+ 868, 504,
+ 87, 665,
+ 782, 237,
+ 818, 380,
+ 21, 325,
+ 446, 179,
+ 830, 558,
+ 586, 369,
+ 487, 200,
+ 605, 565,
+ 270, 391,
+ 98, 535,
+ 884, 425,
+ 994, 134,
+ 12, 342,
+ 931, 634,
+ 473, 676,
+ 225, 228,
+ 714, 543,
+ 18, 214,
+ 580, 698,
+ 338, 90,
+ 516, 524,
+ 298, 646,
+ 905, 576,
+ 261, 703,
+ 938, 558,
+ 910, 177,
+ 494, 607,
+ 954, 478,
+ 910, 519,
+ 42, 625,
+ 369, 702,
+ 483, 93,
+ 964, 12,
+ 676, 105,
+ 155, 487,
+ 981, 521,
+ 761, 318,
+ 138, 162,
+ 764, 40,
+ 490, 135,
+ 630, 413,
+ 567, 613,
+ 938, 144,
+ 712, 523,
+ 258, 686,
+ 532, 418,
+ 322, 253,
+ 332, 734,
+ 203, 500,
+ 574, 38,
+ 542, 155,
+ 91, 652,
+ 27, 726,
+ 327, 307,
+ 135, 95,
+ 413, 463,
+ 132, 730,
+ 180, 570,
+ 482, 576,
+ 302, 11,
+ 463, 527,
+ 66, 501,
+ 345, 443,
+ 229, 200,
+ 932, 619,
+ 145, 485,
+ 883, 556,
+ 515, 101,
+ 39, 625,
+ 117, 392,
+ 873, 29,
+ 692, 357,
+ 169, 47,
+ 32, 181,
+ 112, 303,
+ 42, 694,
+ 935, 607,
+ 188, 440,
+ 903, 725,
+ 67, 238,
+ 696, 480,
+ 632, 621,
+ 713, 251,
+ 167, 573,
+ 359, 66,
+ 729, 660,
+ 41, 131,
+ 420, 255,
+ 44, 84,
+ 438, 53,
+ 816, 649,
+ 131, 144,
+ 437, 728,
+ 773, 98,
+ 927, 620,
+ 392, 105,
+ 52, 69,
+ 886, 126,
+ 362, 490,
+ 604, 296,
+ 374, 47,
+ 428, 539,
+ 768, 145,
+ 862, 21,
+ 902, 177,
+ 128, 238,
+ 848, 624,
+ 345, 179,
+ 535, 203,
+ 34, 470,
+ 520, 31,
+ 757, 741,
+ 801, 257,
+ 335, 263,
+ 442, 434,
+ 617, 132,
+ 864, 532,
+ 170, 641,
+ 19, 481,
+ 162, 193,
+ 342, 4,
+ 438, 597,
+ 675, 408,
+ 564, 10,
+ 608, 741,
+ 224, 440,
+ 835, 594,
+ 329, 267,
+ 960, 167,
+ 211, 115,
+ 495, 195,
+ 555, 54,
+ 378, 345,
+ 778, 540,
+ 231, 18,
+ 257, 307,
+ 8, 353,
+ 852, 692,
+ 231, 743,
+ 5, 251,
+ 789, 73,
+ 442, 285,
+ 832, 533,
+ 355, 18,
+ 693, 315,
+ 858, 431,
+ 940, 660,
+ 458, 12,
+ 68, 240,
+ 592, 457,
+ 512, 108,
+ 876, 553,
+ 373, 621,
+ 90, 48,
+ 505, 700,
+ 148, 427,
+ 59, 126,
+ 69, 679,
+ 447, 79,
+ 665, 376,
+ 409, 545,
+ 172, 288,
+ 267, 231,
+ 177, 361,
+ 629, 44,
+ 196, 209,
+ 707, 245,
+ 425, 528,
+ 159, 329,
+ 629, 693,
+ 356, 614,
+ 640, 536,
+ 738, 728,
+ 246, 31,
+ 247, 33,
+ 705, 626,
+ 934, 353,
+ 512, 197,
+ 98, 599,
+ 142, 604,
+ 879, 374,
+ 914, 309,
+ 200, 482,
+ 399, 460,
+ 437, 444,
+ 951, 414,
+ 903, 103,
+ 1, 459,
+ 541, 585,
+ 821, 715,
+ 609, 217,
+ 826, 282,
+ 609, 465,
+ 441, 149,
+ 443, 693,
+ 671, 61,
+ 572, 90,
+ 999, 748,
+ 694, 280,
+ 401, 693,
+ 244, 498,
+ 481, 26,
+ 110, 671,
+ 892, 686,
+ 307, 223,
+ 659, 446,
+ 984, 461,
+ 154, 623,
+ 815, 69,
+ 887, 12,
+ 863, 674,
+ 850, 489,
+ 328, 409,
+ 237, 653,
+ 176, 277,
+ 759, 229,
+ 616, 164,
+ 872, 485,
+ 473, 175,
+ 833, 73,
+ 205, 176,
+ 596, 471,
+ 982, 132,
+ 799, 116,
+ 360, 716,
+ 130, 204,
+ 809, 724,
+ 92, 437,
+ 405, 674,
+ 84, 135,
+ 50, 225,
+ 190, 6,
+ 127, 84,
+ 730, 179,
+ 901, 246,
+ 874, 177,
+ 378, 406,
+ 515, 310,
+ 388, 255,
+ 402, 342,
+ 382, 493,
+ 881, 429,
+ 428, 193,
+ 865, 129,
+ 579, 545,
+ 730, 302,
+ 117, 572,
+ 533, 541,
+ 597, 317,
+ 933, 745,
+ 547, 547,
+ 27, 647,
+ 998, 243,
+ 850, 458,
+ 441, 395,
+ 779, 188,
+ 462, 635,
+ 678, 275,
+ 137, 302,
+ 931, 504,
+ 419, 426,
+ 41, 746,
+ 619, 584,
+ 931, 256,
+ 811, 654,
+ 665, 441,
+ 893, 336,
+ 244, 610,
+ 697, 307,
+ 5, 715,
+ 605, 4,
+ 498, 448,
+ 300, 346,
+ 495, 439,
+ 869, 624,
+ 778, 411,
+ 613, 550,
+ 566, 581,
+ 986, 591,
+ 614, 118,
+ 476, 212,
+ 153, 582,
+ 58, 59,
+ 664, 392,
+ 446, 230,
+ 17, 220,
+ 267, 27,
+ 804, 250,
+ 891, 607,
+ 964, 718,
+ 591, 233,
+ 918, 37,
+ 225, 272,
+ 412, 708,
+ 579, 140,
+ 596, 700,
+ 134, 736,
+ 153, 615,
+ 677, 303,
+ 217, 580,
+ 847, 397,
+ 409, 13,
+ 148, 603,
+ 419, 254,
+ 297, 538,
+ 997, 413,
+ 889, 126,
+ 883, 527,
+ 422, 647,
+ 235, 422,
+ 26, 285,
+ 361, 68,
+ 45, 256,
+ 355, 746,
+ 944, 98,
+ 518, 357,
+ 401, 697,
+ 515, 607,
+ 881, 572,
+ 464, 55,
+ 470, 150,
+ 208, 133,
+ 354, 683,
+ 433, 133,
+ 752, 37,
+ 82, 28,
+ 465, 452,
+ 181, 389,
+ 710, 693,
+ 529, 728,
+ 547, 4,
+ 472, 391,
+ 152, 490,
+ 130, 340,
+ 982, 99,
+ 60, 50,
+ 96, 614,
+ 629, 587,
+ 77, 728,
+ 882, 472,
+ 929, 298,
+ 488, 514,
+ 281, 507,
+ 495, 593,
+ 218, 559,
+ 454, 306,
+ 922, 113,
+ 130, 286,
+ 541, 708,
+ 323, 73,
+ 947, 642,
+ 26, 88,
+ 829, 103,
+ 569, 358,
+ 306, 42,
+ 936, 678,
+ 722, 490,
+ 392, 730,
+ 711, 369,
+ 326, 86,
+ 972, 205,
+ 187, 161,
+ 760, 708,
+ 501, 496,
+ 347, 96,
+ 681, 293,
+ 26, 375,
+ 528, 167,
+ 1, 334,
+ 505, 60,
+ 822, 180,
+ 9, 168,
+ 84, 619,
+ 714, 183,
+ 63, 320,
+ 706, 538,
+ 193, 555,
+ 956, 386,
+ 430, 17,
+ 507, 514,
+ 138, 504,
+ 39, 323,
+ 854, 316,
+ 88, 42,
+ 103, 363,
+ 674, 68,
+ 832, 582,
+ 61, 241,
+ 377, 376,
+ 449, 350,
+ 104, 280,
+ 21, 336,
+ 893, 581,
+ 249, 548,
+ 315, 372,
+ 50, 436,
+ 282, 220,
+ 126, 669,
+ 451, 488,
+ 809, 212,
+ 273, 289,
+ 421, 699,
+ 867, 333,
+ 29, 80,
+ 196, 178,
+ 824, 672,
+ 27, 429,
+ 805, 315,
+ 525, 214,
+ 658, 67,
+ 822, 605,
+ 191, 478,
+ 832, 352,
+ 580, 81,
+ 462, 664,
+ 464, 349,
+ 196, 29,
+ 615, 423,
+ 108, 556,
+ 183, 261,
+ 480, 482,
+ 621, 570,
+ 286, 369,
+ 681, 382,
+ 768, 224,
+ 546, 183,
+ 443, 607,
+ 103, 172,
+ 791, 424,
+ 827, 731,
+ 965, 712,
+ 551, 69,
+ 740, 423,
+ 745, 341,
+ 155, 746,
+ 889, 602,
+ 411, 159,
+ 294, 467,
+ 248, 599,
+ 18, 360,
+ 734, 512,
+ 421, 519,
+ 367, 174,
+ 785, 545,
+ 706, 23,
+ 239, 278,
+ 581, 65,
+ 232, 609,
+ 752, 603,
+ 294, 585,
+ 224, 217,
+ 848, 558,
+ 332, 425,
+ 699, 68,
+ 53, 647,
+ 629, 652,
+ 87, 649,
+ 41, 718,
+ 227, 563,
+ 400, 302,
+ 253, 380,
+ 184, 42,
+ 366, 539,
+ 474, 691,
+ 170, 538,
+ 869, 96,
+ 974, 565,
+ 916, 28,
+ 285, 617,
+ 274, 38,
+ 147, 12,
+ 782, 261,
+ 749, 41,
+ 78, 592,
+ 370, 83,
+ 405, 488,
+ 436, 151,
+ 443, 556,
+ 96, 383,
+ 843, 745,
+ 630, 214,
+ 126, 10,
+ 338, 363,
+ 546, 27,
+ 61, 17,
+ 507, 199,
+ 445, 730,
+ 797, 213,
+ 555, 148,
+ 790, 65,
+ 837, 180,
+ 434, 320,
+ 102, 681,
+ 149, 680,
+ 10, 130,
+ 839, 232,
+ 848, 683,
+ 899, 650,
+ 837, 190,
+ 843, 463,
+ 984, 457,
+ 651, 490,
+ 552, 139,
+ 980, 71,
+ 748, 393,
+ 290, 171,
+ 503, 698,
+ 574, 742,
+ 429, 312,
+ 627, 680,
+ 69, 412,
+ 154, 538,
+ 135, 3,
+ 537, 12,
+ 535, 34,
+ 153, 632,
+ 797, 227,
+ 398, 336,
+ 20, 463,
+ 804, 175,
+ 400, 369,
+ 501, 250,
+ 105, 480,
+ 151, 146,
+ 57, 686,
+ 830, 119,
+ 867, 380,
+ 128, 84,
+ 222, 667,
+ 450, 522,
+ 390, 466,
+ 716, 375,
+ 760, 624,
+ 559, 407,
+ 587, 18,
+ 989, 53,
+ 817, 102,
+ 153, 269,
+ 253, 164,
+ 563, 360,
+ 93, 385,
+ 197, 360,
+ 277, 7,
+ 887, 280,
+ 416, 658,
+ 760, 411,
+ 902, 690,
+ 465, 424,
+ 28, 105,
+ 399, 620,
+ 455, 520,
+ 637, 491,
+ 769, 0,
+ 300, 521,
+ 90, 392,
+ 894, 722,
+ 705, 573,
+ 344, 188,
+ 667, 111,
+ 470, 16,
+ 759, 154,
+ 840, 581,
+ 176, 663,
+ 93, 151,
+ 372, 130,
+ 345, 425,
+ 156, 581,
+ 33, 8,
+ 320, 395,
+ 629, 661,
+ 641, 17,
+ 695, 663,
+ 751, 197,
+ 507, 93,
+ 608, 519,
+ 77, 303,
+ 513, 605,
+ 98, 354,
+ 567, 401,
+ 184, 440,
+ 785, 748,
+ 52, 32,
+ 528, 452,
+ 82, 532,
+ 116, 147,
+ 779, 341,
+ 308, 275,
+ 763, 135,
+ 137, 375,
+ 14, 260,
+ 337, 378,
+ 492, 262,
+ 202, 119,
+ 561, 334,
+ 855, 683,
+ 876, 724,
+ 202, 544,
+ 571, 437,
+ 456, 436,
+ 67, 4,
+ 468, 592,
+ 922, 540,
+ 125, 539,
+ 615, 290,
+ 785, 76,
+ 402, 556,
+ 12, 696,
+ 460, 52,
+ 909, 92,
+ 894, 153,
+ 931, 373,
+ 360, 120,
+ 726, 626,
+ 318, 733,
+ 472, 424,
+ 146, 74,
+ 86, 564,
+ 742, 236,
+ 845, 400,
+ 832, 139,
+ 275, 437,
+ 929, 42,
+ 818, 123,
+ 439, 274,
+ 65, 590,
+ 512, 132,
+ 520, 443,
+ 444, 107,
+ 961, 313,
+ 130, 488,
+ 587, 191,
+ 287, 603,
+ 56, 208,
+ 936, 628,
+ 908, 445,
+ 773, 258,
+ 383, 283,
+ 425, 530,
+ 244, 133,
+ 216, 543,
+ 631, 595,
+ 785, 108,
+ 87, 192,
+ 640, 427,
+ 889, 688,
+ 152, 89,
+ 10, 209,
+ 122, 343,
+ 188, 5,
+ 896, 748,
+ 806, 22,
+ 535, 457,
+ 851, 307,
+ 261, 566,
+ 791, 590,
+ 947, 300,
+ 658, 394,
+ 418, 305,
+ 371, 632,
+ 470, 438,
+ 165, 410,
+ 538, 380,
+ 643, 408,
+ 318, 591,
+ 564, 311,
+ 327, 690,
+ 930, 8,
+ 93, 100,
+ 627, 196,
+ 582, 416,
+ 200, 492,
+ 943, 267,
+ 31, 355,
+ 67, 374,
+ 692, 57,
+ 229, 373,
+ 542, 371,
+ 801, 230,
+ 114, 420,
+ 769, 326,
+ 83, 448,
+ 846, 137,
+ 912, 77,
+ 126, 3,
+ 784, 420,
+ 660, 391,
+ 795, 188,
+ 530, 42,
+ 137, 106,
+ 663, 80,
+ 757, 340,
+ 694, 267,
+ 768, 612,
+ 926, 155,
+ 600, 25,
+ 292, 31,
+ 97, 225,
+ 60, 437,
+ 724, 563,
+ 698, 85,
+ 286, 196,
+ 66, 1,
+ 269, 25,
+ 467, 405,
+ 204, 171,
+ 653, 14,
+ 299, 360,
+ 521, 719,
+ 760, 602,
+ 329, 282,
+ 687, 530,
+ 110, 200,
+ 30, 300,
+ 6, 501,
+ 868, 281,
+ 281, 76,
+ 805, 363,
+ 876, 114,
+ 219, 549,
+ 65, 611,
+ 859, 23,
+ 66, 354,
+ 205, 169,
+ 434, 174,
+ 828, 668,
+ 814, 720,
+ 663, 34,
+ 875, 707,
+ 969, 561,
+ 932, 66,
+ 834, 548,
+ 961, 86,
+ 263, 148,
+ 145, 202,
+ 83, 146,
+ 947, 727,
+ 3, 138,
+ 927, 514,
+ 814, 742,
+ 80, 430,
+ 866, 184,
+ 593, 731,
+ 193, 219,
+ 496, 490,
+ 606, 530,
+ 314, 334,
+ 301, 327,
+ 50, 715,
+ 178, 57,
+ 936, 626,
+ 972, 617,
+ 33, 427,
+ 147, 435,
+ 83, 341,
+ 859, 244,
+ 337, 688,
+ 637, 124,
+ 874, 71,
+ 590, 474,
+ 332, 120,
+ 640, 290,
+ 816, 171,
+ 665, 431,
+ 79, 31,
+ 857, 110,
+ 103, 79,
+ 293, 397,
+ 866, 651,
+ 356, 73,
+ 438, 710,
+ 41, 233,
+ 782, 596,
+ 852, 407,
+ 590, 104,
+ 34, 116,
+ 756, 276,
+ 282, 181,
+ 871, 275,
+ 888, 712,
+ 872, 279,
+ 645, 324,
+ 730, 524,
+ 430, 302,
+ 601, 486,
+ 114, 529,
+ 359, 317,
+ 313, 426,
+ 33, 732,
+ 970, 211,
+ 657, 582,
+ 945, 501,
+ 450, 630,
+ 822, 697,
+ 702, 600,
+ 958, 289,
+ 732, 96,
+ 205, 662,
+ 695, 533,
+ 369, 433,
+ 83, 445,
+ 176, 315,
+ 239, 95,
+ 895, 682,
+ 628, 118,
+ 730, 741,
+ 779, 734,
+ 804, 314,
+ 465, 567,
+ 810, 106,
+ 81, 268,
+ 968, 518,
+ 22, 159,
+ 726, 504,
+ 38, 269,
+ 751, 649,
+ 954, 659,
+};
+std::array<int32_t, 2000> expCoords = {
+ 190, 464,
+ 437, 588,
+ 774, 203,
+ 276, 599,
+ 939, 646,
+ 356, 373,
+ 681, 533,
+ 369, 419,
+ 500, 7,
+ 765, 655,
+ 363, 460,
+ 75, 272,
+ 920, 484,
+ 397, 590,
+ 315, 424,
+ 861, 326,
+ 795, 107,
+ 701, 526,
+ 220, 688,
+ 442, 678,
+ 59, 134,
+ 50, 501,
+ 593, 398,
+ 44, 417,
+ 327, 375,
+ 111, 452,
+ 562, 3,
+ 614, 680,
+ 780, 734,
+ 941, 586,
+ 284, 467,
+ 476, 142,
+ 379, 36,
+ 451, 731,
+ 122, 85,
+ 735, 439,
+ 469, 76,
+ 231, 670,
+ 415, 400,
+ 8, 221,
+ 435, 458,
+ 906, 466,
+ 701, 111,
+ 741, 619,
+ 632, 327,
+ 151, 423,
+ 527, 709,
+ 479, 375,
+ 535, 612,
+ 59, 498,
+ 762, 529,
+ 791, 417,
+ 948, 113,
+ 31, 441,
+ 119, 705,
+ 323, 141,
+ 457, 687,
+ 869, 189,
+ 346, 132,
+ 890, 525,
+ 721, 670,
+ 775, 448,
+ 288, 108,
+ 334, 492,
+ 74, 38,
+ 322, 441,
+ 845, 215,
+ 171, 96,
+ 975, 137,
+ 316, 425,
+ 17, 665,
+ 961, 414,
+ 83, 245,
+ 723, 105,
+ 551, 201,
+ 958, 495,
+ 253, 77,
+ 770, 583,
+ 754, 679,
+ 657, 425,
+ 201, 521,
+ 934, 657,
+ 973, 605,
+ 544, 336,
+ 875, 717,
+ 592, 272,
+ 323, 650,
+ 215, 549,
+ 365, 600,
+ 777, 524,
+ 621, 369,
+ 832, 531,
+ 440, 19,
+ 362, 547,
+ 474, 255,
+ 637, 92,
+ 171, 549,
+ 126, 273,
+ 601, 74,
+ 792, 701,
+ 959, 649,
+ 624, 692,
+ 721, 535,
+ 42, 325,
+ 280, 247,
+ 86, 565,
+ 508, 494,
+ 629, 276,
+ 445, 309,
+ 479, 732,
+ 370, 5,
+ 905, 645,
+ 350, 471,
+ 355, 155,
+ 221, 311,
+ 73, 484,
+ 748, 692,
+ 374, 218,
+ 371, 618,
+ 891, 319,
+ 6, 29,
+ 141, 445,
+ 105, 218,
+ 60, 461,
+ 28, 633,
+ 306, 567,
+ 560, 25,
+ 564, 493,
+ 184, 595,
+ 611, 415,
+ 628, 513,
+ 240, 587,
+ 847, 541,
+ 690, 353,
+ 848, 495,
+ 331, 386,
+ 391, 19,
+ 575, 635,
+ 936, 507,
+ 76, 303,
+ 42, 126,
+ 563, 126,
+ 565, 384,
+ 858, 536,
+ 892, 209,
+ 255, 522,
+ 884, 724,
+ 639, 245,
+ 604, 614,
+ 624, 86,
+ 287, 734,
+ 430, 429,
+ 525, 145,
+ 164, 372,
+ 974, 295,
+ 710, 130,
+ 70, 114,
+ 159, 208,
+ 535, 578,
+ 871, 475,
+ 844, 446,
+ 691, 401,
+ 876, 43,
+ 777, 108,
+ 59, 41,
+ 52, 382,
+ 404, 744,
+ 107, 241,
+ 980, 300,
+ 874, 424,
+ 935, 654,
+ 771, 24,
+ 948, 387,
+ 209, 652,
+ 222, 99,
+ 718, 722,
+ 534, 331,
+ 25, 449,
+ 943, 711,
+ 916, 140,
+ 621, 307,
+ 360, 23,
+ 859, 501,
+ 92, 658,
+ 777, 236,
+ 812, 379,
+ 22, 321,
+ 444, 175,
+ 822, 554,
+ 585, 368,
+ 486, 197,
+ 604, 564,
+ 268, 389,
+ 100, 531,
+ 875, 423,
+ 975, 137,
+ 14, 338,
+ 915, 626,
+ 472, 673,
+ 223, 224,
+ 711, 541,
+ 19, 210,
+ 578, 694,
+ 336, 85,
+ 515, 523,
+ 298, 643,
+ 892, 570,
+ 263, 698,
+ 923, 552,
+ 898, 178,
+ 493, 606,
+ 940, 474,
+ 898, 515,
+ 47, 618,
+ 369, 698,
+ 481, 89,
+ 945, 18,
+ 673, 103,
+ 155, 484,
+ 964, 516,
+ 757, 317,
+ 136, 158,
+ 757, 41,
+ 488, 131,
+ 629, 412,
+ 566, 611,
+ 924, 146,
+ 709, 521,
+ 259, 682,
+ 531, 417,
+ 320, 250,
+ 333, 729,
+ 202, 498,
+ 571, 35,
+ 540, 152,
+ 95, 645,
+ 36, 715,
+ 325, 304,
+ 134, 91,
+ 412, 462,
+ 137, 722,
+ 181, 567,
+ 481, 575,
+ 300, 7,
+ 462, 526,
+ 68, 497,
+ 344, 442,
+ 227, 196,
+ 917, 611,
+ 145, 482,
+ 872, 551,
+ 513, 97,
+ 44, 618,
+ 116, 389,
+ 861, 32,
+ 690, 356,
+ 168, 43,
+ 33, 177,
+ 111, 299,
+ 49, 685,
+ 920, 600,
+ 187, 438,
+ 887, 713,
+ 67, 234,
+ 694, 479,
+ 630, 619,
+ 710, 250,
+ 168, 570,
+ 356, 62,
+ 724, 655,
+ 42, 127,
+ 418, 252,
+ 45, 81,
+ 436, 49,
+ 807, 643,
+ 130, 140,
+ 437, 723,
+ 767, 98,
+ 912, 612,
+ 390, 101,
+ 53, 66,
+ 875, 128,
+ 361, 489,
+ 603, 294,
+ 371, 43,
+ 427, 538,
+ 763, 144,
+ 850, 24,
+ 891, 178,
+ 126, 234,
+ 838, 618,
+ 343, 175,
+ 534, 200,
+ 36, 466,
+ 517, 28,
+ 749, 732,
+ 796, 256,
+ 333, 260,
+ 441, 433,
+ 615, 129,
+ 855, 528,
+ 172, 636,
+ 22, 476,
+ 160, 189,
+ 339, 0,
+ 438, 596,
+ 673, 407,
+ 561, 8,
+ 605, 735,
+ 223, 438,
+ 826, 589,
+ 327, 264,
+ 945, 169,
+ 209, 111,
+ 494, 192,
+ 552, 51,
+ 377, 343,
+ 773, 537,
+ 229, 14,
+ 255, 304,
+ 10, 349,
+ 840, 683,
+ 234, 736,
+ 7, 247,
+ 782, 73,
+ 441, 282,
+ 824, 530,
+ 352, 14,
+ 691, 314,
+ 850, 429,
+ 923, 650,
+ 455, 8,
+ 68, 236,
+ 591, 456,
+ 510, 104,
+ 866, 549,
+ 373, 619,
+ 90, 45,
+ 504, 696,
+ 147, 424,
+ 59, 122,
+ 75, 671,
+ 445, 75,
+ 664, 375,
+ 408, 544,
+ 170, 284,
+ 265, 227,
+ 175, 358,
+ 625, 42,
+ 194, 205,
+ 704, 244,
+ 424, 527,
+ 157, 326,
+ 626, 689,
+ 356, 612,
+ 638, 535,
+ 731, 720,
+ 244, 27,
+ 245, 29,
+ 701, 623,
+ 922, 352,
+ 511, 194,
+ 101, 594,
+ 144, 600,
+ 870, 373,
+ 903, 308,
+ 199, 480,
+ 398, 459,
+ 436, 443,
+ 938, 412,
+ 891, 105,
+ 4, 454,
+ 540, 584,
+ 810, 706,
+ 608, 215,
+ 820, 281,
+ 608, 464,
+ 439, 145,
+ 443, 690,
+ 667, 60,
+ 570, 87,
+ 974, 731,
+ 692, 279,
+ 401, 690,
+ 243, 496,
+ 478, 22,
+ 114, 664,
+ 878, 676,
+ 305, 219,
+ 658, 445,
+ 967, 457,
+ 156, 619,
+ 807, 70,
+ 873, 16,
+ 851, 666,
+ 842, 486,
+ 327, 407,
+ 238, 649,
+ 174, 273,
+ 755, 228,
+ 614, 161,
+ 863, 482,
+ 471, 171,
+ 824, 74,
+ 203, 172,
+ 595, 470,
+ 964, 135,
+ 792, 116,
+ 361, 712,
+ 128, 200,
+ 799, 715,
+ 92, 434,
+ 405, 671,
+ 84, 131,
+ 50, 221,
+ 189, 3,
+ 126, 80,
+ 726, 178,
+ 891, 246,
+ 865, 178,
+ 377, 405,
+ 514, 308,
+ 386, 252,
+ 401, 340,
+ 381, 492,
+ 872, 427,
+ 426, 189,
+ 855, 130,
+ 578, 544,
+ 727, 301,
+ 119, 568,
+ 532, 540,
+ 596, 315,
+ 914, 731,
+ 546, 546,
+ 33, 639,
+ 981, 244,
+ 842, 456,
+ 440, 394,
+ 774, 187,
+ 462, 633,
+ 676, 273,
+ 135, 298,
+ 918, 500,
+ 418, 425,
+ 50, 734,
+ 617, 582,
+ 919, 256,
+ 802, 648,
+ 664, 440,
+ 884, 335,
+ 244, 607,
+ 695, 306,
+ 14, 704,
+ 601, 2,
+ 497, 447,
+ 298, 344,
+ 494, 438,
+ 858, 618,
+ 774, 410,
+ 612, 549,
+ 565, 580,
+ 967, 583,
+ 612, 115,
+ 475, 209,
+ 154, 578,
+ 59, 56,
+ 663, 391,
+ 444, 227,
+ 18, 216,
+ 265, 23,
+ 799, 249,
+ 879, 601,
+ 943, 704,
+ 590, 231,
+ 903, 41,
+ 223, 268,
+ 412, 704,
+ 577, 137,
+ 594, 696,
+ 139, 727,
+ 155, 611,
+ 675, 302,
+ 217, 577,
+ 840, 396,
+ 406, 9,
+ 150, 599,
+ 417, 251,
+ 296, 537,
+ 980, 410,
+ 878, 128,
+ 873, 523,
+ 422, 645,
+ 234, 420,
+ 27, 281,
+ 358, 64,
+ 45, 252,
+ 356, 740,
+ 929, 101,
+ 517, 356,
+ 401, 694,
+ 514, 606,
+ 870, 567,
+ 462, 51,
+ 468, 146,
+ 206, 129,
+ 354, 680,
+ 431, 129,
+ 745, 37,
+ 83, 25,
+ 464, 451,
+ 180, 386,
+ 705, 687,
+ 528, 723,
+ 544, 1,
+ 471, 390,
+ 152, 487,
+ 129, 337,
+ 964, 103,
+ 61, 47,
+ 99, 609,
+ 627, 585,
+ 84, 718,
+ 873, 469,
+ 917, 298,
+ 488, 513,
+ 280, 506,
+ 494, 592,
+ 218, 557,
+ 453, 304,
+ 908, 115,
+ 129, 282,
+ 540, 704,
+ 320, 69,
+ 930, 633,
+ 28, 85,
+ 821, 104,
+ 568, 357,
+ 304, 38,
+ 919, 667,
+ 719, 489,
+ 392, 725,
+ 709, 368,
+ 323, 81,
+ 956, 206,
+ 185, 157,
+ 753, 701,
+ 500, 495,
+ 345, 92,
+ 679, 292,
+ 27, 371,
+ 526, 164,
+ 3, 330,
+ 503, 56,
+ 815, 180,
+ 11, 164,
+ 88, 613,
+ 711, 182,
+ 63, 316,
+ 703, 536,
+ 193, 552,
+ 942, 384,
+ 427, 13,
+ 506, 513,
+ 138, 501,
+ 40, 319,
+ 847, 315,
+ 88, 39,
+ 102, 360,
+ 670, 66,
+ 824, 578,
+ 61, 237,
+ 376, 374,
+ 448, 348,
+ 103, 276,
+ 22, 332,
+ 881, 576,
+ 249, 546,
+ 313, 370,
+ 51, 432,
+ 280, 216,
+ 130, 663,
+ 450, 487,
+ 803, 211,
+ 271, 286,
+ 421, 696,
+ 859, 332,
+ 31, 77,
+ 194, 174,
+ 814, 665,
+ 29, 425,
+ 800, 314,
+ 524, 211,
+ 654, 65,
+ 814, 600,
+ 190, 476,
+ 826, 351,
+ 577, 78,
+ 462, 662,
+ 463, 347,
+ 194, 25,
+ 614, 422,
+ 110, 552,
+ 181, 257,
+ 479, 481,
+ 619, 569,
+ 284, 367,
+ 679, 381,
+ 764, 223,
+ 545, 180,
+ 443, 606,
+ 102, 168,
+ 786, 423,
+ 816, 721,
+ 944, 699,
+ 548, 66,
+ 737, 422,
+ 742, 340,
+ 160, 737,
+ 877, 596,
+ 409, 155,
+ 293, 466,
+ 248, 596,
+ 20, 356,
+ 731, 510,
+ 420, 518,
+ 365, 170,
+ 779, 542,
+ 700, 23,
+ 237, 275,
+ 578, 62,
+ 233, 606,
+ 747, 599,
+ 294, 583,
+ 222, 213,
+ 839, 554,
+ 331, 424,
+ 694, 67,
+ 58, 640,
+ 627, 649,
+ 91, 642,
+ 49, 708,
+ 227, 561,
+ 398, 299,
+ 251, 378,
+ 182, 38,
+ 365, 538,
+ 473, 688,
+ 170, 535,
+ 858, 98,
+ 956, 558,
+ 901, 33,
+ 285, 615,
+ 272, 34,
+ 146, 9,
+ 778, 260,
+ 743, 41,
+ 81, 587,
+ 368, 79,
+ 404, 487,
+ 434, 147,
+ 443, 555,
+ 96, 380,
+ 830, 734,
+ 628, 212,
+ 126, 7,
+ 336, 361,
+ 543, 24,
+ 62, 15,
+ 506, 196,
+ 445, 725,
+ 792, 212,
+ 553, 145,
+ 783, 66,
+ 829, 180,
+ 433, 318,
+ 107, 674,
+ 152, 674,
+ 12, 127,
+ 832, 232,
+ 837, 675,
+ 885, 642,
+ 830, 190,
+ 836, 461,
+ 967, 453,
+ 650, 489,
+ 550, 136,
+ 961, 76,
+ 745, 392,
+ 288, 167,
+ 502, 694,
+ 572, 736,
+ 428, 310,
+ 624, 676,
+ 70, 408,
+ 155, 535,
+ 135, 0,
+ 534, 9,
+ 532, 31,
+ 155, 627,
+ 792, 226,
+ 397, 334,
+ 23, 458,
+ 798, 175,
+ 399, 367,
+ 500, 247,
+ 106, 477,
+ 149, 142,
+ 63, 677,
+ 822, 120,
+ 859, 379,
+ 127, 80,
+ 224, 663,
+ 449, 521,
+ 389, 465,
+ 714, 374,
+ 754, 620,
+ 558, 406,
+ 584, 16,
+ 969, 59,
+ 809, 103,
+ 151, 265,
+ 251, 160,
+ 562, 359,
+ 93, 382,
+ 195, 357,
+ 275, 3,
+ 878, 280,
+ 416, 656,
+ 756, 410,
+ 887, 680,
+ 464, 423,
+ 30, 102,
+ 399, 618,
+ 454, 519,
+ 636, 490,
+ 761, 2,
+ 299, 520,
+ 90, 388,
+ 878, 710,
+ 702, 571,
+ 342, 184,
+ 664, 109,
+ 467, 12,
+ 754, 153,
+ 831, 577,
+ 178, 658,
+ 92, 147,
+ 370, 126,
+ 344, 424,
+ 157, 577,
+ 36, 7,
+ 318, 393,
+ 626, 658,
+ 637, 16,
+ 691, 659,
+ 747, 196,
+ 505, 89,
+ 607, 518,
+ 77, 299,
+ 512, 604,
+ 97, 350,
+ 566, 400,
+ 183, 438,
+ 775, 738,
+ 54, 30,
+ 527, 451,
+ 84, 528,
+ 115, 143,
+ 775, 340,
+ 306, 272,
+ 758, 134,
+ 136, 372,
+ 15, 256,
+ 335, 376,
+ 491, 259,
+ 200, 115,
+ 560, 332,
+ 843, 675,
+ 862, 713,
+ 202, 541,
+ 570, 436,
+ 455, 435,
+ 68, 2,
+ 468, 591,
+ 909, 535,
+ 126, 535,
+ 614, 288,
+ 778, 76,
+ 402, 555,
+ 20, 686,
+ 458, 48,
+ 896, 95,
+ 883, 154,
+ 919, 372,
+ 358, 116,
+ 721, 622,
+ 319, 728,
+ 471, 423,
+ 145, 70,
+ 88, 559,
+ 739, 235,
+ 838, 399,
+ 824, 139,
+ 274, 435,
+ 913, 46,
+ 810, 123,
+ 438, 271,
+ 69, 584,
+ 510, 128,
+ 519, 442,
+ 442, 103,
+ 947, 312,
+ 130, 485,
+ 585, 188,
+ 287, 601,
+ 56, 204,
+ 920, 620,
+ 897, 443,
+ 769, 257,
+ 381, 280,
+ 424, 529,
+ 242, 129,
+ 216, 541,
+ 629, 593,
+ 779, 108,
+ 86, 188,
+ 639, 426,
+ 875, 678,
+ 151, 85,
+ 12, 205,
+ 121, 340,
+ 187, 2,
+ 879, 735,
+ 797, 24,
+ 534, 456,
+ 844, 306,
+ 261, 564,
+ 784, 586,
+ 934, 300,
+ 657, 393,
+ 417, 303,
+ 371, 630,
+ 469, 437,
+ 164, 407,
+ 537, 379,
+ 642, 407,
+ 318, 589,
+ 563, 309,
+ 328, 686,
+ 913, 14,
+ 93, 96,
+ 625, 194,
+ 581, 415,
+ 199, 490,
+ 930, 267,
+ 32, 351,
+ 67, 370,
+ 687, 56,
+ 227, 370,
+ 541, 370,
+ 796, 229,
+ 114, 417,
+ 765, 325,
+ 84, 444,
+ 837, 138,
+ 898, 80,
+ 126, 0,
+ 780, 419,
+ 659, 390,
+ 789, 187,
+ 527, 39,
+ 136, 102,
+ 659, 78,
+ 754, 339,
+ 692, 266,
+ 762, 608,
+ 913, 157,
+ 597, 23,
+ 290, 27,
+ 96, 221,
+ 61, 433,
+ 720, 561,
+ 694, 84,
+ 284, 192,
+ 68, 0,
+ 267, 21,
+ 466, 404,
+ 202, 167,
+ 649, 13,
+ 297, 358,
+ 520, 715,
+ 755, 598,
+ 327, 279,
+ 685, 529,
+ 109, 196,
+ 31, 296,
+ 10, 496,
+ 860, 280,
+ 279, 72,
+ 800, 362,
+ 865, 116,
+ 219, 547,
+ 69, 605,
+ 847, 26,
+ 66, 350,
+ 203, 165,
+ 432, 170,
+ 818, 661,
+ 804, 711,
+ 659, 33,
+ 861, 697,
+ 952, 555,
+ 917, 70,
+ 826, 544,
+ 944, 90,
+ 260, 144,
+ 143, 198,
+ 83, 142,
+ 927, 713,
+ 5, 135,
+ 914, 510,
+ 803, 732,
+ 81, 426,
+ 857, 184,
+ 590, 726,
+ 191, 215,
+ 495, 489,
+ 605, 529,
+ 312, 332,
+ 299, 324,
+ 57, 705,
+ 176, 53,
+ 920, 618,
+ 953, 608,
+ 35, 423,
+ 146, 432,
+ 83, 337,
+ 851, 244,
+ 338, 684,
+ 634, 122,
+ 863, 73,
+ 589, 473,
+ 330, 116,
+ 639, 288,
+ 809, 171,
+ 664, 430,
+ 80, 28,
+ 847, 111,
+ 103, 75,
+ 291, 395,
+ 854, 644,
+ 353, 69,
+ 438, 706,
+ 41, 229,
+ 776, 592,
+ 845, 405,
+ 588, 101,
+ 35, 113,
+ 752, 275,
+ 280, 177,
+ 863, 275,
+ 873, 701,
+ 864, 279,
+ 644, 323,
+ 727, 522,
+ 429, 300,
+ 600, 485,
+ 115, 525,
+ 357, 315,
+ 312, 424,
+ 42, 721,
+ 955, 212,
+ 655, 580,
+ 931, 497,
+ 450, 628,
+ 812, 689,
+ 698, 597,
+ 944, 289,
+ 727, 95,
+ 207, 657,
+ 692, 531,
+ 368, 432,
+ 84, 441,
+ 174, 312,
+ 237, 91,
+ 881, 672,
+ 625, 116,
+ 723, 733,
+ 770, 725,
+ 799, 313,
+ 465, 566,
+ 803, 106,
+ 80, 264,
+ 952, 513,
+ 23, 155,
+ 723, 502,
+ 39, 265,
+ 745, 644,
+ 936, 649,
+};
+} // namespace openCvData