{

public:

class Solution {

public:

};

TEST_METHOD(test0)

{

Solution s;

}

{

public:

class Solution {

public:

vector<vector<int>> csum3(int k, int n, int last) {

if (k == 1)

if (n < last && n > 0)

return{ { n, last } };

else

return{};

vector<vector<int>> result;

for (int i = last - 1; i > 0; i--)

{

for (auto && v : csum3(k - 1, n - i, i))

{

v.push_back(last);

result.emplace_back(v);

}

}

return std::move(result);

}

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> result;

for (int i = std::min(n, 9); i > 0; i--)

{

for (auto & v : csum3(k - 1, n - i, i))

{

result.emplace_back(v);

}

}

return result;

}

};

TEST_METHOD(Test_3_9)

{

//combination sum iii

Solution s;

auto & v = s.combinationSum3(3, 9);

Assert::IsFalse(v.empty());

}

TEST_METHOD(char_test)

{

char * s = nullptr;

s = "asdfadfds";

char * ss = "abcedfg";

char sss[7] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };

Assert::IsFalse(false);

//char * ss = NULL;

}

{

public:

class Solution {

public:

using Dict = map<int, list<int>>;

// because of the range is 0-9

//create a list, with (value, #remain_elem) order by value desc

auto dict(const vector<int>& data) -> Dict

{

map<int, list<int>> dict;

size_t last = data.size() - 1;

for (size_t i = 0; i < data.size(); i++)

{

dict[data[i]].emplace_back(last - i);

}

return dict;

}

auto find(Dict& dict, int key, int barrier) -> Dict::iterator

{

auto it = dict.find(key);

if (it == dict.end())

return dict.end();

while (!it->second.empty() && it->second.front() >= barrier)

{

it->second.pop_front();

}

if (it->second.empty()){

dict.erase(key);

return dict.end();

}

return it;

}

auto getRemains(Dict& dict, Dict::iterator & iter) -> int

{

int result = iter->second.front();

iter->second.pop_front();

if (iter->second.empty())

dict.erase(iter);

return result;

}

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {

vector<int> result;

auto dict1 = dict(nums1);

auto dict2 = dict(nums2);

size_t remains1 = nums1.size();

size_t remains2 = nums2.size();

for (size_t i = 9, j = k; i > -1 && j > 0;)

{

auto it1 = find(dict1, i, remains1);

auto it2 = find(dict2, i, remains2);

if (it1 == dict1.end()) {

if (it2 == dict2.end()) {

i--;

continue;

}

else {

int check = remains1 + it2->second.front() - j + 1;

if (check < 0){

i--;

continue;

}

else {

remains2 = getRemains(dict2, it2);

result.emplace_back(i);

j--;

i = 9;

continue;

}

}

}

else {

if (it2 == dict2.end()) {

int check = remains2 + it1->second.front() - j + 1;

if (check < 0){

i--;

continue;

}

else {

remains1 = getRemains(dict1, it1);

result.emplace_back(i);

j--;

i = 9;

continue;

}

}

else {

if (it1->second.front() >= it2->second.front()){

int check = remains2 + it1->second.front() - j + 1;

if (check < 0){

i--;

continue;

}

else {

remains1 = getRemains(dict1, it1);

result.emplace_back(i);

j--;

i = 9;

continue;

}

}

else {

int check = remains1 + it2->second.front() - j + 1;

if (check < 0){

i--;

continue;

}

else {

remains2 = getRemains(dict2, it2);

result.emplace_back(i);

j--;

i = 9;

continue;

}

}

}

}

}

return result;

}

};

TEST_METHOD(case1)

{

vector<int> nums1 = { 3, 4, 6, 5 };

vector<int> nums2 = { 9, 1, 2, 5, 8, 3 };

Solution s;

auto & result = s.maxNumber(nums1, nums2, 5);

Assert::IsTrue(!result.empty());

}

TEST_METHOD(case2)

{

vector<int> nums1 = { 6, 7 };

vector<int> nums2 = { 6, 0, 4 };

Solution s;

auto & result = s.maxNumber(nums1, nums2, 5);

Assert::IsTrue(!result.empty());

}

{

class Solution { //TODO DP solution.

public:

bool isPalindrome(string::const_iterator beg, string::const_iterator end) //beg or end

{

while (beg < end)

{

end--; // end pos = last + 1;

if (*beg == *end)

beg++;

else

return false;

}

return true;

}

vector<vector<string>> partition(string s)

{

vector<vector<string>> result;

vector<string> path;

dfs(result, path, s.begin(), s.end());

return result;

}

void dfs(vector<vector<string>>& result, vector<string>& path, string::const_iterator beg, string::const_iterator end)

{

if (beg == end)

return;

if (isPalindrome(beg, end))

{

path.push_back(string(beg, end));

result.push_back(path);

path.pop_back();

}

auto distance = end - beg;

for (decltype(distance) i = 1; i < distance; i++)

{

const auto next = beg + i;

if (isPalindrome(beg, next))

{

path.push_back(string(beg, next));

dfs(result, path, next, end);

path.pop_back();

}

}

}

};

TEST_METHOD(test_string_iterator)

{

string s = "abcdefg";

string::const_iterator & it = s.begin();

char c = *it;

Assert::AreEqual(c, 'a');

c = *(++it);

Assert::AreEqual(c, 'b');

string::const_iterator & end = s.end();

end--;

c= *end;

Assert::AreEqual(c, 'g');

}

TEST_METHOD(test_isPalindrome)

{

Solution s;

vector<string> test_case_positive =

{

"", "a", "aa", "abcba", "abccba"

};

for (const string& tc : test_case_positive)

{

Assert::IsTrue(s.isPalindrome(tc.begin(), tc.end()));

}

vector<string> test_case_negetive =

{

"ab", "abc"

};

for (const string& tc : test_case_negetive)

{

Assert::IsFalse(s.isPalindrome(tc.begin(), tc.end()));

}

}

TEST_METHOD(test_partition_0)

{

Solution s;

auto result = s.partition("");

Assert::IsTrue(result.empty());

result = s.partition("a");

Assert::IsTrue(result.size() == 1);

result = s.partition("abc");

Assert::IsTrue(result.size() == 1);

}

TEST_METHOD(test_partition_1)

{

Solution s;

auto result = s.partition("aab");

auto& v1 = result[0];

auto& v2 = result[1];

Assert::AreEqual(v1[0], string("a"));

Assert::AreEqual(v1[1], string("a"));

Assert::AreEqual(v1[2], string("b"));

Assert::AreEqual(v2[0], string("aa"));

Assert::AreEqual(v2[1], string("b"));

}

{

class Solution {

public:

bool isAnagram(string s, string t) {

int ss[26] = {};

int tt[26] = {};

for (char c : s)

{

ss[c - 'a']++;

}

for (char c : t)

{

tt[c - 'a']++;

}

for (int i = 0; i < 26; i++)

{

if (ss[i] != tt[i])

return false;

}

return true;

}

};

TEST_METHOD(test_0)

{

Solution ss;

string s = "anagram";

string t = "nagaram";

Assert::IsTrue(ss.isAnagram(s, t));

s = "rat";

t = "car";

Assert::IsFalse(ss.isAnagram(s, t));

}

{

class Solution { //TODO DP solution.

public:

bool isPalindrome(string::const_iterator beg, string::const_iterator end) //beg or end

{

while (beg < end)

{

end--; // end pos = last + 1;

if (*beg == *end)

beg++;

else

return false;

}

return true;

}

vector<vector<string>> partition(string s)

{

auto size = s.size();

vector<vector<bool>> isP = { {false} };

for (int i = 0; i < size; i++)

{

for (int j = 0; j < size; j++)

{

}

}

vector<vector<string>> result;

vector<string> path;

dfs(result, path, s.begin(), s.end());

return result;

}

void dfs(vector<vector<string>>& result, vector<string>& path, string::const_iterator beg, string::const_iterator end)

{

if (beg == end)

return;

if (isPalindrome(beg, end))

{

path.push_back(string(beg, end));

result.push_back(path);

path.pop_back();

}

auto distance = end - beg;

for (decltype(distance) i = 1; i < distance; i++)

{

const auto next = beg + i;

if (isPalindrome(beg, next))

{

path.push_back(string(beg, next));

dfs(result, path, next, end);

path.pop_back();

}

}

}

};

TEST_METHOD(test_string_iterator)

{

string s = "abcdefg";

string::const_iterator & it = s.begin();

char c = *it;

Assert::AreEqual(c, 'a');

c = *(++it);

Assert::AreEqual(c, 'b');

string::const_iterator & end = s.end();

end--;

c = *end;

Assert::AreEqual(c, 'g');

}

TEST_METHOD(test_isPalindrome)

{

Solution s;

vector<string> test_case_positive =

{

"", "a", "aa", "abcba", "abccba"

};

for (const string& tc : test_case_positive)

{

Assert::IsTrue(s.isPalindrome(tc.begin(), tc.end()));

}

vector<string> test_case_negetive =

{

"ab", "abc"

};

for (const string& tc : test_case_negetive)

{

Assert::IsFalse(s.isPalindrome(tc.begin(), tc.end()));

}

}

TEST_METHOD(test_partition_0)

{

Solution s;

auto result = s.partition("");

Assert::IsTrue(result.empty());

result = s.partition("a");

Assert::IsTrue(result.size() == 1);

result = s.partition("abc");

Assert::IsTrue(result.size() == 1);

}

TEST_METHOD(test_partition_1)

{

Solution s;

auto result = s.partition("aab");

auto& v1 = result[0];

auto& v2 = result[1];

Assert::AreEqual(v1[0], string("a"));

Assert::AreEqual(v1[1], string("a"));

Assert::AreEqual(v1[2], string("b"));

Assert::AreEqual(v2[0], string("aa"));

Assert::AreEqual(v2[1], string("b"));

}

// Forward declaration of isBadVersion API.

class Solution {

public:

bool isBadVersion(int version)

{

return version >= 1702766719;

}

int firstBadVersion(int n) {

if (n < 0)

return 0;

if (n == 1)

return 1;

int lo = 1, hi = n, dist, mid;

while ((dist = hi - lo) != 1)

{

mid = lo + dist / 2;

if (isBadVersion(mid))

{

hi = mid;

}

else

{

lo = mid;

}

}

return isBadVersion(lo) ? lo: hi;

}

};

TEST_METHOD(test_0)

{

Solution s;

auto result = s.firstBadVersion(2126753390);

Assert::AreEqual(1702766719, result);

}

class Solution {

public:

//token

static const char PLUS = '+';

static const char MINUS = '-';

static const char SUB_BEG = '(';

static const char SUB_END = ')';

int nextInt(string::const_iterator& beg, const string::const_iterator& end)

{

int result = 0;

char c;

for (; beg != end; beg++)

{

c = *beg;

if (c >= '0' && c <= '9')

result = c - '0' + result * 10;

else

break;

}

return result;

}

void compute(vector<char>& ops, vector<int>& nums)

{

int lastNum = 0;

while (!ops.empty())

{

char lastOp = ops.back();

ops.pop_back();

switch (lastOp)

{

case MINUS:

lastNum -= nums.back();

nums.pop_back();

break;

case PLUS:

lastNum += nums.back();

nums.pop_back();

break;

case SUB_BEG:

lastNum += nums.back();

nums.pop_back();

nums.emplace_back(lastNum);

return;

default:

throw runtime_error("stack error");

}

}

lastNum += nums.back();

nums.pop_back();

nums.emplace_back(lastNum);

}

int calculate(string s) {

string::const_iterator beg = s.begin();

const string::const_iterator & end = s.end();

char c;

vector<char> ops;

vector<int> nums;

while (beg != end)

{

switch (c = *(beg++))

{

case PLUS:

case MINUS:

case SUB_BEG:

ops.emplace_back(c);

case ' ':

break;

case SUB_END:

compute(ops, nums);

break;

default: // get next number

beg--;

nums.emplace_back(nextInt(beg, end));

break;

}

}

if (nums.empty())

return 0;

else if (ops.empty())

return nums.back();

else

{

compute(ops, nums);

return nums.back();

}

}

};

TEST_METHOD(test_0)

{

Solution s;

auto result = s.calculate("1 + 1");

Assert::AreEqual(2, result);

result = s.calculate(" 2-1 + 2 ");

Assert::AreEqual(3, result);

result = s.calculate("(1-(4-5-2)-3)+(6+8)");

Assert::AreEqual(15, result);

result = s.calculate("0");

Assert::AreEqual(0, result);

}

{

public:

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) { // O(n) s-O(1)

auto beg = nums.begin();

auto end = nums.end();

auto p = beg;

size_t min = nums.size() + 1;

int sum = 0;

while (p != end)

{

sum += *p;

while (sum >= s)

{

min = std::min<int>(min, p - beg + 1);

sum -= *(beg++);

}

p++;

}

return min > nums.size() ? 0 : min;

}

int minSubArrayLen_On2_sOn(int s, vector<int>& nums) { // t O(n^2) s O(n)

const size_t size = nums.size();

vector<int> last;

last.assign(nums.begin(), nums.end());

for (size_t i = 1; i < size; i++)

{

vector<int> next;

next.reserve(last.size() - 1);

for (size_t j = 0; j < last.size(); j++)

{

if (last[j] >= s)

return i;

size_t k = i + j;

if (k < size)

next.emplace_back(last[j] + nums[k]);

}

last = std::move(next);

}

return 0;

}

int minSubArrayLen_On2(int s, vector<int>& nums) { // O(n^2)

const size_t size = nums.size();

vector<vector<int>> rt;

rt.reserve(size);

rt.emplace_back(nums);

for (size_t i = 1; i < size; i++)

{

auto & v = rt[i - 1];

vector<int> next;

next.reserve(v.size() - 1);

for (size_t j = 0; j < v.size(); j++)

{

if (v[j] >= s)

return i;

size_t k = i + j;

if (k < size)

next.emplace_back(v[j] + rt[0][k]);

}

rt.emplace_back(next);

}

return 0;

}

};

TEST_METHOD(test0)

{

Solution s;

vector<int> case0 = { 2, 3, 1, 2, 4, 3 };

int target = 7;

int result = s.minSubArrayLen(target, case0);

Assert::AreEqual(2, result);

}

TEST_METHOD(test1)

{

Solution s;

vector<int> case0 = { 1,2,3,4,5};

int target = 11;

int result = s.minSubArrayLen(target, case0);

Assert::AreEqual(3, result);

}

TEST_METHOD(testn)

{

Solution s;

vector<int> case0 = { 39396, 75535, 17610, 81826, 10343, 69422, 14335, 9801, 19955, 99295, 38101, 24312, 20341, 69218, 65487, 38409, 89920, 17480, 92688, 71016, 91144, 51111, 88996, 24041, 7190, 78854, 94001, 80392, 50540, 48497, 3153, 43509, 74239, 48742, 14946, 5772, 53828, 15647, 92326, 93162, 53714, 24957, 31602, 1926, 26875, 35836, 60646, 69048, 98012, 92164, 26077, 14024, 77649, 67997, 78341, 18214, 57985, 44171, 52842, 55525, 70084, 74614, 30378, 77896, 4212, 99784, 64496, 46262, 46399, 8492, 6978, 30754, 84811, 36393, 45151, 6340, 13544, 98081, 86997, 95444, 45237, 20037, 14037, 53490, 38646, 17000, 74471, 44593, 82428, 74864, 19016, 54838, 58668, 11032, 84860, 99259, 76070, 30163, 49073, 71500, 28207, 64386, 70747, 48359, 13511, 82968, 98839, 15888, 90781, 2133, 28037, 46092, 31757, 44124, 36338, 44268, 97854, 93749, 36361, 2179, 77441, 85528, 16717, 97573, 26685, 84894, 43169, 59012, 33270, 86629, 11359, 28595, 47766, 21965, 65394, 87355, 57990, 57962, 13864, 37360, 96847, 52645, 93474, 88997, 88822, 40161, 32062, 12006, 1952, 54158, 90362, 40220, 34257, 84673, 93803, 9722, 68847, 78587, 58552, 66210, 17038, 64681, 51612, 38151, 45862, 7565, 34865, 22118, 3179, 81710, 32238, 494, 86367, 87808, 94954, 37642, 1944, 25980, 23970, 4818, 89584, 27863, 10048, 8073, 33515, 14971, 75233, 96927, 47280, 35223, 61500, 64730, 30107, 47455, 64536, 95560, 50286, 87337, 7105, 25961, 31925, 70002, 46739, 68103, 70275, 54251, 34629, 66383, 76483, 12288, 70671, 99958, 80034, 13642, 24341, 15929, 59181, 44814, 79352, 71087, 54428, 18788, 73285, 68203, 25968, 74869, 11750, 48436, 99493, 16714, 7501, 49344, 3942, 797, 19437, 66095, 33367, 88037, 16700, 22559, 34724, 7128, 83307, 46293, 57333, 94730, 28051, 55133, 52280, 16397, 61754, 41447, 51182, 54450, 4157, 62207, 30813, 90077, 49368, 36572, 87523, 89996, 43369, 14540, 6448, 51950, 28665, 87214, 33545, 85912, 18754, 70886, 16646, 71827, 68529, 99288, 3294, 42185, 52304, 71541, 25942, 22506, 8910, 73719, 83262, 12615, 63150, 96392, 46289, 79797, 56970, 22172, 54358, 11895, 80255, 51527, 59, 22591, 16126, 47403, 21702, 21654, 30731, 84466, 46744, 70066, 22379, 69028, 5242, 89976, 10067, 88510, 90661, 10597, 67939, 62942, 38747, 2934, 91174, 55875, 10476, 18975, 75385, 59127, 51002, 53840, 96733, 54994, 2310, 51944, 91857, 74269, 32636, 31301, 25461, 34167, 50288, 59316, 64029, 88498, 54665, 14288, 29800, 62385, 93371, 16246, 5820, 62258, 1951, 2920, 48093, 31781, 98049, 11136, 93114, 39263, 70104, 36356, 90273, 14790, 35511, 10473, 27269, 90261, 46748, 7875, 70785, 29114, 35197, 74539, 25170, 94676, 91668, 70436, 9289, 88109, 48743, 70069, 54481, 58092, 60815, 66278, 65467, 35089, 3283, 45671, 65769, 42535, 29309, 99118, 3658, 34335, 35693, 68280, 61192, 34210, 37485, 18878, 3593, 30740, 35511, 3814, 21030, 6306, 66511, 52145, 31918, 90336, 29722, 54525, 18282, 5266, 59838, 47867, 29745, 11037, 54417, 15356, 23216, 50610, 12648, 46034, 21330, 81758, 44067, 3453, 53784, 8866, 373, 21551, 80679, 97930, 37269, 96502, 11843, 52776, 70726, 73048, 53663, 426, 4340, 79144, 37234, 76898, 36327, 19869, 51710, 80170, 17197, 71294, 46640, 53032, 48778, 84951, 73728, 39584, 48968, 40581, 5286, 87553, 9234, 71765, 12396, 47211, 26513, 17436, 11543, 66703, 51042, 79709, 81518, 99022, 57674, 36347, 7789, 36730, 53905, 90066, 62513, 51427, 81243, 46684, 64972, 88637, 94193, 79082, 38750, 62313, 49728, 75999, 14842, 23500, 5328, 54499, 11474, 37112, 35025, 2619, 31509, 21142, 17947, 74544, 18328, 81018, 23468, 86927, 39252, 71442, 14607, 67312, 83062, 63658, 76471, 3479, 74504, 57442, 23262, 88930, 71104, 70179, 22690, 4753, 56989, 35209, 93038, 61268, 74124, 54177, 76383, 45454, 50030, 31690, 44104, 50299, 65776, 14730, 28733, 45098, 97606, 3496, 167, 67067, 3866, 5312, 62448, 38467, 15829, 46710, 76473, 49091, 69653, 44337, 29725, 56489, 42984, 28531, 60449, 4603, 53116, 333, 36661, 92545, 37433, 5503, 51206, 17112, 91929, 3841, 91577, 57429, 30216, 87156, 95187, 85566, 62591, 23717, 64111, 45833, 43552, 50266, 87417, 10200, 43891, 89379, 23747, 20494, 87495, 42853, 66348, 18389, 40551, 42566, 86900, 32310, 41427, 33121, 77754, 54335, 72621, 15805, 1257, 83941, 20628, 7539, 19207, 5371, 87955, 99785, 52194, 8441, 84835, 64762, 62773, 96928, 53926, 33461, 10852, 58832, 20487, 24325, 12030, 90420, 67142, 49419, 76549, 26707, 66633, 96190, 13931, 60538, 69777, 76489, 81238, 3703, 62924, 41317, 75040, 55449, 65463, 24450, 88403, 90391, 54673, 11272, 59515, 97298, 22477, 69252, 54854, 88438, 28705, 85722, 36527, 93378, 15057, 82883, 51119, 43150, 32686, 97169, 81534, 93366, 8354, 58910, 87190, 1669, 99024, 89131, 53932, 80643, 83565, 77430, 62852, 86602, 86351, 20248, 99484, 99610, 24232, 43297, 53858, 28368, 1072, 21948, 62543, 29218, 15430, 79178, 83460, 42288, 46567, 62948, 16125, 11399, 90473, 85725, 30819, 22185, 7424, 59822, 82822, 64693, 77648, 89251, 28039, 75026, 16992, 5185, 19576, 7815, 77467, 41194, 59217, 61657, 75907, 22034, 44046, 14137, 19932, 86280, 73362, 48552, 40770, 69424, 25464, 3628, 69254, 68662, 37617, 17664, 11856, 36391, 30724, 51221, 68026, 64866, 47181, 47606, 59794, 38866, 37667, 344, 38729, 41529, 48959, 52290, 88360, 82982, 39548, 34128, 61787, 78058, 553, 52390, 25312, 37114, 45128, 81242, 31407, 95570, 66045, 1190, 44659, 98532, 96384, 14237, 53423, 87793, 84117, 25039, 25067, 37402, 78281, 51124, 34422, 87766, 1796, 18376, 49658, 59386, 76993, 95644, 97003, 39833, 8602, 19411, 52690, 66169, 5142, 87400, 4654, 3146, 26949, 94882, 79870, 22139, 65039, 58974, 48105, 49020, 29646, 6802, 43360, 30271, 90687, 89959, 78844, 91073, 62027, 74762, 17600, 89525, 84271, 67172, 20501, 4186, 80485, 71569, 31326, 84056, 44332, 44517, 98716, 84751, 75775, 9412, 12075, 17561, 45622, 54833, 47814, 75903, 63242, 65429, 94759, 34778, 59002, 80836, 93122, 83916, 72358, 65067, 47318, 27829, 90193, 84500, 97998, 19806, 82578, 83386, 45038, 52692, 13883, 34346, 74410, 95084, 50406, 97094, 29220, 93059, 99723, 86132, 25943, 23498, 54728, 46123, 80876, 1330, 69911, 17618, 69436, 18403, 65319, 8291, 80287, 44823, 17529, 88146, 85915, 90747, 81703, 19569, 19785, 6405, 56584, 20351, 3167, 33104, 32453, 12010, 59747, 40481, 48485, 91354, 64922, 8521, 79849, 18178, 32933, 28741, 70883, 67936, 95581, 91960, 81392, 84728, 16815, 2531, 83247, 35302, 45370, 47649, 88078, 31649, 90216, 7494, 38954, 31020, 35492, 58777, 91197, 15435, 11981, 90859, 52557, 59098, 82554, 73359, 32049, 31012, 70914, 69312, 97840, 15859, 28448, 51918, 27260, 12484, 67347, 89859, 97449, 18455, 28188, 77258, 7916, 83616, 57840, 92155, 59310, 80682, 48304, 5410, 70241, 30873, 3269, 66928, 87186, 99735, 99438, 19026, 78671, 84083, 67100, 77968, 44121, 71496, 32698, 49522, 42487, 69067, 25426, 5562, 21977, 62143, 92767, 58263, 70599, 98185, 20574, 13616, 80737, 74722, 60726, 63051, 46437, 69650, 81427, 18118, 53498, 15706, 10543, 67537, 35528, 84448, 90964, 8074, 89762, 96395, 43791, 99016, 92732, 39802, 37964, 36289, 40905, 85218, 45738, 53927, 91875, 53134, 63155, 34843, 37716, 77409, 24775, 73943, 26202, 9397, 95458, 40220, 30288, 35975, 55766, 856, 70679, 53464, 76778, 21009, 7432, 21681, 11693, 40317, 10435, 99434, 10599, 42847, 12648, 92937, 79915, 54840, 25772, 28207, 51767, 90546, 28154, 12288, 8807, 96827, 28538, 72068, 23176, 73297, 45991, 29502, 60263, 4475, 35704, 90026, 21836, 9492, 4183, 59829, 88462, 35721, 60818, 32057, 86479, 28450, 391, 12973, 65889, 49126, 19419, 26198, 43881, 41564, 87360, 63944, 68431, 24226, 81341, 63489, 97077, 46507, 86514, 90891, 73979, 30870, 85766, 4191, 89867, 7577, 45925, 45994, 42787, 88993, 96906, 61074, 65599, 94285, 55077, 86260, 41469, 28174, 50074, 32224, 639, 47282, 43658, 79500, 49313, 95378, 41623, 71987, 4031, 93976, 73230, 30060, 88240, 90056, 30994, 35111, 84500, 87093, 91146, 26981, 36803, 47296, 30441, 83438, 77553, 2791, 82584, 39843, 34137, 90525, 55462, 49578, 71702, 93954, 81397, 56662, 19369, 75593, 13406, 92812, 68041, 89583, 99060, 8063, 12387, 62244, 24821, 27330, 95897, 20457, 14631, 70401, 23215, 80660, 12579, 12827, 66984, 87599, 66560, 77472, 53210, 71536, 94514, 38976, 35325, 79812, 14039, 34552, 93342, 65980, 8536, 35104, 74166, 81327, 65615, 55368, 29470, 67557, 99322, 55003, 86087, 64293, 81631, 14807, 36967, 78650, 40008, 97468, 50914, 52805, 46653, 94688, 47043, 12238, 82212, 3869, 49209, 98598, 36460, 70734, 87949, 49941, 94498, 3036, 63768, 69167, 54317, 68907, 18198, 52638, 92077, 4749, 33728, 73369, 50524, 78817, 77926, 65901, 7571, 9960, 70221, 97389, 1520, 79462, 18403, 54922, 6217, 10702, 34005, 37591, 59143, 35682, 74246, 35543, 76095, 87008, 96958, 76264, 48379, 1621, 39130, 33879, 27495, 26489, 79834, 351, 59611, 48304, 65433, 92219, 96589, 46057, 85685, 61323, 43461, 54776, 43506, 67396, 81696, 92327, 95204, 88453, 2868, 81493, 2734, 69102, 57011, 74452, 21967, 90113, 19412, 39499, 92931, 51009, 94632, 61818, 87840, 86932, 50210, 936, 12532, 17360, 13512, 77503, 28909, 17320, 93321, 93027, 68956, 2877, 26738, 26014, 29929, 36178, 13190, 88430, 71404, 41473, 40609, 73261, 64563, 46643, 81322, 74548, 56802, 74247, 52455, 67920, 3208, 12905, 85719, 11010, 59522, 49566, 24203, 93578, 90420, 76193, 63372, 49058, 72358, 25551, 93919, 54379, 93355, 31188, 32806, 43014, 92704, 33684, 27917, 91107, 61829, 44941, 84805, 49373, 15734, 66616, 42054, 27732, 26740, 29626, 68431, 56115, 88718, 76686, 22008, 16888, 56893, 3784, 78615, 81209, 72139, 46721, 68457, 32592, 87573, 15506, 8102, 51023, 30918, 93003, 59895, 57330, 76480, 30018, 69309, 29305, 20103, 51630, 75051, 63394, 28204, 49024, 44758, 77618, 92035, 64655, 76365, 51439, 33394, 14024, 92409, 43553, 63649, 53436, 47560, 55655, 98911, 87544, 4908, 49585, 65504, 43824, 19902, 50535, 42829, 40926, 69815, 27732, 89669, 64696, 36970, 97117, 86240, 55130, 905, 47520, 35509, 88406, 64934, 87212, 4362, 79214, 96191, 72446, 83436, 93952, 39176, 53789, 64572, 99842, 21734, 63547, 7866, 59155, 88440, 11772, 72582, 78750, 10177, 44439, 36871, 2622, 16025, 18193, 5264, 83475, 39905, 596, 34953, 45152, 75973, 42684, 15920, 2341, 50050, 3062, 76777, 26120, 37511, 47387, 15442, 29614, 5140, 80928, 38799, 8964, 26464, 43983, 97149, 14831, 46906, 92585, 37048, 7336, 43096, 84352, 75374, 35751, 38048, 89980, 84775, 90009, 43050, 77255, 56783, 75468, 87158, 79590, 48056, 92940, 82258, 8561, 1854, 70748, 9228, 69687, 27019, 28033, 76541, 1891, 88077, 59415, 33049, 61800, 29001, 60842, 40113, 94989, 94517, 71060, 3645, 55634, 87917, 84411, 84716, 9595, 92783, 83568, 83777, 71311, 99397, 80770, 74410, 16352, 20789, 80266, 3945, 16965, 83038, 82033, 74404, 85171, 92013, 4461, 65526, 61188, 67542, 39732, 70722, 8963, 35287, 6476, 98855, 15536, 57735, 50176, 19199, 91943, 36552, 22361, 50672, 20647, 63814, 48930, 68598, 58880, 62231, 93560, 77860, 25017, 38926, 58866, 89379, 44424, 3608, 6194, 82907, 76203, 97877, 69346, 85990, 93558, 37663, 17533, 44030, 98287, 71012, 55270, 13867, 7910, 60821, 35633, 77585, 47921, 53250, 5231, 912, 35041, 61148, 89778, 14632, 60887, 12612, 52311, 52643, 29271, 38935, 25516, 2218, 27732, 11060, 19028, 66113, 40141, 99731, 21487, 81395, 84005, 75331, 20970, 52263, 21048, 92455, 24042, 28483, 85270, 80177, 8613, 66046, 46802, 23983, 43951, 42058, 67990, 91737, 94225, 60447, 11027, 77436, 36322, 7354, 46018, 64745, 56414, 24125, 20047, 38601, 73219, 48093, 90578, 31546, 13712, 60609, 76483, 46306, 11055, 46414, 38913, 82987, 26047, 52248, 15128, 55244, 78642, 16320, 82977, 31877, 63301, 49074, 44601, 21040, 55247, 35545, 10812, 92421, 39338, 41725, 82158, 23291, 45192, 92576, 90751, 63040, 56935, 40873, 75918, 70528, 44634, 79068, 75761, 36921, 51374, 21113, 96760, 48345, 84413, 64674, 7761, 75922, 28442, 14399, 42286, 54940, 74681, 37703, 18129, 97450, 61097, 1853, 13405, 61329, 40157, 3550, 97486, 38305, 93591, 32913, 44248, 71178, 93770, 74914, 48286, 48202, 22848, 68804, 2750, 48553, 60975, 37646, 89652, 61372, 88237, 90246, 30632, 18842, 79348, 16854, 34458, 51636, 21380, 26956, 75009, 77894, 80243, 43543, 4520, 38233, 15832, 42280, 44021, 86433, 18715, 84785, 40303, 95924, 24925, 50981, 67821, 82804, 25097, 14770, 34275, 98986, 23241, 31719, 47235, 97001, 8706, 4831, 86055, 29866, 71528, 81000, 58258, 25890, 28753, 59723, 66522, 14002, 29110, 17453, 52236, 35103, 41899, 83167, 2107, 94975, 11557, 3620, 14863, 56466, 55180, 59653, 33602, 46044, 74559, 83876, 1986, 83454, 36382, 9982, 84471, 32359, 87617, 44151, 72207, 67117, 94784, 96415, 70299, 75595, 91895, 60036, 88270, 78250, 23523, 4751, 78396, 10809, 60038, 88419, 30903, 35489, 60171, 40561, 14109, 48111, 11127, 69719, 22309, 34856, 63954, 96702, 47632, 47083, 96909, 16467, 58581, 62344, 82199, 94420, 16697, 33620, 2019, 6501, 94483, 5585, 309, 19481, 1195, 90217, 41046, 29, 87919, 56933, 89082, 96256, 60757, 34531, 48157, 68119, 32800, 41542, 57929, 45963, 29091, 53445, 4952, 77163, 92254, 87679, 75580, 64300, 2794, 79961, 39911, 27460, 85650, 91906, 69846, 22878, 39295, 29464, 34669, 52779, 81925, 75600, 57392, 49051, 49894, 54370, 49410, 42390, 54897, 79470, 7781, 7005, 49788, 40248, 64504, 12616, 50762, 16002, 69729, 28671, 96052, 79230, 45999, 38708, 85158, 97, 79681, 44355, 58478, 40722, 54225, 94372, 20237, 12486, 83461, 13557, 26090, 73458, 38088, 75434, 89200, 60881, 61513, 23414, 56410, 38555, 41976, 29303, 57043, 79987, 68644, 16633, 17217, 87928, 89255, 14438, 42049, 38269, 88939, 84125, 72339, 8003, 57959, 22951, 46563, 28531, 72016, 37050, 18519, 26059, 65245, 8814, 47416, 47101, 57118, 28263, 93807, 41228, 42562, 92116, 32260, 15692, 40949, 27629, 56773, 18329, 5947, 26794, 8396, 72738, 41204, 55938, 30905, 14377, 74151, 97645, 18994, 78820, 2915, 75220, 1569, 62596, 65789, 9615, 26994, 95083, 97921, 49528, 23693, 13701, 20893, 93077, 99623, 60732, 49414, 26958, 93302, 60222, 20338, 23413, 13655, 41459, 36163, 22524, 86401, 79410, 94896, 10023, 98222, 21574, 72296, 5214, 28964, 76487, 63283, 85193, 91806, 43459, 16061, 58517, 22908, 60228, 31950, 71486, 6935, 99811, 50019, 9539, 83285, 52388, 11031, 7205, 52292, 47997, 57271, 64498, 18417, 6867, 24584, 40325, 36791, 51917, 96616, 84366, 40099, 59099, 86276, 85261, 39543, 86276, 67228, 48148, 65299, 46792, 20354, 25144, 20903, 36151, 9550, 45081, 34451, 24655, 59280, 25657, 11765, 52641, 89763, 1802, 20792, 55754, 32915, 82216, 76698, 94490, 49106, 275, 63561, 26506, 88528, 848, 89944, 75488, 39394, 95697, 77551, 9299, 6441, 66952, 48790, 67291, 30072, 62031, 30742, 1172, 12020, 7893, 15559, 80628, 10947, 62716, 27140, 56513, 24126, 79696, 86390, 91912, 70871, 6355, 39665, 20456, 42337, 50888, 1349, 16254, 89982, 98988, 57904, 46677, 55165, 13724, 5807, 87034, 97557, 1811, 92030, 31463, 93887, 36166, 88559, 13821, 33969, 52880, 87162, 73093, 31387, 11957, 52129, 77423, 82937, 2940, 43130, 96650, 67203, 2737, 15596, 65946, 43790, 88539, 10125, 49548, 36299, 44477, 88819, 30559, 32171, 26600, 39047, 93902, 46367, 83745, 93392, 41313, 24454, 18426, 6419, 5388, 22306, 60665, 77881, 21477, 7882, 74154, 133, 80172, 48246, 23712, 87176, 5377, 13908, 9610, 52615, 29520, 88177, 55935, 50575, 55440, 58706, 73689, 83399, 15704, 36081, 55846, 18165, 62098, 64540, 53681, 35509, 94617, 11033, 49963, 320, 40165, 96813, 92951, 56908, 98503, 4021, 34239, 91700, 62407, 69679, 38986, 33990, 63169, 59913, 65559, 90775, 56184, 55989, 63078, 48304, 65531, 69777, 55847, 12151, 15474, 36987, 86673, 61734, 5181, 22165, 54338, 82673, 91429, 84213, 79634, 95501, 76740, 4048, 2314, 96946, 83638, 61955, 37690, 73166, 92909, 51649, 6145, 96117, 77033, 84474, 16561, 94402, 54892, 17211, 64684, 58969, 42312, 74038, 7233, 51050, 88464, 80348, 97013, 18110, 22356, 63305, 43912, 55447, 60774, 63894, 68959, 98067, 31751, 45918, 60197, 19779, 57927, 80291, 75766, 7475, 2588, 73319, 4869, 32371, 15784, 68561, 91723, 76393, 88745, 43451, 148, 54691, 11675, 87292, 76690, 76354, 16995, 80789, 35972, 85277, 87566, 81937, 24286, 87907, 39542, 22983, 90285, 46529, 46947, 19161, 98260, 59839, 40231, 59762, 10943, 42929, 87760, 58210, 98799, 29598, 29478, 10480, 13542, 86373, 46569, 17866, 98613, 57540, 56743, 39158, 60381, 95766, 70354, 65757, 48445, 355, 40482, 95435, 50949, 2388, 93602, 17615, 46033, 97217, 47780, 56980, 42596, 98260, 46473, 48747, 89313, 38426, 45404, 52226, 87584, 59555, 99397, 67091, 37168, 99997, 38467, 43792, 84212, 90998, 28513, 82651, 51043, 2366, 89367, 18812, 82320, 53734, 60922, 70663, 69584, 41685, 61157, 13938, 42627, 11876, 39332, 66569, 29969, 20045, 14730, 95218, 60827, 96140, 78620, 96853, 55458, 37354, 66348, 89394, 94940, 32722, 29380, 70405, 34837, 50840, 7300, 52220, 39591, 3836, 72712, 28399, 78158, 19392, 86204, 71592, 98892, 15578, 58668, 41853, 4524, 79687, 79133, 60250, 61690, 26379, 82490, 31232, 30104, 59044, 98413, 87850, 91590, 58478, 88735, 45776, 95113, 88511, 9846, 93962, 80335, 65073, 56564, 12278, 55448, 22426, 32117, 72838, 25254, 21825, 10297, 87768, 40717, 51382, 86889, 74813, 41950, 13875, 47536, 8264, 67289, 16427, 45285, 14550, 14057, 4648, 65130, 2740, 57035, 12988, 24555, 16955, 37173, 89706, 1253, 50773, 91893, 7100, 79538, 4550, 74999, 85264, 4146, 60097, 47544, 5951, 75076, 58898, 36388, 83848, 99758, 20560, 38142, 19099, 69886, 29542, 96064, 33792, 27778, 58072, 68198, 74866, 60774, 73651, 21060, 24609, 92088, 14112, 78306, 14719, 74778, 11800, 33540, 97726, 76358, 14048, 86987, 45592, 76269, 53972, 64762, 92603, 78105, 82842, 66274, 56557, 97382, 44330, 300, 24815, 89306, 43071, 73013, 57932, 99066, 17994, 59503, 98376, 69832, 49228, 14810, 35275, 45711, 27603, 59675, 6706, 11671, 50582, 31760, 84795, 83758, 56084, 97854, 96191, 9546, 50310, 90043, 73097, 22774, 16179, 25422, 55586, 33949, 80772, 18335, 59008, 83632, 64628, 71233, 41260, 54220, 65989, 2981, 24686, 73110, 85662, 98901, 68766, 6602, 37581, 87523, 71558, 41214, 70036, 99783, 31850, 6593, 45852, 96840, 58097, 78171, 75568, 5114, 16693, 26119, 37976, 65550, 51459, 3944, 87390, 61305, 95411, 4895, 8909, 64454, 79247, 50451, 77156, 1082, 61702, 29750, 440, 87365, 34364, 67321, 57797, 35193, 55112, 35323, 45837, 79581, 42644, 97690, 49543, 15534, 21249, 39559, 82614, 14062, 29652, 94279, 52900, 74735, 21780, 23494, 30381, 98686, 22257, 74083, 46654, 46410, 58299, 63571, 13601, 33485, 80902, 29285, 68142, 32757, 49069, 64467, 21215, 7581, 45211, 50297, 6269, 88597, 50857, 15864, 59602, 94952, 44284, 37559, 33994, 11033, 64911, 93721, 18043, 95501, 7288, 84404, 17463, 10237, 66366, 82032, 47242, 51130, 17178, 6672, 76165, 51590, 82299, 90402, 40571, 83142, 40759, 93006, 30707, 20402, 54899, 50384, 89536, 87276, 92294, 51747, 68914, 18912, 78760, 45748, 3471, 54344, 69702, 48873, 95950, 27539, 83211, 67381, 1674, 9152, 49895, 61434, 21675, 21307, 16333, 5559, 97883, 6830, 2756, 57836, 80119, 67466, 84420, 4071, 96443, 14146, 67797, 25154, 31388, 21860, 65817, 64957, 24446, 84944, 26218, 34477, 16837, 84370, 59008, 89393, 9389, 76602, 97984, 76676, 22978, 61883, 78755, 25809, 32809, 92292, 59738, 80273, 53238, 31631, 40870, 58171, 25934, 57875, 39414, 46804, 7411, 17759, 18172, 7326, 19162, 26229, 93848, 90223, 49896, 83765, 9586, 32610, 80674, 66995, 32490, 54441, 14405, 71592, 54313, 69297, 22650, 80152, 91626, 34243, 3688, 7721, 55644, 81662, 44072, 34856, 53238, 74408, 95722, 43062, 94898, 99793, 36137, 59841, 76132, 96806, 84866, 30121, 76990, 50392, 24444, 83072, 71053, 85644, 24508, 67411, 14097, 37308, 47209, 67479, 10394, 89851, 57469, 38506, 23695, 7322, 47897, 53387, 25084, 1189, 5412, 4059, 83133, 89234, 1347, 81156, 32380, 42065, 61183, 25941, 62073, 31315, 96144, 81542, 96374, 62595, 31305, 91271, 63325, 50125, 94912, 81382, 92741, 79313, 72468, 43867, 7420, 74518, 78162, 23273, 98359, 55968, 83788, 86933, 72911, 74570, 23382, 14123, 27759, 63324, 32903, 22809, 49220, 60869, 89562, 28083, 34427, 81422, 22780, 57944, 42340, 39129, 74235, 75862, 78883, 84035, 43780, 47069, 4473, 93474, 24757, 59209, 93831, 71134, 68068, 7173, 81154, 44101, 56488, 42597, 1565, 7112, 34898, 6247, 55264, 33333, 29940, 1222, 69845, 84628, 70951, 66222, 16709, 13799, 35614, 99352, 10488, 16292, 34969, 78456, 61632, 1690, 24930, 41511, 7680, 69982, 3149, 49624, 73167, 54424, 48858, 5256, 49995, 10164, 84861, 38048, 74230, 87445, 21311, 86343, 64688, 86769, 82510, 94771, 56858, 86567, 85360, 54662, 53713, 42523, 569, 125, 24032, 72361, 58388, 76966, 34537, 20413, 71798, 98979, 3535, 95268, 79479, 51088, 1681, 13752, 11021, 7923, 73318, 29841, 83608, 41401, 82930, 65390, 69720, 42702, 11693, 50374, 40106, 39385, 88538, 16559, 70181, 78934, 47521, 14078, 86793, 66579, 26357, 42871, 70486, 36669, 96106, 14804, 84662, 66637, 88893, 94074, 41308, 61624, 5735, 74069, 82379, 85949, 92313, 96112, 28568, 24116, 53249, 52106, 16572, 88969, 5754, 20500, 25919, 12929, 56629, 12030, 39259, 22522, 5102, 89699, 32539, 41155, 46251, 72333, 82527, 48016, 46661, 45615, 34932, 62038, 69128, 80695, 4639, 98205, 72552, 219, 15988, 45378, 16460, 55747, 75464, 59404, 57121, 46322, 79947, 68186, 78604, 15354, 90273, 38518, 85519, 78803, 93416, 56072, 92619, 86265, 45, 58435, 21996, 4866, 753, 53269, 64519, 62661, 49915, 95756, 72457, 22270, 17163, 33063, 90992, 40998, 26296, 95708, 92580, 39992, 57457, 32325, 82122, 68901, 21266, 13999, 97137, 73102, 75321, 91012, 64944, 12882, 43634, 40098, 1928, 33485, 58628, 32628, 88192, 74966, 87223, 39226, 99380, 17837, 85544, 32529, 18363, 32528, 74112, 54835, 61945, 96038, 16007, 5121, 94839, 79836, 58490, 80449, 25858, 4365, 87790, 85160, 19587, 9893, 14032, 6605, 40215, 53286, 18093, 79817, 65074, 22363, 66799, 62080, 83683, 22209, 42885, 36435, 30991, 32888, 58523, 60637, 29341, 85211, 54372, 3623, 11062, 36657, 9422, 74198, 88506, 17576, 46737, 6153, 93853, 84720, 24735, 18478, 59542, 47905, 48369, 20696, 4881, 11005, 27815, 36297, 50487, 81822, 79309, 90798, 49998, 5273, 27270, 94702, 79362, 55670, 58833, 19769, 95532, 98412, 3875, 81069, 42667, 40871, 41702, 56856, 48333, 37007, 38982, 68807, 468, 75178, 22157, 74550, 94760, 84050, 92982, 75102, 80618, 99388, 26694, 19327, 97836, 30642, 59136, 18447, 35086, 22202, 58157, 18465, 59589, 30151, 87475, 70855, 93177, 88655, 55770, 53011, 77889, 44553, 86184, 43904, 53937, 23678, 79925, 40955, 98804, 38853, 14265, 34032, 99512, 40193, 11254, 6867, 97357, 53540, 33298, 63728, 53555, 52636, 68763, 43502, 96318, 50225, 89160, 93973, 58309, 40665, 15524, 86774, 77951, 68272, 9292, 3432, 99400, 35073, 69538, 54588, 20492, 47772, 99082, 85604, 71268, 29336, 47841, 83104, 36387, 84641, 2914, 99115, 80475, 83486, 84063, 40516, 30804, 73270, 34381, 86272, 85827, 1725, 36447, 52600, 82471, 59649, 50575, 88960, 41544, 17489, 26179, 30674, 3388, 56146, 47906, 7222, 95097, 18373, 1768, 95736, 27271, 8813, 84736, 97710, 30941, 17808, 50644, 13626, 25365, 96732, 8611, 97457, 51713, 73438, 71981, 99710, 21732, 448, 71588, 91118, 60586, 75548, 31930, 76730, 87878, 20564, 5611, 52871, 319, 77501, 12066, 47266, 95366, 93002, 89959, 71114, 70095, 30533, 2484, 35779, 97499, 4670, 21347, 16951, 24194, 33108, 77875, 41832, 36583, 74738, 40613, 8814, 18051, 51569, 57860, 17788, 94999, 24336, 89828, 44311, 29093, 18777, 29483, 1819, 59163, 30411, 69022, 20173, 2636, 2948, 20463, 56233, 27494, 97557, 34208, 12589, 64223, 75381, 76920, 41216, 94198, 69738, 75704, 38187, 1152, 22168, 22774, 90006, 73159, 58372, 65378, 25184, 91237, 27423, 82820, 90949, 97279, 21259, 25544, 23832, 75329, 34488, 61863, 25183, 48700, 34576, 32389, 84418, 37922, 69018, 47734, 35236, 8553, 91846, 23757, 98938, 75112, 69994, 80104, 52193, 32955, 84061, 71298, 85704, 24239, 83849, 91754, 32442, 4140, 51396, 77330, 24696, 30389, 30502, 97255, 67917, 30124, 58671, 80767, 22310, 41965, 25707, 91708, 60525, 40332, 163, 49360, 6934, 88796, 39685, 2373, 59526, 79827, 71729, 17509, 20681, 99048, 29081, 40629, 86696, 70505, 79934, 44121, 17229, 13055, 48653, 48232, 79829, 46571, 40176, 16293, 46797, 73772, 74924, 59137, 3722, 93918, 36264, 84361, 74322, 49230, 17978, 82483, 42331, 4770, 43100, 72334, 45516, 43479, 8872, 56770, 35690, 48204, 66164, 15, 9227, 44349, 37471, 34065, 12390, 68674, 22195, 85615, 16052, 65441, 83512, 81936, 76739, 99431, 36750, 20772, 79450, 1240, 58270, 13775, 67851, 88199, 28762, 91528, 8645, 56381, 92034, 95259, 82740, 42520, 65151, 25509, 55175, 63350, 8638, 76058, 57379, 67323, 24928, 7770, 12594, 93902, 89987, 18024, 75329, 71311, 31215, 4730, 70529, 25378, 23290, 37635, 17575, 35591, 49979, 4596, 89986, 37083, 21906, 22309, 93734, 74456, 16433, 22565, 68562, 83448, 66241, 18518, 95822, 41910, 62905, 40348, 94667, 65141, 46541, 16875, 23296, 55171, 8252, 45370, 85226, 20054, 24962, 97750, 45838, 15796, 1306, 1990, 43417, 24064, 91203, 94430, 85733, 59245, 90999, 33422, 86721, 28282, 69996, 74941, 24586, 44159, 38977, 52339, 93293, 64589, 33354, 49557, 63877, 35901, 43932, 49751, 57603, 11478, 65565, 5302, 20329, 25075, 48364, 62074, 29658, 15134, 71148, 28120, 38567, 43961, 17031, 85033, 27404, 80591, 22191, 36288, 90615, 44731, 30739, 57858, 69687, 39905, 96592, 19856, 5344, 10093, 22038, 21483, 17030, 75141, 75793, 30854, 23808, 50258, 94768, 87962, 94082, 4620, 75691, 58411, 30418, 43425, 27724, 6579, 79013, 42916, 9788, 61279, 69591, 31355, 24503, 180, 87539, 59125, 44256, 90064, 96051, 69004, 52568, 97734, 99956, 54981, 85624, 37165, 81163, 69740, 29422, 16291, 71346, 98405, 99617, 66996, 1181, 24683, 72239, 49805, 24151, 41803, 34262, 15291, 41224, 28700, 99728, 60520, 77123, 21558, 24476, 28351, 81486, 54478, 76335, 70383, 49371, 23845, 65782, 40732, 56631, 82037, 64685, 41325, 52291, 56154, 11140, 30634, 92665, 54137, 30270, 85417, 40427, 67504, 59801, 85947, 36772, 13443, 84477, 27374, 18769, 50422, 1944, 5366, 8819, 89896, 66268, 35071, 37643, 13958, 78394, 30825, 22522, 46016, 30355, 76771, 1535, 20535, 33755, 29443, 17037, 74655, 31004, 15677, 74417, 9699, 77673, 55203, 75908, 57532, 18998, 36650, 3999, 74563, 54748, 89442, 44110, 67891, 16165, 29992, 22998, 65935, 2852, 34048, 90883, 41648, 64484, 20927, 56208, 55286, 41299, 45555, 99604, 6998, 78426, 11974, 43386, 54954, 89661, 85445, 31050, 87768, 27712, 1973, 79886, 52562, 49999, 65541, 3128, 18864, 80606, 10524, 71744, 18381, 96845, 58064, 33907, 58605, 37297, 64385, 12098, 77939, 52937, 43939, 76791, 64025, 3889, 93943, 54566, 47634, 70436, 24264, 28737, 45448, 24907, 36309, 20677, 55775, 4501, 51347, 93996, 27359, 41943, 5831, 20703, 34500, 46696, 49838, 64832, 421, 89615, 65371, 45618, 76582, 71881, 91183, 89584, 52187, 27570, 12347, 13491, 51454, 74680, 26600, 37801, 6553, 76232, 13651, 9392, 57994, 78961, 56149, 74231, 97497, 74807, 98908, 29784, 48537, 41581, 90785, 76780, 25505, 48213, 15016, 7130, 43017, 39453, 87326, 73722, 16652, 67564, 54084, 61666, 12127, 15400, 46, 14349, 49296, 59389, 6229, 17010, 11905, 83072, 95880, 15880, 48140, 42298, 70241, 24494, 29418, 78082, 52360, 71128, 45212, 15372, 27721, 86754, 70704, 32677, 16843, 21658, 9064, 12265, 62257, 41380, 16344, 19691, 15965, 10842, 43325, 20003, 18835, 61491, 33954, 44527, 79888, 40384, 38370, 25445, 20187, 87248, 20883, 464, 86061, 84788, 51087, 82805, 33070, 56663, 19691, 26587, 32879, 77652, 25867, 19409, 99340, 44353, 28903, 81485, 32897, 80608, 8141, 57694, 44567, 15532, 86189, 73120, 99822, 90189, 86697, 53430, 43008, 3618, 9767, 99483, 45200, 55859, 95687, 50264, 8226, 37931, 75446, 72982, 87939, 47472, 14776, 26841, 59656, 2765, 1381, 15731, 60437, 23495, 48762, 90920, 55251, 94066, 84490, 94736, 96904, 18137, 95349, 14955, 96274, 76319, 475, 34400, 35196, 79011, 90526, 41404, 53897, 5687, 71463, 81633, 45810, 59994, 52667, 70606, 73542, 19634, 72735, 61811, 19187, 29715, 81351, 62819, 43629, 21893, 72365, 38884, 89866, 36201, 18416, 91920, 67379, 52063, 47701, 36068, 90238, 68595, 80269, 34569, 79178, 25188, 59984, 24316, 93063, 72410, 18429, 26389, 72929, 40404, 44629, 35797, 64214, 22693, 3138, 94184, 14817, 70562, 57989, 70838, 7590, 36871, 42827, 46036, 74778, 45268, 94729, 63781, 5938, 95078, 59610, 13677, 21644, 33058, 19197, 76974, 1183, 21819, 69469, 40588, 99146, 58117, 10037, 59466, 93162, 63660, 90206, 76821, 5139, 44278, 88827, 40497, 64236, 34055, 11097, 10170, 84717, 53819, 17799, 96267, 43961, 92117, 84674, 42571, 32075, 78290, 7531, 61448, 69634, 18426, 47870, 53570, 23598, 93969, 77529, 46920, 13569, 1692, 30386, 5983, 34088, 46075, 17597, 88647, 1688, 65679, 85757, 42295, 86486, 29653, 42881, 63131, 86464, 12395, 37924, 15545, 92995, 42023, 83824, 91659, 54616, 28105, 65064, 46178, 22531, 1653, 93605, 93998, 9044, 37929, 16498, 98115, 95693, 94326, 76137, 2560, 25437, 50777, 22359, 83181, 6945, 65103, 83955, 88489, 61370, 11072, 69819, 90352, 33954, 46519, 35036, 43363, 70569, 53424, 51711, 30166, 29757, 14090, 18978, 8594, 77143, 56800, 45808, 94709, 47679, 78436, 63684, 41736, 55195, 99741, 51279, 5208, 28683, 16579, 75897, 10421, 83166, 27167, 29246, 27152, 63572, 77657, 77028, 23016, 21341, 26280, 43692, 77613, 30247, 4488, 56369, 26455, 37894, 59934, 5470, 50103, 96907, 11545, 22350, 30720, 4681, 13513, 84078, 52123, 35520, 94482, 57321, 4080, 76271, 56315, 17240, 34658, 32521, 71001, 77004, 47614, 91927, 70875, 18586, 72610, 79724, 85696, 88773, 79028, 80526, 94057, 73803, 80082, 68593, 64138, 9714, 39457, 41494, 72594, 43557, 29097, 27343, 81428, 7958, 63007, 73749, 89400, 87288, 95271, 37406, 47714, 88360, 73780, 68270, 78068, 68459, 67287, 53066, 53341, 74945, 36908, 73592, 68653, 38934, 13818, 26061, 19948, 718, 37701, 31235, 27465, 35599, 44010, 87227, 90155, 78103, 86528, 77957, 1038, 33152, 26239, 60503, 41009, 95202, 18422, 89482, 11352, 71349, 5435, 73371, 27764, 98716, 26010, 6249, 71857, 27660, 90035, 62299, 8186, 98743, 85541, 98018, 16521, 34687, 69350, 30523, 58861, 48993, 85229, 43805, 42626, 30797, 8404, 50498, 79102, 98803, 74177, 38757, 31082, 83182, 59787, 41631, 15543, 19450, 85155, 93044, 79655, 6971, 28807, 54840, 52820, 88010, 28899, 15536, 77090, 56499, 27476, 26876, 43108, 29367, 42192, 36975, 85974, 41806, 67382, 27127, 47725, 80643, 37573, 69973, 92523, 15100, 96002, 25734, 92943, 38477, 47437, 39517, 70375, 49219, 9664, 94912, 1366, 61059, 96082, 80803, 53865, 30842, 72751, 56706, 93951, 1316, 30749, 21656, 93681, 74420, 93502, 55217, 11355, 32395, 17299, 7428, 32707, 2168, 29671, 11706, 35361, 97066, 55535, 69454, 447, 13176, 21342, 5998, 35299, 1672, 91597, 81140, 29715, 21503, 38417, 96027, 53710, 40118, 58726, 85935, 43466, 2973, 91698, 49024, 19601, 40518, 48824, 77119, 61501, 22711, 4234, 60608, 65872, 17253, 69225, 68311, 84192, 37580, 7023, 97278, 58350, 28990, 20635, 47906, 11791, 17889, 51605, 53421, 28506, 97631, 6152, 22240, 14036, 55881, 81405, 12126, 20261, 49890, 95656, 13373, 45673, 4099, 99928, 57674, 60350, 74314, 89745, 41248, 94793, 27545, 22012, 965, 40224, 9284, 11537, 73623, 95330, 15259, 73145, 15313, 27830, 61885, 45263, 44436, 66624, 11891, 41431, 34014, 14171, 63730, 87527, 34993, 6134, 20658, 91385, 23846, 27695, 17606, 7585, 92142, 39522, 22569, 5173, 73605, 43825, 71104, 47827, 90398, 63682, 99416, 560, 98471, 16946, 98292, 7802, 23830, 33802, 54559, 89150, 20388, 1754, 80848, 16196, 78629, 74159, 30158, 97646, 63739, 24121, 35711, 29778, 17360, 54505, 64653, 99703, 10257, 73587, 44181, 38809, 4388, 19959, 23236, 84735, 48729, 51817, 47375, 85738, 55755, 23189, 63689, 98310, 45711, 83163, 98001, 73709, 76652, 4328, 96778, 81140, 8985, 43761, 96777, 2836, 13148, 91260, 24267, 76567, 46812, 42382, 20757, 11826, 31716, 84607, 93786, 71478, 23465, 77455, 29896, 54243, 13782, 63460, 9627, 30115, 26012, 35402, 80820, 1189, 48043, 6053, 58116, 35617, 27315, 88493, 90229, 71670, 93081, 36563, 28536, 9097, 72134, 347, 25339, 21447, 14559, 75793, 19285, 16935, 85561, 52888, 97230, 21551, 19513, 50454, 9444, 56085, 19078, 28579, 66184, 4858, 60014, 95695, 77397, 26589, 63073, 40550, 82768, 61651, 57448, 16708, 48963, 74502, 84056, 51035, 88690, 45689, 11864, 46797, 60841, 45700, 39141, 59129, 5920, 53857, 39961, 95555, 61566, 26692, 33422, 76180, 39153, 15175, 97549, 32430, 48215, 72760, 19341, 56796, 79096, 83080, 12254, 29690, 74040, 7630, 62511, 26946, 42030, 46973, 88541, 54154, 46716, 61366, 46146, 40719, 5535, 73229, 54948, 35749, 56870, 11323, 79272, 78120, 82810, 91041, 89251, 79172, 2673, 91920, 44851, 41859, 41849, 17622, 97320, 12238, 44751, 97024, 67810, 54364, 99739, 22677, 83762, 10174, 49209, 17889, 75842, 12238, 78592, 20910, 45027, 48272, 84738, 4238, 76333, 13770, 8876, 21632, 58081, 68191, 95107, 48708, 37818, 83820, 45687, 54628, 81966, 48089, 18315, 79759, 61213, 95399, 47096, 77400, 86453, 16333, 46039, 18779, 7012, 20649, 20535, 44480, 52325, 3771, 4798, 45930, 78018, 66889, 71210, 76981, 30660, 30457, 18512, 92103, 77308, 56109, 24467, 83125, 70767, 50885, 7858, 14579, 64271, 67180, 84075, 95535, 76205, 66529, 3706, 76014, 57012, 65219, 37110, 83464, 60257, 91694, 40360, 65879, 74871, 22056, 66964, 11744, 31560, 71966, 28982, 1172, 44127, 40428, 57165, 31849, 73923, 12251, 90880, 81849, 61933, 69260, 28373, 34616, 56613, 47981, 31381, 95454, 89739, 43433, 92939, 10236, 84291, 5174, 43, 89683, 50438, 8960, 46615, 32365, 97702, 11330, 45908, 96501, 45641, 70718, 59374, 88336, 91486, 71778, 56590, 75346, 67857, 92440, 85503, 58020, 67802, 14868, 3844, 62895, 41386, 93324, 18642, 22261, 11751, 56983, 65389, 10296, 81752, 48824, 54443, 36536, 39070, 73167, 94385, 47177, 22165, 80999, 8538, 26403, 36219, 99868, 90716, 14292, 86607, 58514, 66235, 14488, 74193, 52721, 15153, 30161, 71098, 78460, 54212, 9439, 59853, 43728, 88154, 8378, 6845, 88740, 31418, 18520, 25959, 53003, 59309, 98135, 49204, 25142, 46393, 30677, 6972, 77351, 21879, 93253, 14279, 35398, 47376, 9785, 62421, 85616, 93037, 97456, 86916, 63452, 90395, 87820, 83180, 46489, 37115, 52371, 23628, 68465, 11379, 6590, 53634, 88232, 69049, 21478, 72793, 62931, 41497, 93118, 48107, 49080, 87941, 32205, 93316, 14138, 22689, 22472, 79221, 27424, 54357, 51401, 46432, 53442, 24661, 7874, 52966, 26041, 5139, 93644, 36799, 18759, 53546, 72522, 20571, 64878, 74862, 12954, 33903, 11454, 69692, 1588, 20124, 24868, 81323, 32547, 97692, 16929, 19018, 11398, 97924, 8030, 33462, 20013, 59552, 52608, 42735, 68647, 94852, 2441, 95345, 28482, 24976, 24748, 70411, 79869, 78092, 56095, 81483, 1477, 60425, 6487, 24948, 97948, 38371, 56241, 30827, 22900, 72128, 8393, 39524, 93271, 70556, 57446, 95856, 34780, 98884, 29949, 43200, 30751, 68, 26010, 7426, 98867, 111, 1099, 99848, 1100, 35093, 21140, 79071, 38771, 64189, 20070, 11987, 38527, 691, 3982, 48315, 51960, 25014, 49270, 57452, 24340, 87863, 19710, 73133, 11075, 46601, 74247, 807, 11120, 87299, 30312, 35600, 5851, 62060, 80538, 49889, 3197, 3365, 97640, 88883, 18414, 93840, 39598, 75212, 61819, 80922, 39285, 16085, 51296, 92220, 29916, 10857, 85732, 68666, 9233, 41592, 76923, 84217, 63070, 87526, 67935, 288, 27487, 24197, 60858, 37426, 4136, 47218, 50430, 22054, 2536, 22320, 64120, 28070, 50295, 24904, 27521, 77132, 51353, 24731, 47938, 21000, 73010, 29342, 65503, 78292, 94914, 96836, 88511, 19997, 88359, 58002, 36396, 85798, 24192, 41046, 36365, 17882, 37196, 96270, 131, 56224, 61379, 3612, 56891, 33852, 10849, 45734, 66913, 94484, 11130, 52398, 92594, 22515, 17375, 90455, 23134, 37664, 66630, 18309, 73321, 70545, 71742, 7039, 15998, 27440, 78912, 6776, 81055, 73442, 76830, 95474, 20584, 77260, 94876, 26553, 27306, 99880, 18711, 26659, 78127, 22534, 3311, 11793, 82879, 59064, 16893, 67616, 28290, 97837, 49649, 37716, 5713, 16641, 94426, 4600, 741, 55200, 99689, 45008, 29753, 44711, 13696, 38170, 24596, 38213, 55736, 99279, 83133, 52438, 67507, 39069, 83898, 94320, 24430, 21450, 41654, 88800, 79466, 14181, 73770, 39224, 51408, 94573, 66378, 19757, 24774, 55345, 46861, 481, 44931, 31314, 87244, 51338, 60826, 76882, 5883, 58471, 19005, 81575, 87075, 23091, 36441, 84501, 14031, 69736, 79763, 15584, 5623, 66687, 66905, 24751, 39618, 59229, 77026, 70589, 2961, 22757, 25973, 31806, 57243, 36933, 51385, 33106, 86, 63816, 3789, 45849, 75225, 33865, 77224, 16746, 82676, 59535, 5758, 26978, 15957, 65500, 37740, 16055, 51103, 72898, 97310, 24453, 1423, 50795, 56480, 39345, 29841, 61863, 36569, 47069, 44540, 9825, 7485, 78813, 52755, 49988, 54044, 56543, 67673, 53155, 17118, 62293, 90686, 81315, 57765, 37744, 10247, 88283, 60622, 42694, 89918, 3676, 36557, 24879, 96814, 13386, 11956, 98308, 13431, 41406, 44198, 66239, 58104, 80716, 45429, 13023, 33374, 90777, 37171, 56889, 46635, 57235, 38679, 66947, 16555, 3846, 62879, 9359, 47816, 9150, 29468, 36544, 44564, 18168, 83295, 67043, 22135, 19025, 1956, 96488, 56887, 17232, 87672, 8989, 14768, 43230, 27344, 5511, 7035, 90882, 5820, 32017, 80293, 49549, 62762, 93757, 47823, 1401, 11024, 46225, 31174, 67020, 96990, 9323, 24781, 64102, 79141, 79687, 3916, 2039, 44547, 40365, 52536, 30366, 89089, 1564, 17434, 26791, 23654, 64855, 30472, 64864, 47352, 75556, 3015, 64048, 72329, 76920, 44892, 8395, 38779, 73197, 95182, 21706, 89449, 85041, 15021, 34207, 49870, 1685, 13795, 97683, 8392, 84654, 94939, 66041, 74907, 98614, 4943, 16266, 65375, 8489, 17084, 82764, 88801, 66104, 97376, 77375, 28063, 74357, 4270, 46411, 13262, 41652, 15978, 30911, 10860, 21708, 71972, 90258, 94275, 38070, 25342, 64807, 60982, 25490, 61435, 93401, 85269, 80200, 55699, 15369, 39867, 89782, 81572, 69719, 6370, 72932, 37252, 52761, 34031, 87086, 70585, 95945, 22801, 46656, 91044, 89637, 47212, 97472, 39564, 30252, 9222, 9448, 82704, 64199, 26505, 84727, 27070, 53540, 90213, 72345, 5502, 75440, 75734, 4527, 8644, 12534, 6809, 72370, 35778, 8034, 64675, 31660, 25220, 54100, 96038, 69117, 72233, 22597, 37748, 10671, 36414, 40961, 93386, 38218, 34447, 11489, 9624, 78773, 89446, 93467, 82011, 20734, 66152, 42503, 32760, 63068, 12067, 30070, 39414, 25562, 98702, 29959, 36074, 35156, 77926, 40396, 74701, 33585, 56364, 15326, 28934, 88390, 5408, 65971, 22269, 78598, 69363, 11026, 65907, 20610, 99469, 87438, 40903, 31232, 52849, 20091, 98110, 26378, 8889, 82580, 6714, 67477, 85755, 24811, 24035, 95205, 16980, 16461, 23584, 80791, 23861, 57228, 27683, 14011, 72760, 85347, 71668, 63312, 27293, 82149, 51975, 73124, 19392, 24514, 12166, 21092, 52434, 27121, 65427, 49356, 36270, 41763, 94673, 76755, 68316, 26165, 27284, 27236, 68726, 3999, 64343, 10403, 61776, 95326, 65605, 80505, 15191, 88354, 80589, 28638, 27661, 25630, 55297, 14366, 64042, 88725, 9143, 10124, 31436, 31198, 75206, 70781, 42031, 21558, 21926, 16170, 78471, 66924, 53444, 47199, 56343, 96865, 72038, 9079, 10490, 32982, 58160, 40763, 64571, 63821, 32891, 78571, 4595, 8200, 83569, 29944, 98328, 61835, 72233, 38317, 21419, 72874, 7103, 94446, 930, 18507, 31609, 63669, 93736, 76112, 60911, 52086, 31702, 35422, 61774, 16954, 18747, 612, 53013, 59093, 2823, 65527, 18995, 50647, 56998, 16485, 4054, 2365, 68071, 58327, 85050, 12857, 22097, 80627, 14622, 50256, 2721, 34686, 21614, 78078, 95169, 83137, 71236, 53402, 80943, 46588, 12291, 2489, 24367, 54909, 24143, 42070, 70063, 55543, 42039, 34846, 69551, 2004, 15146, 77653, 78983, 57726, 35207, 65108, 44921, 90488, 62160, 82972, 44817, 78808, 92376, 96242, 82093, 4227, 19633, 68907, 32653, 1183, 91815, 10317, 10348, 53570, 34198, 59733, 33844, 28505, 60895, 59104, 69410, 46912, 453, 83893, 22045, 80582, 72647, 32122, 17299, 18842, 61127, 23161, 4341, 91140, 39576, 43212, 24358, 41604, 75463, 81567, 67694, 37461, 54183, 91617, 85440, 16609, 51563, 12380, 82201, 31462, 80046, 71837, 63122, 67641, 98575, 61298, 47595, 28701, 3010, 22938, 18225, 3950, 69501, 44625, 12577, 27504, 19362, 27276, 22233, 99328, 38407, 11515, 66642, 56890, 93268, 33914, 92986, 26322, 72928, 252, 98933, 8379, 23632, 64763, 47266, 92285, 92841, 4498, 62890, 10618, 9703, 48180, 60347, 69524, 96137, 60066, 38919, 35044, 92503, 13833, 50688, 53556, 27362, 94565, 87331, 36034, 4562, 52083, 84097, 17607, 17032, 68521, 98737, 43346, 53007, 74340, 24815, 51702, 93538, 40965, 61443, 49261, 39286, 24682, 92146, 74465, 76129, 59187, 57949, 68947, 7141, 30285, 1115, 55394, 96684, 99164, 91949, 80723, 86763, 59841, 95298, 34710, 10360, 66725, 4976, 91401, 15771, 95240, 53396, 18252, 59972, 57470, 77497, 58024, 3815, 64842, 34135, 22366, 82149, 32059, 86662, 46031, 74662, 73115, 29358, 41398, 25891, 4491, 88626, 7937, 88652, 47299, 56674, 41225, 69176, 72937, 7935, 42549, 4644, 41325, 50026, 99312, 92642, 74702, 84605, 48499, 60596, 37110, 75881, 22024, 17877, 34755, 67899, 43516, 66265, 96710, 99563, 69717, 84936, 74109, 7467, 73991, 1744, 56210, 17525, 24399, 50572, 77182, 14724, 71662, 3703, 24804, 50540, 55620, 33209, 18664, 41580, 35545, 10707, 82767, 34727, 96871, 43282, 17224, 90707, 65367, 96724, 23766, 95941, 39659, 83670, 69321, 8277, 54201, 42540, 86010, 82133, 8072, 12990, 5255, 38445, 1522, 50660, 54593, 83696, 3610, 85554, 23373, 5319, 77830, 3701, 25948, 37939, 96954, 5422, 72590, 1381, 19213, 10399, 12212, 4200, 60950, 34641, 62140, 36566, 90034, 13391, 8269, 62989, 27946, 96422, 70963, 30948, 64614, 37296, 60790, 41314, 49007, 34868, 42235, 32843, 31244, 88343, 34295, 33136, 90757, 85932, 39064, 44819, 35689, 74769, 44089, 2937, 69339, 37655, 90838, 7497, 50934, 20950, 39832, 78159, 64950, 18306, 20011, 32205, 69610, 96350, 1443, 17653, 15645, 89375, 822, 62195, 49456, 32092, 27405, 24899, 32845, 78658, 25417, 48207, 2890, 57113, 67781, 92937, 11581, 54822, 4693, 43562, 85170, 4522, 82922, 91270, 87294, 87117, 12536, 53996, 335, 89025, 16648, 54473, 25530, 51226, 25954, 18250, 36484, 87367, 26636, 92422, 71315, 12090, 12559, 75951, 99287, 84129, 93320, 95831, 81748, 77613, 33640, 78897, 4684, 36608, 22561, 12947, 26351, 19659, 42735, 79514, 82467, 71619, 49002, 95672, 96688, 77407, 85320, 21769, 38108, 35641, 32903, 57204, 33369, 9332, 61691, 2574, 61023, 69714, 54029, 97491, 27386, 60416, 87016, 72932, 42546, 9718, 82642, 67258, 42347, 32433, 14738, 68696, 59877, 72223, 58992, 14336, 59407, 78867, 70105, 55985, 30853, 59821, 85082, 65905, 67641, 40108, 67953, 43483, 30360, 16229, 84090, 75239, 22238, 2573, 47296, 35393, 39441, 33866, 69154, 28907, 33918, 31606, 64808, 6271, 31405, 9487, 94409, 83720, 93773, 71103, 2649, 49149, 8532, 22477, 24253, 40137, 85372, 76297, 36939, 93820, 40912, 84342, 54797, 85306, 80210, 1933, 78555, 13830, 14852, 99482, 329, 2207, 60233, 36928, 9293, 99347, 40384, 962, 11512, 52292, 27746, 3367, 85458, 56774, 7376, 28934, 29796, 60359, 11511, 61533, 6554, 83416, 54032, 13274, 7531, 41093, 4686, 66843, 1085, 34099, 74421, 98355, 64868, 16176, 77525, 33346, 71840, 84082, 30938, 87236, 41750, 72146, 44694, 65431, 53938, 80601, 50313, 49410, 10270, 17689, 82699, 27248, 7670, 36636, 27067, 21052, 88326, 67764, 53674, 87392, 40615, 15879, 2, 66518, 92300, 13979, 37256, 23524, 34317, 18658, 48602, 38745, 50808, 56141, 50551, 47700, 56300, 22645, 5980, 69516, 83809, 98762, 47013, 72726, 83229, 75754, 88826, 98899, 44911, 30662, 58336, 67395, 38736, 15929, 15634, 6706, 79883, 77398, 98953, 49875, 30833, 54305, 70310, 18252, 11732, 9016, 39796, 13580, 25017, 67107, 29764, 95173, 2030, 34864, 66867, 50414, 65715, 61763, 90826, 23912, 3352, 86511, 42492, 98754, 31556, 72207, 86043, 6414, 45928, 25997, 75077, 60609, 92865, 34986, 15302, 56671, 15914, 29358, 64661, 89763, 42334, 55867, 18501, 81285, 88646, 32201, 86293, 63007, 14915, 60399, 58984, 24427, 6515, 93389, 70182, 69385, 29492, 61734, 17629, 39525, 31008, 71006, 34590, 13009, 8951, 22226, 30002, 28170, 61164, 910, 59149, 30474, 69664, 88686, 83600, 19171, 69697, 34565, 55372, 42246, 86470, 93413, 19310, 13782, 56523, 68574, 28438, 25001, 25983, 78520, 24950, 45899, 33337, 72891, 47234, 130, 76026, 69793, 24271, 6437, 38519, 53956, 96131, 16004, 80462, 300, 74391, 67540, 1906, 52265, 85457, 98033, 70782, 42629, 61720, 75166, 91275, 10714, 68828, 81525, 48276, 68347, 79497, 79116, 23066, 6794, 3051, 98913, 85668, 60919, 3640, 76242, 25723, 87427, 41098, 57331, 97051, 70672, 73946, 2831, 64120, 1572, 77390, 79258, 43647, 42900, 48337, 69174, 7312, 4898, 56002, 39521, 67211, 3944, 47439, 88909, 45822, 96144, 29964, 63734, 13540, 33589, 25899, 13507, 25173, 36015, 32444, 82918, 41405, 58955, 57930, 81611, 43355, 71678, 10115, 93589, 17369, 30903, 7786, 6583, 7921, 5906, 1740, 44593, 90544, 4860, 65527, 70808, 8465, 55687, 75674, 5197, 9605, 63565, 54131, 60610, 62541, 45347, 19522, 40865, 64345, 26630, 45510, 56885, 90628, 20681, 16269, 23894, 36276, 24730, 96292, 68541, 49747, 2440, 86679, 79103, 82248, 9983, 95311, 23000, 85616, 70948, 78401, 2410, 69693, 57323, 73376, 59664, 14396, 7426, 48816, 36288, 90089, 69646, 14937, 181, 84770, 77772, 89239, 23386, 10308, 13929, 81085, 55040, 64520, 45329, 62933, 63718, 11163, 14513, 44810, 19631, 18600, 69880, 72040, 49220, 28818, 90663, 47211, 95061, 87562, 92687, 57606, 22860, 7123, 1505, 15718, 97156, 36405, 4251, 6971, 366, 78720, 12042, 58261, 48158, 2835, 60904, 68989, 9482, 53781, 61418, 85524, 43812, 57605, 29962, 21977, 46241, 4056, 35621, 2717, 5779, 36163, 49685, 1045, 28379, 80394, 85769, 48382, 81736, 35785, 65590, 62609, 353, 65470, 88995, 33387, 86812, 7025, 3851, 29244, 65947, 2873, 49038, 5367, 85480, 58462, 30775, 24656, 31690, 29189, 68392, 38515, 27898, 45562, 87592, 58589, 85356, 18943, 57379, 10075, 19406, 20507, 21971, 6150, 16165, 5598, 50268, 24354, 68021, 31700, 49457, 15546, 89553, 80095, 52028, 61165, 31948, 29717, 89086, 12830, 91481, 47623, 83556, 73117, 70614, 76566, 40320, 96865, 70757, 67652, 69259, 43717, 65834, 19194, 45659, 38442, 79249, 53357, 30310, 88243, 40246, 77136, 15024, 92706, 69281, 63510, 84538, 22937, 79162, 64730, 34092, 91318, 49988, 92055, 2655, 40396, 11581, 68759, 50462, 97074, 68324, 56483, 69639, 77202, 31894, 47528, 32229, 23317, 76951, 50191, 94913, 72074, 32957, 30712, 78348, 1895, 94263, 61675, 27320, 66053, 20233, 62977, 42224, 85134, 30781, 63267, 92363, 28232, 30290, 15495, 23714, 23994, 72270, 3820, 19819, 61268, 18554, 25480, 30453, 47073, 15061, 11539, 20977, 11510, 86100, 22648, 25869, 75561, 77302, 78401, 74120, 33298, 6470, 63310, 771, 86833, 70454, 14662, 99254, 72387, 21734, 24690, 84407, 1174, 23586, 7273, 54509, 52974, 28084, 22132, 83850, 49122, 37762, 84192, 78673, 65837, 970, 81220, 11363, 17785, 26603, 3805, 88219, 46381, 86800, 88112, 58652, 12119, 32701, 68478, 70297, 49800, 84769, 72117, 3273, 72481, 70064, 1590, 48366, 30571, 70126, 37412, 97400, 71845, 25474, 9082, 17445, 15908, 53408, 71262, 28141, 58212, 6805, 61325, 72971, 55941, 1336, 2274, 43897, 88393, 40938, 17887, 8666, 35532, 20402, 60873, 7568, 20444, 11127, 94184, 21041, 44348, 99276, 21780, 22058, 91269, 53400, 39786, 71317, 31372, 20976, 97324, 3910, 75513, 20311, 77546, 3605, 19096, 85513, 72024, 68749, 43916, 16064, 61682, 64066, 50337, 11759, 68566, 67050, 8976, 21258, 73505, 98856, 92368, 73965, 98401, 2857, 69439, 77252, 41299, 79570, 9935, 19089, 11293, 68516, 10043, 5615, 80989, 85340, 15845, 31778, 55273, 97107, 84503, 57544, 87650, 41762, 65128, 56238, 7517, 97866, 19534, 2518, 84233, 44236, 63217, 59458, 17042, 9780, 49363, 19501, 99089, 98016, 45619, 27364, 96199, 9518, 45877, 29172, 70071, 35085, 42223, 10660, 49213, 15927, 6095, 36543, 75253, 42225, 46122, 52346, 19002, 71312, 62297, 90075, 10460, 75500, 89784, 27041, 76920, 84177, 8922, 16508, 47587, 97534, 67460, 9015, 76798, 87140, 52251, 89651, 34112, 4025, 58628, 88951, 21618, 7653, 76670, 24594, 82183, 2379, 11711, 17295, 25545, 28400, 59349, 82831, 44866, 69273, 90634, 82099, 13522, 6614, 5353, 34151, 35684, 99743, 89164, 90158, 82470, 25127, 14227, 99529, 4463, 12536, 96059, 61136, 45775, 81925, 98411, 67959, 13271, 68890, 69104, 13250, 32079, 87489, 70260, 35876, 88921, 8917, 87281, 34310, 22113, 10554, 5276, 91276, 68971, 11587, 13578, 52945, 16413, 96386, 51785, 41888, 11625, 7790, 18094, 78870, 62828, 56172, 80431, 5959, 8430, 29089, 18750, 64054, 56367, 60978, 84622, 34094, 46037, 61760, 21312, 99530, 37920, 21539, 82836, 62772, 54796, 4465, 12423, 66553, 33395, 82310, 11875, 48287, 5576, 41948, 29547, 95074, 19664, 71910, 25485, 31191, 42542, 37618, 90690, 53300, 56313, 92015, 50515, 85763, 70902, 73934, 46203, 78805, 18189, 27905, 40403, 15448, 7627, 28615, 65582, 54982, 60118, 59979, 89500, 32586, 78449, 19069, 52334, 18669, 26873, 76426, 51152, 97017, 94948, 59124, 2965, 69127, 10341, 83200, 76198, 851, 22287, 49983, 53333, 78496, 65942, 60733, 29271, 51521, 85811, 10185, 68025, 99406, 79343, 7258, 98168, 51468, 89284, 86222, 40357, 14041, 69135, 2915, 96258, 53389, 13257, 96846, 90394, 41983, 51312, 59376, 69673, 3049, 82367, 46875, 77121, 13345, 10903, 39741, 25734, 80080, 88204, 9841, 22307, 81410, 16939, 66381, 77390, 90363, 11914, 91300, 89530, 41952, 71523, 71926, 96452, 3835, 87040, 69711, 2953, 59157, 97877, 54112, 11522, 10590, 90944, 24083, 42619, 65312, 90695, 12370, 51551, 57800, 39296, 66144, 50630, 81833, 98194, 61195, 87583, 91921, 82220, 86304, 98627, 21669, 95394, 61801, 16487, 60901, 83746, 94506, 73366, 73894, 69210, 13035, 84754, 46294, 76302, 74096, 92650, 1722, 76820, 38975, 92159, 6917, 56671, 29107, 19285, 15928, 61722, 81098, 78684, 96879, 51464, 62307, 28953, 12160, 32107, 96068, 84936, 55956, 70166, 49384, 23995, 5340, 74226, 99471, 11305, 49471, 25985, 48590, 66511, 4374, 92552, 7314, 14575, 96558, 46859, 11191, 12743, 43410, 53605, 95818, 68536, 61003, 71136, 67713, 65533, 22081, 78801, 1698, 30043, 79195, 19, 93188, 7906, 9477, 18485, 37346, 37196, 5790, 1844, 79015, 92080, 12934, 80113, 60857, 46234, 1756, 72620, 43981, 27619, 84751, 94989, 29754, 19258, 76564, 6385, 6444, 57457, 19990, 72834, 95797, 69856, 74238, 85919, 30405, 72579, 61349, 20596, 1629, 61645, 17813, 46765, 55714, 96823, 85544, 7835, 24429, 67205, 71845, 752, 91182, 45988, 17282, 11308, 70063, 9293, 72263, 31797, 83213, 76893, 40420, 82962, 51579, 35307, 93209, 20327, 86563, 48786, 68787, 295, 35134, 88782, 45750, 39597, 11650, 15186, 14316, 66775, 69095, 13999, 72357, 32821, 55467, 27552, 49053, 43486, 21199, 65561, 92555, 72388, 7516, 45421, 54089, 45966, 85323, 31534, 35115, 83959, 15176, 31737, 18728, 27213, 26439, 57309, 77871, 82604, 4031, 96121, 84958, 85295, 92966, 18770, 3035, 72008, 29035, 62673, 65615, 86576, 90373, 15780, 47411, 67380, 18472, 21350, 82345, 58861, 82779, 39947, 56285, 17426, 1809, 12489, 86057, 69767, 67915, 30421, 8906, 87281, 20280, 33840, 55980, 45215, 35247, 74257, 32723, 6150, 26440, 9090, 5707, 26234, 67055, 52990, 84262, 28027, 97072, 57920, 65343, 60646, 23656, 46004, 15416, 44536, 58972, 70592, 53858, 31315, 68229, 25517, 95629, 2601, 58582, 81955, 20961, 31816, 29270, 23140, 79213, 12535, 33710, 20458, 82879, 60015, 51676, 24639, 79545, 40075, 87473, 27349, 16268, 82194, 48201, 11049, 96526, 12935, 24059, 94636, 76186, 4896, 15838, 43784, 51795, 18906, 74413, 45741, 79578, 30262, 27109, 65828, 39018, 60712, 67750, 95926, 66701, 88812, 36913, 41471, 49953, 77286, 90414, 31370, 70, 10695, 25380, 20154, 59964, 34132, 11037, 62728, 89002, 61872, 10505, 96253, 72212, 87201, 2093, 29969, 37860, 75358, 9273, 10444, 91684, 94832, 20147, 77371, 59957, 62895, 51944, 88570, 97124, 19099, 48446, 18703, 50114, 98017, 75259, 86133, 65282, 7155, 68478, 96905, 69489, 91811, 98217, 566, 62406, 52640, 42038, 76039, 36920, 17139, 79106, 47655, 7316, 46149, 95081, 99102, 35393, 26662, 36610, 53446, 36274, 86569, 86439, 43140, 61344, 44498, 60927, 72411, 21178, 66084, 80215, 99166, 87260, 99072, 84330, 20257, 70882, 13236, 3909, 27428, 16488, 93527, 13733, 3706, 93408, 58982, 71692, 9302, 85321, 56782, 38586, 70643, 27650, 30984, 27355, 45566, 51329, 68281, 81848, 71023, 18085, 90896, 23678, 86594, 19014, 26449, 53670, 59257, 19262, 40050, 50528, 92858, 94741, 77905, 15366, 44671, 61571, 17913, 5547, 77664, 99508, 7326, 98062, 53733, 12433, 85775, 365, 42867, 8739, 45946, 97654, 36613, 27443, 32744, 26296, 81358, 693, 1378, 16181, 44592, 94770, 68471, 44350, 93590, 73702, 92281, 57226, 51634, 72603, 27765, 39208, 14491, 59611, 96253, 6075, 80646, 23294, 28712, 88887, 68619, 43343, 71123, 3891, 50969, 54525, 36918, 15552, 1161, 42991, 64457, 4955, 47966, 87911, 56223, 77851, 91390, 1002, 92588, 92276, 20087, 69705, 25026, 11491, 48279, 25377, 88985, 91170, 18583, 81462, 13248, 1449, 67903, 16353, 10155, 60289, 91595, 22445, 98451, 48646, 28507, 53829, 68542, 23615, 90977, 7847, 82879, 87220, 40158, 94374, 80437, 72374, 1338, 37773, 4642, 29634, 43964, 13120, 97326, 76412, 40513, 18962, 5385, 55664, 34771, 36648, 53625, 59681, 56385, 43982, 91753, 73562, 23165, 46492, 93042, 50055, 50388, 14590, 94307, 79626, 11982, 19049, 15363, 95127, 89452, 72525, 36886, 16839, 26612, 78360, 84082, 71613, 36896, 22318, 92370, 38065, 37824, 11183, 6029, 94915, 19553, 81525, 95461, 6342, 4972, 95047, 19369, 96931, 79639, 92470, 4905, 88787, 18110, 29467, 71591, 40694, 55540, 69720, 30886, 65973, 12755, 40041, 47009, 94123, 80994, 86278, 82320, 32873, 5770, 82979, 22154, 58708, 84973, 11980, 94940, 21368, 24708, 78365, 76056, 47800, 90303, 53302, 47675, 3657, 91879, 41185, 77952, 900, 63892, 78468, 31158, 60086, 97937, 10190, 29859, 13647, 45930, 80999, 2831, 84050, 50520, 77137, 70577, 6420, 99987, 49750, 67092, 40325, 9930, 97965, 61700, 14952, 60842, 23554, 49822, 30254, 66662, 68078, 40792, 85715, 37099, 69398, 60150, 40812, 89494, 88670, 19761, 25966, 69462, 4580, 1389, 19312, 84849, 77992, 36642, 25526, 94951, 52968, 61014, 49534, 14099, 95877, 98161, 61064, 77726, 54421, 22812, 95971, 97476, 81211, 86545, 56906, 69118, 83297, 48575, 13850, 12999, 75306, 55124, 66515, 24659, 2258, 60527, 94612, 92434, 27609, 65913, 20326, 46775, 21547, 70803, 23145, 50773, 9351, 22195, 82376, 45895, 10792, 48427, 22794, 58102, 87266, 46111, 71249, 93522, 28972, 35458, 42856, 12790, 64463, 76638, 37153, 93361, 55795, 97913, 74968, 58425, 83363, 16367, 32505, 452, 97919, 77333, 48271, 89172, 48121, 43796, 11250, 83529, 48865, 79714, 5045, 96144, 24179, 3932, 36938, 67951, 89452, 69221, 61477, 95295, 94727, 64903, 42281, 81143, 72837, 53915, 36459, 31318, 23940, 57998, 52688, 18711, 95013, 67174, 14216, 33072, 29553, 74096, 41235, 42744, 62355, 69016, 53585, 63535, 5072, 65797, 16187, 51998, 65583, 6938, 64366, 12009, 72327, 72295, 70960, 65871, 87041, 45592, 7605, 21651, 95102, 984, 87256, 59993, 93781, 63608, 92953, 86421, 72373, 43063, 47082, 27552, 28082, 11057, 71043, 31189, 68583, 91831, 36272, 4418, 35868, 7588, 66462, 34959, 68099, 73842, 25065, 6504, 71151, 49272, 84028, 40809, 31675, 2815, 1243, 44732, 42482, 50949, 39858, 81565, 86376, 60684, 45412, 18175, 81755, 44676, 23119, 22685, 87936, 77252, 70982, 68426, 85842, 47008, 83842, 45842, 86029, 58235, 99789, 11035, 16895, 3817, 12769, 79680, 1530, 21827, 54046, 66016, 59811, 75463, 8743, 44648, 24367, 98232, 99723, 75611, 45916, 81978, 55137, 58599, 63702, 17108, 74056, 37093, 17426, 92107, 75916, 93106, 85593, 82751, 37593, 32971, 49096, 64687, 23940, 53490, 80303, 71553, 38165, 71701, 96459, 82512, 68308, 41952, 25366, 9110, 12294, 8630, 73560, 84948, 13165, 52533, 33777, 13817, 86644, 88384, 67522, 57555, 90661, 41470, 30739, 19842, 59822, 26142, 63600, 85103, 19247, 40702, 27460, 2722, 21585, 63699, 74979, 95780, 2173, 70258, 76300, 48965, 2954, 24492, 29590, 72467, 26989, 87634, 51823, 2457, 42382, 36872, 93399, 30351, 18108, 9507, 63807, 68823, 18289, 21777, 42058, 35399, 11676, 53534, 70251, 3176, 18021, 16514, 27318, 91933, 16342, 39932, 93964, 20670, 30527, 63959, 62909, 54095, 27887, 44108, 54308, 3959, 27611, 37614, 53515, 65204, 50814, 65152, 97305, 84097, 98786, 65904, 88739, 72775, 5216, 63786, 15454, 40584, 57319, 33573, 99742, 91763, 79728, 13948, 63013, 6743, 47194, 93165, 40927, 60418, 80400, 36330, 68675, 18413, 35031, 25919, 29500, 35178, 69790, 58157, 88177, 48425, 93333, 10686, 24910, 93003, 87785, 30473, 86997, 34100, 36711, 97111, 84245, 75220, 89180, 52922, 52521, 63329, 65418, 44166, 90241, 15224, 12111, 82866, 45481, 84031, 64545, 62644, 9130, 36530, 71723, 14939, 80662, 12770, 97201, 14546, 24949, 22492, 98650, 72088, 56637, 55012, 50227, 27197, 98806, 62139, 65543, 30792, 19730, 15566, 99106, 57626, 9279, 69297, 12570, 89322, 18735, 20135, 58645, 17091, 90716, 17058, 21717, 63657, 20173, 76074, 18059, 239, 48611, 94947, 84320, 72999, 24107, 81765, 4813, 36720, 40951, 8633, 85690, 76237, 42191, 55507, 11756, 91047, 35777, 24642, 25104, 42779, 89669, 81728, 77266, 93672, 31487, 20049, 79478, 67550, 62335, 92881, 5823, 70587, 24484, 54709, 36623, 68473, 20041, 44197, 82346, 97675, 60928, 28673, 85365, 40869, 8517, 82807, 38039, 70803, 61272, 82282, 16246, 81063, 57523, 59962, 38001, 92965, 77787, 46454, 77026, 20814, 697, 243, 951, 991, 521, 130, 369, 601, 254, 612, 64, 287, 84, 216, 315, 296, 367, 167, 245, 588, 240, 51, 784, 630, 702, 499, 378, 271, 865, 862, 269, 25, 647, 889, 920, 729, 359, 642, 243, 574, 475, 585, 387, 292, 236, 590, 839, 278, 481, 84, 101, 151, 795, 148, 233, 613, 241, 686, 555, 616, 929, 224, 15, 608, 412, 148, 532, 938, 964, 899, 272, 591, 184, 231, 640, 239, 460, 529, 454, 943, 565, 991, 829, 434, 767, 452, 122, 73, 485, 149, 31, 475, 898, 794, 19, 313, 372, 181, 788, 279, 220, 68, 955, 423, 547, 33, 990, 895, 463, 879, 761, 255, 606, 197, 884, 351, 420, 594, 806, 97, 790, 664, 217, 513, 258, 16, 711, 492, 796, 280, 883, 538, 316, 302, 280, 848, 897, 907, 538, 692, 805, 635, 739, 207, 90, 887, 522, 552, 976, 694, 642, 936, 497, 182, 68, 215, 221, 252, 711, 921, 750, 872, 172, 31, 783, 998, 427, 365, 345, 188, 600, 843, 153, 798, 747, 101, 564, 29, 690, 202, 711, 543, 803, 691, 811, 26, 588, 90, 533, 142, 689, 29, 696, 179, 757, 556, 889, 353, 980, 1, 391, 165, 44, 703, 949, 656, 220, 127, 712, 741, 207, 557, 660, 413, 396, 296, 999, 205, 372, 235, 669, 881, 924, 687, 342, 675, 460, 406, 4, 237, 847, 25, 995, 805, 279, 310, 593, 3, 63, 218, 246, 454, 267, 501, 534, 623, 878, 137, 938, 247, 975, 17, 162, 384, 353, 506, 207, 281, 112, 320, 834, 414, 961, 479, 534, 259, 582, 221, 443, 472, 658, 286, 197, 694, 780, 393, 888, 736, 83, 370, 727, 298, 666, 655, 539, 572, 952, 527, 803, 111, 506, 70, 785, 416, 199, 37, 940, 735, 348, 42, 844, 428, 637, 704, 422, 780, 989, 692, 679, 203, 694, 317, 335, 192, 458, 446, 673, 672, 261, 954, 860, 803, 330, 420, 454, 552, 491, 782, 889, 875, 637, 674, 248, 734, 439, 663, 865, 658, 689, 937, 275, 132, 1, 637, 459, 214, 847, 210, 458, 386, 150, 8, 223, 780, 766, 691, 812, 721, 782, 641, 330, 66, 568, 422, 614, 340, 654, 363, 895, 156, 759, 763, 182, 28, 847, 110, 181, 700, 738, 54, 654, 676, 877, 607, 540, 473, 881, 873, 10, 61, 169, 306, 876, 990, 904, 998, 896, 552, 258, 714, 990, 714, 841, 658, 543, 986, 709, 978, 293, 696, 928, 293, 842, 34, 871, 732, 500, 690, 575, 464, 826, 316, 81, 1, 128, 696, 6, 905, 959, 244, 653, 74, 960, 475, 115, 405, 435, 253, 802, 625, 75, 997, 244, 589, 229, 291, 900, 201, 244, 344, 514, 686, 390, 935, 553, 67, 927, 337, 981, 505, 775, 78, 976, 65, 154, 656, 295, 220, 80, 780, 904, 933, 786, 341, 674, 498, 125, 180, 335, 362, 168, 62, 633, 604, 707, 883, 727, 444, 467, 522, 7, 653, 206, 368, 309, 525, 537, 797, 1000, 99, 669, 812, 872, 624, 749, 335, 542, 36, 766, 1000, 648, 335, 798, 307, 828, 332, 753, 529, 594, 638, 453, 877, 248, 757, 492, 432, 572, 896, 586, 345, 464, 946, 945, 363, 418, 855, 81, 462, 537, 677, 872, 740, 469, 359, 26, 145, 278, 281, 91, 494, 757, 970, 322, 594, 498, 814, 224, 239, 130, 810, 457, 650, 899, 76, 329, 995, 107, 427, 269, 700, 791, 297, 437, 908, 826, 21, 285, 369, 619, 752, 204, 243, 434, 671, 67, 236, 405, 721, 904, 74, 687, 78, 462, 847, 644, 7, 485, 947, 487, 246, 113, 52, 113, 334, 715, 226, 339, 474, 993, 480, 461, 235, 878, 841, 22, 465, 417, 416, 486, 509, 579, 965, 714, 715, 186, 694, 264, 919, 506, 283, 888, 392, 190, 799, 734, 50, 489, 649, 881, 100, 113, 121, 593, 176, 205, 712, 688, 938, 752, 575, 450, 995, 211, 165, 237, 502, 830, 97, 78, 837, 148, 153, 337, 525, 788, 608, 698, 790, 580, 355, 747, 946, 50, 655, 522, 191, 172, 670, 258, 163, 229, 230, 402, 152, 832, 318, 925, 512, 28, 682, 556, 188, 850, 217, 254, 781, 287, 633, 906, 575, 252, 7, 483, 648, 958, 349, 444, 384, 176, 167, 41, 95, 671, 176, 157, 348, 715, 999, 990, 408, 893, 806, 269, 194, 473, 981, 980, 577, 201, 973, 71, 523, 88, 383, 526, 143, 702, 51, 317, 54, 930, 170, 374, 216, 416, 120, 24, 882, 372, 240, 377, 513, 945, 722, 692, 680, 585, 729, 303, 55, 940, 929, 597, 550, 482, 931, 97, 548, 125, 544, 237, 5, 454, 196, 31, 412, 643, 830, 56, 462, 663, 8, 103, 893, 285, 637, 96, 868, 558, 772, 135, 627, 10, 359, 259, 573, 667, 579, 45, 669, 528, 797, 108, 195, 244, 746, 226, 937, 96, 722, 609, 65, 628, 55, 426, 991, 214, 342, 653, 19, 847, 220, 906, 857, 298, 835, 574, 135, 236, 944, 274, 170, 466, 974, 730, 23, 804, 793, 374, 202, 527, 414, 486, 298, 696, 632, 837, 647, 348, 582, 151, 588, 187, 380, 218, 616, 686, 825, 395, 277, 907, 184, 476, 99, 945, 440, 54, 851, 904, 36, 480, 354, 817, 61, 438, 505, 987, 758, 841, 508, 360, 195, 420, 234, 808, 899, 687, 173, 491, 614, 986, 916, 180, 480, 782, 790, 708, 349, 401, 816, 830, 607, 195, 302, 465, 391, 191, 802, 513, 93, 606, 442, 691, 921, 549, 354, 971, 827, 79, 882, 578, 303, 940, 818, 790, 893, 289, 757, 458, 598, 379, 953, 501, 250, 280, 808, 577, 326, 795, 939, 120, 827, 535, 748, 432, 762, 473, 120, 582, 332, 10, 466, 996, 200, 394, 589, 555, 155, 312, 948, 801, 94, 609, 61, 380, 760, 471, 603, 891, 771, 340, 615, 583, 708, 888, 424, 852, 262, 331, 883, 509, 497, 619, 181, 454, 239, 683, 25, 693, 363, 881, 624, 476, 619, 379, 684, 993, 239, 789, 145, 388, 441, 629, 549, 489, 174, 864, 199, 13, 493, 317, 748, 23, 914, 696, 509, 694, 792, 270, 158, 164, 795, 691, 546, 680, 776, 422, 665, 507, 991, 45, 187, 37, 405, 765, 924, 41, 364, 767, 1000, 777, 403, 475, 9, 812, 326, 63, 77, 677, 205, 243, 515, 395, 832, 335, 794, 617, 351, 694, 497, 859, 329, 722, 137, 221, 403, 458, 508, 974, 529, 281, 310, 85, 858, 721, 556, 374, 862, 823, 336, 970, 425, 374, 997, 222, 142, 360, 83, 833, 928, 852, 212, 728, 741, 828, 155, 484, 45, 2, 740, 539, 57, 545, 780, 489, 654, 37, 368, 735, 135, 792, 264, 988, 63, 193, 172, 1000, 127, 299, 700, 886, 135, 886, 957, 543, 367, 929, 285, 503, 145, 634, 437, 928, 213, 742, 568, 954, 47, 22, 7, 219, 852, 246, 501, 598, 88, 740, 632, 812, 416, 397, 68, 845, 377, 693, 402, 715, 206, 465, 23, 123, 538, 804, 30, 891, 670, 738, 781, 900, 537, 258, 134, 657, 295, 503, 255, 719, 850, 506, 622, 172, 39, 285, 986, 723, 356, 282, 371, 141, 797, 183, 846, 91, 555, 689, 866, 927, 842, 712, 309, 401, 333, 231, 591, 677, 206, 879, 917, 76, 122, 468, 549, 530, 747, 241, 640, 940, 663, 182, 799, 380, 928, 29, 804, 423, 680, 545, 669, 930, 758, 622, 974, 661, 63, 354, 704, 707, 484, 518, 955, 626, 390, 762, 282, 222, 974, 132, 51, 211, 64, 213, 965, 174, 296, 132, 799, 211, 856, 724, 398, 918, 992, 858, 516, 276, 178, 484, 258, 850, 754, 158, 546, 747, 994, 586, 941, 807, 390, 554, 718, 984, 164, 242, 995, 440, 113, 873, 217, 452, 664, 174, 984, 48, 742, 891, 372, 462, 885, 553, 996, 669, 527, 105, 760, 241, 660, 684, 868, 816, 438, 863, 126, 573, 242, 147, 210, 475, 697, 246, 440, 805, 168, 402, 456, 894, 514, 154, 504, 652, 604, 509, 981, 464, 298, 671, 242, 199, 425, 912, 836, 301, 688, 973, 836, 728, 186, 581, 97, 422, 177, 307, 829, 3, 49, 192, 374, 379, 164, 879, 909, 48, 354, 413, 342, 29, 225, 264, 167, 150, 369, 913, 52, 413, 785, 632, 2, 44, 597, 996, 413, 785, 111, 853, 633, 322, 306, 204, 466, 306, 442, 446, 221, 816, 198, 609, 140, 662, 893, 997, 277, 826, 139, 405, 833, 243, 332, 318, 931, 33, 338, 817, 316, 371, 960, 77, 701, 288, 956, 744, 400, 931, 18, 572, 875, 979, 102, 471, 699, 377, 783, 343, 328, 78, 644, 626, 42, 873, 533, 429, 641, 631, 844, 212, 98, 341, 837, 917, 278, 699, 946, 257, 640, 678, 719, 362, 209, 209, 70, 640, 481, 1000, 226, 406, 11, 414, 390, 547, 46, 784, 203, 456, 204, 955, 604, 105, 955, 148, 211, 652, 306, 914, 472, 980, 599, 408, 741, 60, 419, 384, 534, 186, 63, 743, 461, 260, 124, 399, 158, 831, 948, 288, 167, 102, 620, 309, 93, 114, 486, 899, 241, 58, 80, 680, 433, 310, 608, 705, 825, 221, 703, 589, 642, 91, 225, 405, 336, 695, 135, 744, 834, 273, 264, 320, 764, 475, 990, 229, 830, 820, 629, 41, 858, 664, 385, 86, 471, 295, 1000, 660, 132, 140, 372, 270, 380, 990, 567, 990, 501, 617, 767, 256, 198, 695, 230, 615, 392, 887, 201, 21, 215, 861, 134, 408, 906, 588, 507, 975, 351, 967, 955, 511, 645, 250, 906, 133, 610, 745, 796, 85, 738, 308, 254, 80, 243, 435, 870, 633, 929, 239, 162, 442, 803, 307, 593, 872, 590, 224, 494, 323, 376, 677, 90, 723, 328, 182, 669, 519, 49, 582, 175, 555, 711, 531, 349, 157, 484, 359, 502, 126, 60, 439, 978, 375, 889, 606, 224, 310, 214, 866, 543, 904, 979, 138, 921, 383, 939, 372, 142, 210, 754, 458, 34, 163, 925, 472, 505, 933, 93, 410, 691, 753, 734, 523, 400, 57, 3, 91, 150, 226, 618, 368, 721, 503, 55, 529, 224, 738, 288, 963, 392, 39, 594, 676, 406, 792, 105, 349, 580, 237, 787, 981, 404, 742, 618, 767, 494, 97, 814, 635, 676, 877, 210, 271, 611, 576, 52, 931, 590, 876, 228, 384, 774, 101, 594, 669, 54, 358, 861, 745, 530, 840, 827, 55, 531, 855, 83, 119, 498, 193, 445, 872, 843, 472, 201, 118, 484, 555, 405, 448, 296, 558, 334, 409, 506, 626, 138, 326, 214, 982, 412, 186, 283, 196, 578, 956, 448, 882, 993, 644, 2, 84, 348, 780, 921, 130, 504, 558, 791, 119, 830, 284, 595, 335, 64, 865, 492, 775, 890, 846, 453, 466, 778, 94, 350, 338, 169, 666, 464, 940, 796, 88, 617, 370, 520, 598, 820, 342, 730, 350, 205, 640, 619, 467, 682, 770, 726, 225, 297, 501, 146, 756, 311, 167, 198, 461, 800, 926, 364, 694, 316, 277, 301, 735, 893, 75, 65, 28, 419, 407, 633, 997, 23, 60, 932, 720, 198, 537, 9, 63, 898, 726, 502, 851, 917, 61, 655, 595, 45, 128, 429, 146, 662, 441, 738, 562, 290, 200, 416, 301, 359, 112, 994, 191, 979, 749, 991, 377, 657, 435, 267, 664, 72, 190, 105, 123, 473, 277, 987, 882, 323, 127, 986, 526, 105, 46, 563, 188, 925, 863, 819, 205, 227, 274, 980, 343, 60, 531, 225, 562, 69, 571, 947, 981, 444, 846, 663, 396, 70, 321, 428, 904, 524, 161, 734, 364, 367, 557, 989, 577, 755, 406, 848, 103, 850, 313, 772, 531, 992, 851, 204, 253, 846, 247, 767, 785, 225, 291, 981, 467, 67, 118, 207, 705, 38, 572, 133, 223, 145, 62, 212, 840, 939, 589, 670, 339, 714, 813, 509, 53, 11, 92, 6, 59, 247, 187, 958, 194, 239, 563, 659, 320, 772, 813, 878, 557, 909, 154, 166, 760, 767, 949, 482, 670, 390, 243, 837, 840, 918, 815, 993, 412, 896, 695, 945, 144, 76, 631, 125, 948, 30, 623, 777, 191, 677, 887, 630, 24, 193, 517, 800, 523, 235, 952, 602, 371, 883, 464, 158, 608, 691, 418, 135, 901, 590, 419, 340, 64, 532, 350, 625, 605, 922, 120, 774, 556, 468, 895, 218, 58, 725, 771, 133, 939, 260, 623, 120, 936, 387, 557, 226, 273, 548, 249, 587, 899, 602, 767, 342, 512, 706, 867, 556, 54, 139, 878, 157, 409, 471, 547, 525, 931, 584, 25, 269, 619, 124, 21, 190, 188, 943, 984, 572, 565, 183, 652, 554, 236, 845, 585, 567, 832, 388, 764, 331, 196, 750, 181, 925, 203, 271, 527, 714, 549, 566, 815, 856, 221, 891, 701, 240, 349, 357, 749, 63, 354, 300, 757, 783, 382, 3, 437, 568, 170, 878, 221, 196, 3, 1, 902, 599, 92, 839, 759, 701, 376, 448, 115, 509, 259, 835, 819, 818, 970, 826, 253, 827, 523, 488, 160, 477, 543, 417, 564, 757, 789, 625, 937, 307, 741, 540, 826, 361, 115, 761, 207, 80, 372, 385, 164, 509, 527, 811, 952, 666, 684, 41, 54, 698, 288, 286, 848, 796, 956, 153, 189, 333, 266, 489, 481, 940, 785, 531, 977, 79, 752, 121, 184, 223, 373, 65, 497, 233, 766, 547, 410, 521, 368, 858, 234, 367, 169, 848, 839, 580, 37, 940, 652, 45, 611, 521, 111, 763, 680, 563, 367, 556, 949, 943, 920, 846, 538, 959, 815, 902, 293, 608, 234, 887, 713, 501, 199, 467, 297, 553, 286, 822, 769, 18, 923, 399, 591, 851, 216, 291, 251, 763, 470, 943, 681, 929, 983, 28, 609, 80, 689, 820, 924, 290, 934, 224, 129, 926, 558, 681, 555, 801, 237, 782, 974, 612, 593, 488, 317, 639, 536, 636, 17, 961, 685, 964, 644, 916, 309, 936, 907, 26, 236, 544, 340, 956, 998, 538, 654, 323, 926, 806, 17, 380, 368, 777, 576, 973, 972, 625, 233, 196, 767, 453, 504, 393, 491, 7, 641, 79, 974, 23, 423, 831, 742, 155, 520, 290, 962, 397, 776, 906, 469, 155, 401, 238, 584, 117, 875, 461, 261, 472, 841, 857, 718, 129, 817, 812, 801, 67, 543, 156, 595, 639, 484, 177, 913, 84, 973, 702, 598, 784, 969, 373, 747, 62, 144, 423, 251, 849, 972, 648, 22, 688, 965, 665, 212, 327, 594, 271, 34, 882, 918, 949, 722, 423, 78, 228, 710, 11, 783, 193, 521, 244, 702, 819, 457, 252, 467, 345, 686, 241, 362, 938, 425, 996, 347, 474, 784, 263, 280, 640, 628, 126, 852, 849, 990, 210, 212, 298, 336, 765, 738, 184, 378, 843, 880, 516, 514, 349, 221, 511, 642, 397, 577, 4, 2, 141, 8, 265, 220, 866, 964, 98, 429, 635, 78, 481, 969, 614, 630, 425, 446, 484, 677, 678, 752, 942, 207, 87, 785, 907, 136, 169, 683, 723, 455, 829, 564, 300, 943, 36, 126, 889, 246, 981, 140, 264, 103, 470, 793, 158, 754, 701, 589, 805, 590, 27, 978, 175, 161, 595, 171, 259, 856, 720, 937, 62, 738, 846, 539, 616, 118, 494, 778, 419, 695, 844, 983, 575, 201, 394, 858, 859, 331, 601, 834, 827, 165, 182, 647, 23, 503, 51, 524, 840, 132, 219, 213, 865, 205, 925, 912, 71, 766, 558, 968, 344, 219, 926, 781, 581, 471, 725, 302, 789, 973, 770, 543, 457, 32, 915, 607, 501, 197, 461, 306, 573, 68, 404, 301, 319, 26, 424, 175, 486, 223, 584, 335, 502, 856, 465, 129, 786, 235, 95, 435, 686, 215, 140, 317, 372, 646, 611, 567, 584, 184, 740, 859, 236, 449, 463, 488, 244, 658, 607, 98, 548, 222, 394, 241, 83, 301, 248, 937, 206, 631, 995, 942, 867, 725, 95, 164, 887, 39, 741, 687, 799, 629, 85, 222, 5, 286, 575, 263, 1, 625, 633, 562, 999, 350, 105, 342, 123, 696, 994, 947, 406, 156, 908, 205, 540, 315, 369, 401, 791, 953, 884, 233, 427, 57, 418, 762, 729, 28, 170, 763, 375, 899, 161, 912, 660, 563, 129, 584, 881, 127, 349, 890, 588, 240, 631, 432, 694, 835, 279, 747, 524, 671, 798, 58, 368, 139, 283, 792, 759, 279, 576, 739, 146, 12, 538, 539, 438, 400, 279, 58, 605, 567, 109, 386, 769, 438, 846, 747, 336, 347, 11, 813, 931, 367, 708, 351, 567, 981, 465, 466, 464, 706, 600, 667, 729, 513, 43, 58, 536, 14, 140, 488, 575, 182, 573, 137, 65, 716, 991, 491, 905, 591, 414, 900, 650, 218, 759, 689, 499, 123, 338, 585, 178, 580, 487, 314, 159, 560, 717, 784, 247, 373, 34, 159, 630, 503, 166, 939, 730, 429, 622, 132, 852, 195, 283, 263, 731, 682, 444, 38, 746, 846, 1000, 59, 658, 332, 56, 18, 24, 782, 191, 459, 277, 296, 716, 386, 927, 62, 615, 992, 821, 592, 614, 840, 658, 813, 652, 243, 906, 239, 545, 657, 965, 41, 450, 107, 43, 602, 690, 585, 273, 845, 973, 863, 734, 886, 217, 446, 418, 108, 212, 997, 435, 402, 864, 97, 925, 398, 939, 916, 79, 530, 480, 549, 365, 872, 804, 219, 275, 927, 435, 599, 519, 958, 614, 34, 215, 630, 498, 38, 875, 826, 950, 45, 76, 667, 251, 479, 347, 698, 926, 898, 98, 909, 441, 401, 95, 887, 955, 588, 94, 278, 360, 1000, 485, 442, 638, 171, 318, 420, 192, 652, 114, 294, 600, 619, 570, 680, 503, 500, 148, 456, 635, 547, 592, 84, 355, 791, 502, 599, 397, 313, 50, 161, 203, 85, 119, 317, 143, 424, 414, 437, 768, 835, 470, 93, 466, 385, 817, 513, 204, 5, 491, 859, 306, 422, 877, 319, 902, 204, 10, 469, 712, 809, 346, 187, 631, 930, 862, 299, 801, 995, 287, 627, 301, 322, 402, 418, 818, 909, 567, 599, 255, 330, 337, 598, 568, 796, 537, 776, 925, 717, 286, 207, 979, 172, 238, 19, 504, 962, 423, 457, 509, 838, 357, 966, 436, 528, 352, 853, 264, 522, 117, 874, 554, 644, 452, 338, 579, 705, 868, 815, 475, 268, 193, 485, 484, 913, 66, 76, 934, 554, 741, 210, 282, 119, 708, 321, 954, 326, 180, 188, 763, 325, 745, 861, 710, 612, 175, 263, 599, 657, 76, 197, 794, 341, 40, 444, 84, 198, 290, 91, 904, 576, 44, 579, 679, 250, 432, 808, 419, 199, 447, 912, 690, 404, 714, 151, 99, 304, 33, 285, 277, 733, 834, 418, 203, 837, 980, 286, 262, 989, 363, 823, 757, 592, 92, 260, 285, 664, 36, 289, 51, 885, 788, 676, 762, 187, 418, 171, 644, 6, 82, 718, 57, 34, 483, 884, 177, 227, 75, 947, 645, 771, 34, 946, 804, 244, 289, 795, 30, 189, 262, 405, 863, 930, 164, 892, 11, 721, 769, 16, 819, 537, 145, 696, 794, 681, 687, 624, 110, 32, 467, 918, 934, 572, 21, 342, 907, 378, 460, 670, 575, 849, 845, 747, 160, 113, 89, 576, 745, 8, 737, 818, 801, 828, 952, 888, 89, 939, 515, 663, 630, 451, 124, 394, 269, 548, 807, 408, 272, 229, 896, 681, 813, 764, 848, 392, 642, 365, 649, 279, 223, 311, 962, 458, 721, 61, 814, 440, 761, 426, 925, 770, 283, 567, 102, 407, 700, 610, 638, 776, 330, 39, 902, 915, 373, 427, 642, 716, 388, 157, 558, 713, 684, 253, 824, 193, 375, 133, 740, 336, 612, 742, 886, 767, 23, 462, 711, 996, 613, 26, 428, 537, 143, 13, 334, 339, 376, 230, 961, 984, 572, 509, 580, 32, 374, 151, 807, 246, 826, 931, 993, 359, 920, 415, 140, 622, 388, 242, 829, 226, 719, 744, 461, 855, 83, 352, 540, 402, 982, 550, 66, 51, 110, 161, 129, 981, 811, 121, 292, 786, 788, 515, 636, 52, 53, 837, 308, 389, 674, 556, 131, 468, 943, 800, 889, 229, 684, 270, 157, 563, 289, 405, 895, 417, 474, 587, 1000, 468, 426, 812, 105, 254, 563, 678, 46, 731, 602, 493, 885, 250, 640, 991, 416, 606, 332, 919, 465, 8, 825, 263, 926, 427, 653, 987, 672, 414, 716, 34, 517, 167, 562, 908, 921, 424, 414, 422, 879, 885, 418, 826, 652, 461, 607, 650, 128, 157, 100, 362, 762, 457, 586, 502, 717, 677, 822, 389, 277, 285, 880, 502, 930, 309, 81, 751, 961, 543, 62, 912, 681, 683, 474, 309, 764, 664, 504, 543, 156, 111, 29, 289, 613, 540, 209, 822, 322, 607, 736, 773, 122, 339, 632, 813, 921, 993, 6, 777, 795, 847, 918, 961, 850, 995, 9, 487, 512, 56, 200, 19, 427, 342, 337, 646, 802, 532, 568, 846, 292, 835, 930, 832, 240, 309, 294, 159, 430, 174, 42, 566, 914, 663, 479, 819, 175, 654, 438, 732, 215, 390, 842, 916, 250, 764, 617, 94, 439, 173, 493, 275, 142, 799, 519, 572, 102, 832, 470, 868, 237, 138, 261, 511, 252, 328, 267, 651, 191, 783, 460, 854, 664, 523, 432, 336, 715, 671, 117, 655, 728, 564, 249, 604, 889, 333, 297, 549, 628, 800, 237, 384, 395, 415, 181, 98, 540, 299, 104, 622, 265, 118, 331, 506, 401, 21, 21, 67, 600, 408, 529, 501, 636, 990, 178, 965, 911, 367, 701, 758, 869, 225, 926, 10, 813, 780, 192, 373, 71, 222, 291, 185, 78, 713, 429, 95, 906, 129, 779, 714, 53, 465, 764, 295, 569, 178, 709, 49, 347, 371, 1, 587, 191, 22, 838, 233, 711, 256, 864, 986, 235, 287, 180, 502, 101, 837, 242, 960, 704, 240, 544, 275, 264, 998, 409, 401, 506, 941, 910, 854, 789, 514, 189, 323, 924, 876, 857, 479, 721, 391, 487, 125, 732, 975, 692, 313, 187, 992, 833, 496, 233, 220, 43, 62, 282, 328, 466, 943, 323, 294, 106, 107, 382, 143, 151, 875, 241, 8, 547, 301, 937, 501, 879, 6, 893, 295, 161, 209, 591, 796, 26, 878, 940, 926, 816, 646, 509, 876, 718, 82, 122, 814, 584, 89, 856, 884, 798, 141, 611, 107, 593, 858, 705, 75, 360, 249, 592, 974, 537, 904, 121, 426, 259, 998, 372, 369, 980, 193, 399, 733, 859, 679, 265, 915, 184, 764, 477, 224, 463, 976, 729, 536, 818, 504, 68, 749, 516, 841, 762, 740, 758, 615, 209, 932, 715, 671, 499, 771, 404, 17, 443, 712, 452, 601, 206, 132, 330, 60, 762, 383, 902, 868, 594, 998, 435, 797, 110, 397, 505, 837, 827, 872, 437, 19, 321, 299, 891, 889, 788, 941, 167, 748, 328, 62, 669, 873, 548, 556, 181, 27, 255, 68, 260, 686, 362, 517, 191, 612, 346, 590, 720, 717, 80, 460, 148, 171, 148, 620, 465, 592, 76, 91, 289, 874, 63, 607, 391, 212, 910, 405, 573, 474, 205, 466, 698, 773, 230, 763, 898, 495, 241, 869, 935, 560, 911, 381, 476, 929, 81, 327, 751, 23, 270, 118, 448, 291, 347, 639, 978, 208, 229, 307, 652, 746, 671, 483, 519, 72, 561, 174, 471, 50, 940, 356, 675, 669, 992, 300, 942, 766, 717, 691, 556, 49, 636, 619, 495, 386, 740, 452, 326, 938, 281, 991, 326, 536, 309, 22, 556, 133, 338, 128, 337, 238, 129, 40, 406, 960, 95, 704, 792, 694, 314, 50, 184, 379, 931, 289, 575, 512, 259, 740, 975, 970, 700, 399, 237, 681, 353, 904, 66, 432, 578, 846, 985, 692, 154, 26, 495, 386, 780, 622, 168, 98, 390, 561, 197, 57, 977, 713, 877, 45, 172, 396, 508, 405, 799, 112, 937, 652, 295, 560, 804, 815, 31, 570, 149, 842, 167, 103, 193, 655, 21, 312, 495, 158, 186, 92, 763, 559, 109, 364, 804, 708, 936, 475, 667, 98, 780, 842, 452, 310, 324, 921, 517, 80, 49, 33, 441, 981, 383, 251, 876, 632, 37, 988, 549, 45, 286, 943, 599, 16, 939, 582, 558, 193, 345, 904, 707, 381, 824, 917, 94, 941, 254, 908, 11, 487, 406, 84, 290, 442, 646, 469, 876, 277, 727, 45, 334, 225, 290, 858, 386, 892, 953, 130, 913, 887, 641, 760, 731, 913, 57, 320, 893, 688, 407, 517, 368, 163, 877, 96, 806, 722, 399, 718, 921, 347, 125, 67, 819, 852, 825, 300, 792, 317, 866, 962, 874, 736, 809, 208, 28, 613, 987, 149, 218, 266, 804, 287, 868, 435, 824, 789, 679, 760, 450, 648, 947, 214, 540, 356, 391, 566, 877, 996, 736, 339, 892, 939, 3, 847, 534, 974, 713, 71, 601, 157, 267, 711, 37, 750, 82, 808, 574, 356, 182, 531, 537, 536, 311, 368, 193, 904, 346, 405, 649, 2, 506, 656, 978, 121, 458, 231, 519, 930, 729, 386, 651, 760, 832, 861, 204, 398, 850, 581, 827, 802, 182, 588, 370, 824, 199, 599, 208, 49, 640, 55, 321, 311, 539, 22, 957, 654, 241, 617, 290, 922, 887, 341, 502, 646, 56, 673, 166, 339, 380, 89, 313, 987, 56, 579, 150, 5, 273, 114, 913, 182, 43, 830, 123, 886, 237, 304, 442, 932, 631, 871, 32, 632, 918, 154, 159, 57, 660, 440, 358, 111, 71, 88, 884, 428, 478, 212, 963, 342, 943, 406, 976, 214, 807, 422, 752, 560, 67, 91, 411, 833, 463, 564, 948, 546, 835, 51, 753, 872, 383, 493, 965, 398, 658, 797, 513, 411, 23, 196, 31, 755, 386, 363, 563, 541, 275, 989, 762, 652, 16, 900, 543, 558, 208, 371, 57, 226, 341, 419, 865, 972, 836, 523, 397, 583, 528, 159, 28, 459, 704, 559, 111, 212, 378, 476, 366, 283, 664, 796, 807, 793, 689, 968, 762, 670, 454, 346, 744, 470, 131, 654, 695, 152, 521, 84, 464, 291, 303, 831, 489, 923, 186, 672, 407, 285, 403, 547, 706, 604, 728, 186, 463, 918, 238, 873, 576, 268, 264, 222, 223, 907, 388, 534, 193, 551, 182, 271, 233, 943, 461, 407, 51, 170, 520, 936, 335, 624, 778, 826, 890, 738, 10, 833, 240, 4, 628, 235, 812, 832, 998, 953, 153, 633, 851, 877, 988, 545, 117, 279, 227, 541, 898, 951, 856, 48, 794, 627, 788, 681, 201, 445, 78, 501, 10, 217, 23, 428, 745, 595, 729, 138, 693, 778, 718, 391, 824, 75, 987, 558, 387, 12, 543, 304, 933, 281, 374, 94, 430, 919, 372, 341, 857, 486, 564, 680, 638, 553, 78, 200, 288, 769, 477, 267, 48, 415, 994, 164, 926, 763, 227, 598, 779, 998, 389, 651, 633, 104, 362, 591, 762, 653, 851, 544, 872, 29, 133, 642, 635, 266, 261, 796, 653, 407, 15, 592, 443, 439, 639, 610, 779, 550, 398, 199, 79, 236, 155, 149, 554, 320, 764, 170, 160, 423, 4, 720, 993, 26, 145, 484, 958, 680, 466, 490, 106, 540, 166, 401, 586, 925, 317, 530, 48, 699, 496, 978, 732, 433, 230, 346, 816, 579, 78, 333, 458, 955, 907, 126, 144, 83, 458, 850, 690, 723, 280, 520, 119, 111, 460, 399, 353, 801, 878, 670, 316, 522, 780, 326, 215, 337, 513, 580, 864, 152, 655, 404, 730, 950, 33, 461, 372, 821, 261, 481, 664, 727, 108, 380, 335, 703, 450, 587, 78, 402, 705, 178, 140, 471, 115, 611, 18, 291, 223, 65, 549, 253, 722, 741, 423, 432, 554, 190, 622, 282, 470, 330, 382, 71, 739, 609, 346, 83, 125, 560, 408, 714, 171, 25, 983, 438, 237, 102, 119, 918, 638, 509, 767, 765, 519, 750, 117, 61, 505, 489, 916, 440, 952, 524, 881, 387, 133, 108, 23, 447, 573, 189, 43, 932, 505, 754, 820, 465, 917, 578, 156, 556, 150, 875, 911, 693, 43, 16, 727, 364, 465, 667, 114, 378, 54, 534, 344, 152, 661, 14, 266, 301, 24, 894, 749, 288, 286, 27, 711, 914, 577, 51, 341, 122, 541, 156, 964, 786, 199, 205, 970, 436, 226, 921, 736, 881, 18, 326, 631, 265, 125, 842, 437, 971, 332, 997, 172, 680, 486, 831, 348, 908, 163, 993, 408, 556, 394, 371, 505, 561, 85, 189, 587, 506, 641, 203, 375, 35, 148, 378, 402, 865, 815, 583, 51, 618, 63, 860, 991, 939, 829, 286, 432, 358, 9, 997, 885, 928, 535, 56, 869, 813, 809, 177, 184, 876, 516, 742, 567, 325, 415, 313, 26, 326, 610, 370, 779, 740, 955, 103, 11, 16, 254, 980, 774, 188, 64, 33, 891, 72, 319, 608, 122, 226, 904, 93, 367, 9, 168, 605, 104, 973, 288, 661, 257, 82, 77, 589, 932, 481, 668, 857, 839, 465, 67, 597, 38, 572, 192, 98, 235, 461, 59, 582, 410, 199, 184, 392, 309, 651, 214, 30, 285, 787, 674, 221, 377, 752, 865, 255, 137, 693, 479, 178, 209, 35, 943, 803, 745, 378, 337, 848, 59, 88, 864, 881, 473, 556, 162, 349, 730, 170, 162, 778, 211, 493, 470, 639, 892, 845, 547, 751, 267, 353, 341, 413, 243, 131, 117, 32, 696, 852, 524, 163, 159, 872, 752, 599, 176, 564, 952, 302, 33, 755, 65, 805, 473, 173, 3, 779, 806, 711, 524, 944, 655, 722, 931, 7, 861, 356, 103, 94, 60, 976, 688, 799, 411, 800, 128, 517, 893, 327, 266, 149, 124, 175, 261, 793, 718, 660, 919, 987, 718, 778, 760, 383, 580, 617, 496, 655, 696, 727, 702, 484, 963, 506, 742, 178, 704, 502, 347, 73, 598, 589, 863, 979, 943, 693, 763, 953, 355, 988, 135, 984, 217, 815, 638, 391, 694, 245, 685, 406, 773, 322, 781, 328, 890, 484, 626, 349, 555, 822, 961, 771, 58, 598, 982, 812, 58, 341, 47, 287, 321, 583, 129, 741, 704, 977, 100, 659, 917, 341, 768, 792, 151, 591, 971, 359, 721, 624, 221, 135, 993, 937, 900, 120, 447, 586, 980, 119, 844, 555, 251, 680, 37, 258, 579, 924, 492, 471, 965, 959, 751, 704, 89, 140, 508, 597, 344, 755, 842, 16, 761, 434, 816, 173, 60, 904, 746, 160, 703, 897, 624, 647, 833, 625, 761, 250, 414, 518, 597, 347, 495, 736, 105, 79, 987, 485, 556, 190, 996, 674, 178, 564, 853, 717, 51, 627, 772, 224, 992 };

int target = 120331635;

int result = s.minSubArrayLen(target, case0);

Assert::AreEqual(2327, result);

}

{

public:

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}

};

class Solution {

public:

vector<TreeNode*> next(const vector<TreeNode*> & nodes)

{

vector<TreeNode*> result;

result.reserve(nodes.size() * 2);

for (auto n : nodes)

{

if (n->left)

result.push_back(n->left);

if (n->right)

result.push_back(n->right);

}

return std::move(result);

}

vector<int> rightSideView(TreeNode* root) {

vector<int> result;

if (root)

{

vector<TreeNode*> layer{ root };

while (!layer.empty())

{

result.push_back(layer.back()->val);

layer = next(layer);

}

/*for (vector<TreeNode*> layer{ root }; !layer.empty(); layer = next(layer))

}

return result;

}

};

TEST_METHOD(test0)

{

Solution s;

auto * root = new TreeNode{ 1,

new TreeNode{ 2, nullptr, new TreeNode{5} },

new TreeNode{ 3, nullptr, new TreeNode{4} }

};

auto & result = s.rightSideView(root);

vector<int> expected = { 1, 3, 4 };

for (size_t i = 0; i < 3; i++)

{

Assert::AreEqual(expected[i], result[i]);

}

}

{

public:

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}

};

class Solution {

public:

vector<int> rightSideView(TreeNode* root) {

vector<int> result;

if (root)

{

vector<TreeNode*> nodes{ root };

int beg = 0, end;

do{

result.push_back(nodes.back()->val);

for (end = nodes.size(); beg != end; ++beg)

{

auto n = nodes[beg];

if (n->left)

nodes.push_back(n->left);

if (n->right)

nodes.push_back(n->right);

}

} while (beg != nodes.size());

}

return result;

}

};

TEST_METHOD(test0)

{

Solution s;

auto * root = new TreeNode{ 1,

new TreeNode{ 2, nullptr, new TreeNode{ 5 } },

new TreeNode{ 3, nullptr, new TreeNode{ 4 } }

};

auto & result = s.rightSideView(root);

vector<int> expected = { 1, 3, 4 };

for (size_t i = 0; i < 3; i++)

{

Assert::AreEqual(expected[i], result[i]);

}

}

{

public:

struct ListNode {

const int val;

ListNode *next;

ListNode(const int x) : val(x), next(NULL) {}

ListNode(const int x, ListNode *next) : val(x), next(next) {}

};

class Solution {

public:

inline ListNode* nextNode(ListNode* left)

{

if (left)

{

auto * right = left->next;

return right ? right : left;

}

else

return nullptr;

}

inline ListNode* swap(ListNode* left)

{

if (auto * right = left->next)

{

auto * nn = right->next;

auto * nx = nextNode(nn);

right->next = left;

left->next = nx;