爱生气的书店老板
力扣 1052. 爱生气的书店老板
题目说明
今天，书店老板有一家店打算试营业customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
- 1 <= X <= customers.length == grumpy.length <= 20000
- 0 <= customers[i] <= 1000
- 0 <= grumpy[i] <= 1
示例
例1
1 | 输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 |
例2
1 | 输入：customers =[66,514,364,657,627,645,208,599,803,501,297,839,253,877,1000,636,928,415,583,639,832,170,94,492,29,102,702,965,56,300,53,535,725,249,615,919,667,841,358,567,257,95,714,224,4,772,263,761,413,743,165,519,535,476,32,690,687,483,77,125,651,455,664,891,709,738,684,865,263,157,476,343,538,768,743,53,680,171,204,69,936,297,252,410,924,533,205,883,757,419,147,281,393,400,431,629,994,715,533,836,352,167,413,805,719,708,431,844,994,652,663,528,774,228,44,506,628,927,533,1,699,880,280,277,26,46,239,482,601,585,357,103,791,840,916,935,334,53,16,219,131,902,462,423,972,74,428,377,396,545,404,527,713,605,663,953,558,752,869,258,242,163,444,812,793,289,178,557,606,712,181,687,245,325,350,486,466,624,918,274,21,560,432,339,577,538,53,24,277,901,82,425,498,511,709,391,780,870,799,316,658,718,765,497,91,587,156,993,999,345,163,200,346,840,909,119,335,882,945,677,931,254,595,528,903,876,424,233,66,379,31,535,943,241,708,335,522,882,697,579,130,36,810,695,933,515,205,444,840,121,212,762,963,624,914,126,30,206,72,934,913,212,245,477,185,319,290,449,85,589,361,481,13,430,698,22,558,565,401,53,112,639,846,49,443,192,131,323,594,487,311,517,211,238,733,725,409,868,192,463,278,91,299,96,952,903,305,860,857,934,818,515,391,334,708,97,100,732,444,180,15,866,625,598,775,260,758,485,707,111,404,272,128,649,686,773,101,325,383,558,34,290,305,565,84,893,816,118,817,319,488,464,488,228,603,16,324,291,279,238,11,745,667,341,6,35,291,974,397,23,516,577,370,588,729,150,214,481,738,813,870,42,956,276,840,641,946,876,577,879,118,936,318,631,707,633,265,107,364,53,161,700,407,293,399,783,738,508,362,39,940,327,467,339,627,671,602,887,604,162,792,740,757,305,112,204,974,460,530,912,787,387,798,321,209,839,109,463,518,201,86,404,239,75,816,851,230,140,462,462,985,454,104,372,864,387,303,596,275,10,500,751,522,211,29,261,885,365,582,514,599,836,72,749,799,198,812,272,99,874,355,327,395,96,885,77,149,800,697,903,62,117,740,957,651,156,600,84,731,193,572,110,924,735,21,267,163,986,10,639,236,808,419,86,96,955,286,398,187,654,682,260,942,860,51,891,131,279,252,84,788,348,323,367,27,585,187,930,610,51,837,635,830,107,82,883,763,26,899,602,455,934,494,865,944,673,665,961,509,562,294,679,852,510,288,934,378,705,446,22,521,532,354,70,759,123,101,908,781,978,457,818,602,599,191,704,789,962,279,946,738,976,960,196,796,776,396,969,339,88,666,181,872,699,85,5,289,591,311,920,463,764,197,840,505,80,432,460,504,136,438,86,902,949,171,419,628,274,672,627,809,671,491,48,913,49,164,987,992,525,513,973,12,453,911,137,221,919,233,580,1000,836,227,453,664,801,418,831,531,190,306,486,416,730,953,51,776,83,742,425,674,271,525,889,958,24,159,392,534,367,389,87,613,915,549,763,767,814,134,235,838,437,106,8,857,95,985,790,332,938,252,53,30,665,518,20,341,170,324,711,223,344,668,981,954,611,510,781,784,450,852,648,134,678,98,503,607,35,491,950,901,948,280,245,953,709,889,886,616,761,181,37,983,352,168,118,750,599,28,664,694,785,977,488,582,730,317,99,105,880,484,144,841,569,466,925,409,390,784,266,105,117,310,408,601,425,796,257,311,921,205,917,911,646,740,943,691,331,69,184,987,726,990,120,722,248,322,771,827,195,210,859,173,864,416,853,571,306,365,650,145,678,321,820,701,852,57,176,712,438,434,707,705,75,266,770,931,711,480,422,712,76,741,61,967,618,854,476,874,610,134,198,357,49,547,229,291,174,268,933,2,883,678,179,985,950,272,106,600,264,972,296,450,224,235,22,356,851,842,423,523,597,222,680,773,57,703,251,605,702,296,652,770,892,930,999,216,440,575,331,989,70,569,859,394,705,462,895,101,983,401,886,676,678,76,404,10,699,867,389,591,105,669,612,592,258,452,208,640,432,87,711,159,573,374,913,661,454,542,658,257,200,873,374,737,590,979,545,962,430,400,625,809,473,84,819,718,129,540,32,485,503,801,111,335,983,564,736,994,681,702,126,251,366,504,223,859,960,133,237,390,789,518,309,181,579,221,443,597,343,421,572,998,185,948,994,272,138,957,584,380,451,179,242,595,917,316,41,320,714,706,443,829,668,68,806,950,680,242,404,655,209,28,434,534,418,680,298,825,730,213,198,589,734,110,715,547,423,828,958,63,85,918,833,664,96,190,21,503,535,91,301,303,228,457,805,640,874,87,53,924,810,360,712,93,688,801,393,266,764,729,790,848,988,824,58,499,202,960,958,442,552,629,18,365,258,200,335,698,921,63,833,949,948,980,800,517,777,891,36,123,791,222,44,82,372,914,956,266,221,280,905,170,607,380,494,336,768,716,122,477,931,223,994,137,775,286,705,841,666,931,339,897,516,271,340,833,482,649,845,728,941,864,245,153,174,271,38,549,922,865,908,363,434,150,675,803,760,41,787,736,372,859,514,130,756,435,475,822,983,262,805,433,605,567,841,765,458,599,867,401,185,88,505,764,577,297,207,348,448,109,127,744,239,788,379,213,39,15,477,834,331,85,452,592,737,47,508,817,594,772,709,465,166,694,673,584,425,582,674,354,549,836,373,436,331,662,860,72,86,956,877,603,869,667,136,129,480,978,285,583,860,649,699,754,609,38,742,211,314,643,855,995,306,80,332,998,336,709,726,660,618,854,115,349,551,896,946,507,545,367,636,531,615,677,359,260,923,670,642,15,466,946,150,275,45,944,298,833,582,616,442,404,682,277,268,592,37,865,879,222,633,878,358,594,884,705,420,62,952,528,838,16,562,145,808,953,264,355,846,887,63,989,327,92,124,43,516,35,581,617,184,298,420,685,437,365,721,140,658,555,507,413,208,687,777,927,445,940,916,380,127,696,300,207,794,739,842,179,646,851,360,942,220,210,254,187,756,387,488,419,864,631,125,235,693,710,997,265,347,755,830,827,604,980,315,295,200,674,9,297,510,836,253,792,163,62,167,770,137,487,914,354,406,257,514,776,951,887,362,576,498,929,808,914,236,870,494,831,839,509,459,501,486,39,461,451,196,816,648,160,394,838,396,500,831,912,26,380,550,170,340,51,863,70,108,113,505,346,224,803,478,68,148,435,51,406,454,284,733,147,450,935,362,996,296,439,820,918,749,254,362,231,52,311,795,19,689,709,365,4,112,398,350,294,906,60,776,522,944,226,225,546,667,329,442,794,634,358,10,1000,828,506,809,301,169,654,242,963,688,831,144,196,589,288,392,876,156,17,478,871,44,272,650,198,321,736,369,855,973,522,306,339,684,783,110,339,105,835,34,655,752,77,402,327,772,161,439,66,650,821,645,187,113,611,246,382,232,833,492,546,904,743,36,399,84,916,434,606,930,600,201,215,678,889,671,46,877,583,438,530,933,167,965,877,64,964,96,21,187,899,970,881,504,955,835,663,553,186,446,119,124,620,392,44,115,920,909,745,299,515,194,17,967,310,933,248,275,950,782,617,16,359,810,56,150,878,416,373,268,749,894,384,900,748,939,659,905,1,781,164,278,142,527,72,520,414,558,194,242,79,979,571,870,188,111,70,94,741,83,389,640,76,872,359,743,598,547,7,270,432,952,155,109,223,581,906,50,732,122,774,226,999,277,476,202,814,314,128,632,879,786,326,254,689,369,976,406,769,381,801,818,52,942,175,243,485,333,9,188,248,123,641,615,186,885,504,822,761,78,65,980,198,596,604,174,53,149,331,896,716,720,341,796,200,766,845,427,246,629,368,271,845,224,635,469,470,452,128,158,205,373,791,287,589,839,778,582,487,310,685,377,683,53,870,622,750,931,783,298,479,686,491,586,315,635,511,940,55,728,701,737,254,422,310,832,836,491,266,32,476,713,322,906,535,926,57,610,788,927,238,736,530,235,446,523,308,125,77,809,452,214,88,370,650,760,182,375,136,172,342,39,804,750,384,593,310,789,35,181,358,199,456,585,360,130,977,827,847,867,266,443,14,497,644,419,351,438,901,985,294,526,208,414,768,354,620,685,675,695,333,453,899,214,206,34,763,132,987,445,2,456,687,185,10,35,822,602,644,819,735,669,164,353,221,525,75,260,321,937,959,443,386,998,34,652,734,820,832,277,641,791,598,341,566,853,44,834,997,741,756,531,150,778,512,49,258,546,176,56,250,563,756,809,522,992,689,651,982,607,862,487,423,73,902,928,627,615,874,261,588,151,188,744,777,575,709,686,403,956,613,836,286,262,392,659,232,653,538,568,871,420,799,257,231,754,451,831,945,718,113,917,819,178,164,841,430,381,290,513,333,597,273,859,246,857,486,760,234,791,545,85,206,179,838,103,683,627,953,176,74,192,774,35,986,137,436,115,842,4,14,842,789,199,363,988,4,96,737,735,743,619,721,62,425,254,882,576,800,120,417,903,620,841,224,255,826,75,250,631,787,626,102,563,920,726,440,860,867,334,384,318,79,988,862,42,379,949,223,218,460,972,848,793,417,714,669,379,279,850,401,920,140,83,419,634,679,849,844,446,705,781,517,712,585,618,124,111,956,544,112,34,878,477,711,865,485,409,862,615,705,243,531,443,440,157,121,864,19,799,577,356,802,220,859,719,71,263,664,551,383,605,476,752,162,292,601,973,784,139,492,590,55,761,465,448,166,948,178,998,270,94,484,85,561,384,421,865,90,283,243,341,121,944,119,550,569,59,959,14,494,213,317,573,335,127,613,625,930,842,905,464,47,628,858,517,404,653,982,690,133,869,745,956,671,221,667,216,225,589,59,234,965,942,945,769,342,966,908,21,642,96,113,809,975,201,179,228,693,931,640,815,203,949,773,892,555,481,475,279,387,218,257,405,458,18,702,49,557,550,776,272,867,978,882,352,805,471,567,893,720,633,622,459,72,868,57,487,179,486,50,845,79,711,876,385,370,746,547,519,151,173,595,396,558,350,435,364,287,104,660,830,311,564,417,172,984,477,128,443,733,839,798,78,49,278,658,78,325,584,663,636,584,130,177,798,910,939,710,462,865,541,381,526,979,125,116,33,178,49,637,597,657,919,57,72,924,598,195,757,133,518,489,906,146,880,121,967,682,713,792,187,213,279,207,682,65,739,176,802,893,377,306,752,42,572,268,308,515,485,262,855,162,596,723,428,267,801,904,5,34,712,592,167,875,36,799,912,920,89,804,500,708,785,44,297,13,626,482,235,330,466,62,362,354,393,423,609,826,648,328,710,579,78,851,130,6,304,137,963,201,820,52,411,226,923,206,617,332,618,17,808,689,539,299,297,701,392,160,497,706,273,770,899,821,780,502,711,844,593,851,504,379,776,269,897,532,633,971,969,74,424,287,213,403,803,313,828,121,991,828,28,617,71,643,671,242,536,829,705,927,835,186,197,851,410,148,815,244,228,536,934,508,522,927,250,126,902,385,497,107,632,643,555,505,413,842,526,995,465,604,837,298,2,469,357,999,850,664,402,940,218,854,530,899,258,787,544,296,922,623,495,922,903,12,345,274,607,606,514,568,531,188,608,150,192,284,662,528,120,772,363,456,727,758,167,291,679,857,310,285,326,29,897,228,366,968,9,910,277,687,576,529,159,510,289,880,190,831,842,424,85,735,584,54,319,343,841,889,447,205,510,194,225,559,799,916,668,893,504,489,435,606,685,100,351,104,539,276,10,91,958,877,609,993,832,42,10,239,146,621,372,89,4,687,289,625,887,493,256,146,317,43,600,410,613,524,24,894,758,480,259,467,958,295,250,731,138,815,827,603,233,951,708,795,785,666,531,929,4,600,601,444,10,872,851,970,471,594,299,346,970,346,516,593,814,462,296,972,503,466,16,209,104,913,519,623,878,3,995,773,221,402,743,42,344,751,942,484,783,390,331,221,216,50,592,940,873,534,893,202,996,77,840,843,669,945,776,767,893,617,903,614,671,88,35,971,913,889,704,965,180,681,1,335,298,328,436,228,171,725,7,634,887,120,847,539,48,42,94,992,212,390,935,419,612,537,689,52,112,611,73,123,110,90,209,198,530,411,359,875,724,35,18,358,665,268,440,618,341,505,835,565,735,240,644,808,252,658,96,192,79,662,825,378,518,577,137,687,263,135,804,587,369,57,800,25,382,867,295,932,177,2,263,817,543,688,634,599,190,151,1000,473,771,4,59,531,912,966,754,155,924,708,441,791,997,537,757,686,929,305,800,371,277,110,5,724,153,206,759,147,836,507,129,682,879,548,512,169,17,487,152,358,23,27,603,888,234,702,526,564,679,427,149,930,711,651,621,382,820,134,541,995,498,545,462,575,288,391,988,495,462,96,601,290,729,88,209,826,383,246,106,144,18,92,937,835,490,753,375,805,490,718,706,962,412,90,519,60,44,35,272,400,744,699,948,727,145,847,834,194,634,849,778,418,263,828,397,741,262,721,98,715,833,981,128,190,442,296,165,752,208,812,993,666,931,778,123,399,286,149,572,109,429,387,286,855,739,783,163,118,564,98,644,229,900,505,521,394,241,276,53,802,282,794,259,729,734,691,336,781,348,673,214,207,720,622,879,856,544,643,759,348,691,611,910,29,951,376,326,415,349,66,381,717,89,368,308,502,362,97,439,36,104,548,135,822,834,993,31,62,507,881,794,447,627,564,917,16,814,71,841,44,772,933,856,923,283,836,770,406,349,903,304,949,768,161,849,298,357,387,927,536,300,844,192,217,573,50,667,718,210,842,692,945,921,818,616,832,552,893,491,702,308,885,274,11,189,2,546,67,141,648,675,587,752,474,66,64,483,862,781,371,745,599,701,601,445,193,15,19,851,408,751,112,564,864,111,119,632,983,256,635,222,888,809,338,328,415,228,714,97,174,426,614,869,756,145,89,887,610,93,325,714,388,738,633,645,179,178,257,143,346,65,554,606,640,59,621,881,51,905,732,383,81,340,780,540,141,993,434,749,269,790,132,344,378,950,365,478,14,495,297,356,736,618,107,381,977,575,191,43,726,6,887,522,862,861,90,276,298,370,262,347,835,98,639,602,757,835,300,936,407,481,780,767,722,278,19,917,528,767,286,342,783,755,719,173,530,914,191,878,403,638,465,838,986,780,305,53,966,20,185,901,100,87,153,1000,69,837,140,101,66,59,293,196,583,941,23,940,570,234,869,122,176,25,432,208,769,295,272,968,105,530,595,980,551,138,720,234,805,512,11,449,853,173,545,993,64,879,564,591,959,321,772,558,204,210,11,61,94,218,320,847,88,631,571,930,390,592,946,290,660,85,243,296,127,782,149,920,205,323,611,530,200,672,965,144,689,740,117,999,992,353,722,515,56,773,327,743,200,861,187,730,197,650,686,536,934,678,81,720,204,927,77,508,765,16,833,731,587,270,181,383,553,995,611,960,243,288,93,761,766,157,964,687,428,97,844,314,62,560,67,5,269,539,663,835,616,132,313,836,635,377,174,180,739,365,377,302,626,607,110,867,330,240,637,309,442,909,156,415,377,743,189,514,84,312,634,864,816,88,574,335,113,245,195,504,486,857,189,869,769,142,670,835,779,792,774,777,36,69,817,803,310,829,233,379,85,75,408,543,419,977,592,22,168,750,991,845,875,317,53,425,199,174,963,211,572,84,600,98,364,293,164,185,308,746,102,686,306,708,330,187,487,665,566,536,676,962,781,101,271,26,68,272,471,178,416,282,925,558,470,383,900,912,961,587,98,192,150,272,940,676,125,976,266,712,33,240,905,755,990,418,171,364,373,829,658,411,739,239,865,147,567,916,916,276,117,284,61,297,80,103,999,471,368,644,456,743,450,546,620,540,315,554,330,298,668,319,936,364,495,405,435,518,492,790,56,591,858,539,690,357,989,510,749,796,786,109,652,331,187,112,150,624,295,378,751,377,972,530,138,167,638,108,787,840,159,951,750,97,368,966,830,206,79,507,521,559,321,998,48,885,287,123,234,259,885,831,311,816,85,205,604,639,117,206,591,859,822,742,937,232,561,134,461,848,789,926,653,722,707,585,784,323,701,319,585,360,483,812,880,409,969,354,837,484,960,858,724,407,186,683,134,377,484,297,53,686,628,850,791,498,981,347,150,413,414,886,382,839,387,650,341,780,443,227,381,558,225,988,128,114,653,962,808,801,887,540,383,986,938,498,949,690,229,946,641,200,143,354,486,424,32,38,288,843,131,745,877,629,791,773,622,561,459,195,862,122,250,965,85,439,918,240,351,890,909,389,628,587,364,250,535,988,568,821,282,363,741,264,664,442,63,121,234,375,630,667,652,770,848,87,276,875,380,283,198,725,861,147,443,67,643,382,528,45,340,160,124,881,529,814,872,984,668,913,202,976,213,582,509,613,653,319,519,573,827,614,380,181,962,753,520,639,101,442,512,109,648,114,28,557,960,149,144,210,155,61,415,621,45,945,500,344,735,629,728,482,323,792,624,136,262,972,139,243,240,7,494,121,505,844,660,832,567,551,842,179,212,462,28,67,395,111,800,356,11,233,953,530,623,877,302,484,174,745,97,772,323,624,727,883,91,740,44,56,780,254,278,603,806,410,891,326,79,27,353,189,774,525,588,473,690,782,798,305,146,779,295,82,73,414,774,828,755,883,230,383,584,906,914,103,399,787,201,105,212,125,963,836,120,599,803,439,708,760,186,923,513,374,905,498,126,51,677,770,343,962,694,431,228,152,183,78,962,519,926,976,733,578,810,462,875,467,765,204,943,332,663,639,751,217,351,538,638,715,243,629,162,354,545,639,808,828,944,243,945,735,465,892,133,899,908,882,936,359,966,950,539,22,289,326,308,542,20,889,136,784,939,980,473,984,438,509,713,934,904,902,21,490,82,180,923,736,767,187,335,78,636,605,565,85,770,333,537,998,491,311,947,398,390,472,338,728,889,516,35,847,250,928,706,419,807,191,69,354,300,327,142,619,433,376,370,292,609,859,163,160,285,195,726,495,341,13,632,722,976,974,690,453,909,75,377,873,965,783,526,167,973,459,660,679,85,497,695,715,626,6,425,196,771,348,262,901,828,442,70,772,484,200,108,122,732,689,637,771,873,331,412,566,785,68,114,453,776,409,495,164,219,949,24,448,835,965,536,203,108,572,356,922,355,916,806,795,455,977,708,391,935,968,200,142,6,822,376,791,644,369,541,291,174,415,666,450,910,499,981,299,769,958,959,889,183,75,684,889,18,742,74,87,78,233,95,760,200,80,973,591,224,128,124,648,92,283,44,957,652,355,240,940,105,519,972,351,764,133,560,629,256,184,414,558,594,760,814,761,561,98,914,603,464,449,643,178,659,369,916,991,503,248,592,927,34,656,675,984,305,718,415,491,405,342,863,984,346,766,613,32,395,74,994,943,707,937,21,808,287,58,872,488,710,175,483,556,715,315,223,562,905,372,685,556,246,769,987,260,385,247,590,205,208,444,649,223,658,856,312,153,845,671,322,981,532,534,973,226,330,774,610,838,732,172,814,70,736,576,887,700,544,810,226,689,363,32,507,153,888,791,971,224,426,499,694,361,308,802,503,125,57,391,860,817,669,975,103,94,865,926,470,238,447,46,556,444,451,511,852,616,755,605,984,976,625,999,232,474,846,836,50,301,921,314,798,338,901,403,850,974,80,382,736,85,963,586,569,782,98,361,999,769,824,242,207,205,684,184,445,789,594,782,285,174,4,478,850,651,544,155,512,473,383,184,822,334,581,184,158,530,614,500,963,12,844,648,358,64,990,947,580,682,308,586,87,118,560,372,188,899,149,556,89,359,601,328,386,807,786,28,451,702,945,43,346,319,279,530,919,725,753,15,985,370,121,528,278,783,428,828,436,975,959,735,78,333,608,862,52,608,823,908,27,835,198,937,786,995,301,783,275,281,879,774,31,472,353,574,987,606,441,967,455,78,452,24,390,646,410,45,991,933,1000,965,668,288,630,998,674,897,242,375,446,580,837,323,810,390,764,210,765,239,606,589,607,654,627,148,446,697,126,874,691,855,751,976,332,902,275,370,662,799,507,643,854,352,745,467,162,944,840,998,183,295,939,689,315,942,101,187,476,522,988,375,442,227,131,6,217,174,448,911,777,847,709,671,671,197,742,292,325,312,459,975,631,90,353,727,451,490,944,397,731,499,60,705,476,283,666,942,339,354,219,614,725,143,296,434,428,223,985,29,392,356,672,509,484,447,199,176,708,350,489,259,591,163,131,204,504,691,289,270,825,669,753,744,157,85,532,827,366,808,489,490,459,646,22,399,234,642,479,142,573,911,75,259,843,399,120,497,433,669,428,315,807,745,73,678,868,640,621,53,977,545,710,940,703,18,365,851,873,942,383,910,953,53,666,338,685,778,791,89,883,770,154,212,77,254,849,682,288,634,534,407,804,706,897,304,947,27,422,434,538,849,751,178,486,329,847,810,687,185,644,404,344,408,161,236,890,651,535,170,870,488,949,127,733,979,796,524,276,541,176,293,876,435,886,314,853,329,878,312,404,682,903,448,224,518,320,108,928,668,832,917,26,641,183,901,52,491,418,403,1000,170,468,730,779,684,450,237,274,987,674,896,717,136,444,805,219,680,282,960,395,37,944,692,385,311,33,798,366,553,718,337,302,248,223,967,352,764,422,756,393,594,113,650,394,574,317,508,928,285,565,984,383,526,457,920,441,405,440,154,706,638,137,649,391,742,548,170,880,81,295,195,967,345,480,617,564,958,356,353,578,784,117,199,483,456,706,206,57,965,24,234,337,877,950,685,916,602,89,231,292,646,306,787,864,851,203,532,928,451,489,742,864,450,874,964,200,520,987,779,938,368,950,307,377,990,594,466,108,840,1,258,458,165,674,198,324,418,352,382,208,790,263,488,280,388,92,127,107,677,118,636,478,699,376,303,207,511,231,248,936,40,788,417,281,167,270,399,609,686,271,534,437,534,374,475,781,501,198,411,441,83,233,111,279,273,788,911,35,693,59,961,488,738,308,301,461,428,983,581,547,404,472,751,885,146,11,273,340,497,370,488,718,106,547,103,661,976,590,817,595,229,664,912,586,945,240,717,148,187,562,800,108,298,428,442,610,995,748,43,649,260,837,416,669,451,659,622,745,789,577,842,969,131,788,24,54,608,378,814,765,779,668,484,951,448,154,411,433,82,813,643,826,129,981,325,646,344,106,670,8,368,461,983,985,944,55,534,648,695,368,524,531,620,773,952,627,788,465,134,694,843,201,138,413,444,509,674,604,260,617,221,753,904,428,706,508,219,9,389,565,214,582,678,813,619,890,764,468,110,147,464,543,856,958,568,725,866,326,101,608,181,850,655,77,793,577,843,902,333,515,661,945,872,556,14,4,232,619,454,865,58,56,155,818,217,622,264,684,603,314,6,702,790,446,677,785,124,890,695,727,999,633,975,198,393,570,496,461,329,444,455,977,956,5,927,901,97,145,542,829,702,738,105,10,598,149,637,923,159,826,390,785,228,653,591,512,749,252,51,223,244,103,937,634,108,99,332,59,921,931,524,502,813,144,209,260,133,711,38,402,154,25,46,437,152,252,193,586,131,401,774,845,700,474,3,855,151,582,556,438,944,21,265,980,994,689,621,979,91,734,367,835,557,849,567,248,585,59,290,535,398,664,880,613,821,162,246,86,995,485,989,407,324,179,229,772,935,721,675,410,224,886,523,254,919,358,394,652,629,186,711,952,916,146,72,845,335,165,449,535,105,745,917,538,772,928,19,484,114,173,405,987,897,581,823,660,54,491,399,881,105,718,443,278,178,81,877,766,1000,610,782,643,925,508,968,391,218,238,145,528,341,843,159,580,484,229,46,251,613,199,256,280,333,456,270,817,347,645,466,763,243,181,927,145,412,445,38,12,917,75,241,926,417,668,352,136,305,921,391,120,775,952,930,208,557,258,546,510,818,342,753,457,589,957,158,661,262,262,519,942,190,318,118,715,799,197,344,290,520,495,270,221,618,192,143,40,481,454,483,769,860,59,219,319,939,817,678,4,412,84,581,616,523,17,689,426,586,380,275,208,495,733,485,828,67,505,8,386,467,226,96,772,186,487,926,724,884,106,533,286,195,727,118,304,855,876,800,915,420,190,200,421,313,596,420,312,381,202,992,145,386,778,49,577,892,924,246,708,875,978,773,809,355,255,654,274,377,155,969,313,193,56,658,720,892,122,68,921,78,939,649,165,471,786,224,896,501,840,195,110,504,940,482,63,287,162,274,302,350,835,972,813,875,490,232,388,602,885,73,258,809,931,724,673,18,468,236,479,543,413,110,942,129,40,468,605,230,900,701,713,880,698,205,952,116,602,191,25,413,359,257,468,74,48,248,857,418,324,344,723,149,411,193,563,999,224,964,842,177,511,642,278,746,985,215,798,867,686,374,411,854,524,665,166,473,86,182,976,524,634,999,742,524,296,34,547,967,556,125,502,20,328,379,964,923,727,190,724,702,124,861,917,962,686,24,121,417,379,487,953,895,933,984,927,246,139,768,648,133,516,302,804,241,477,246,950,490,483,663,480,987,138,785,244,97,237,924,180,653,219,257,470,113,45,9,845,271,981,15,599,56,228,826,49,298,213,386,303,295,903,501,324,308,295,863,625,114,634,713,633,878,893,258,181,12,630,443,35,29,783,455,383,139,21,583,824,761,711,644,233,358,256,690,523,322,370,171,991,312,574,867,258,256,524,835,482,184,231,334,460,868,204,937,771,20,590,198,283,370,572,673,280,522,18,195,120,38,239,525,40,736,375,523,615,774,803,594,630,298,49,491,671,116,950,32,75,137,230,942,756,281,371,692,707,892,701,569,886,473,658,522,610,427,521,873,853,798,987,946,469,56,388,273,227,111,636,785,343,82,417,532,188,186,706,817,481,946,127,257,815,938,433,358,291,469,976,661,805,6,798,171,842,566,401,734,185,2,380,363,58,199,119,484,437,75,758,844,639,67,22,887,48,420,212,157,531,259,71,755,199,890,703,594,759,479,184,572,441,526,876,525,763,737,568,357,857,230,762,970,691,736,736,406,268,819,587,82,15,641,135,729,378,751,663,946,406,784,512,329,679,294,288,9,338,996,951,710,879,886,940,97,149,868,675,450,414,96,681,477,697,81,371,329,34,320,463,803,475,221,500,684,32,417,376,742,395,638,80,280,577,651,93,510,810,204,67,214,388,516,727,568,869,495,798,285,77,759,704,408,603,565,663,866,737,677,254,541,820,880,702,236,736,313,991,403,231,246,210,379,39,815,889,283,668,975,978,419,869,281,580,582,940,316,93,519,557,29,457,961,70,602,262,108,518,991,909,738,349,987,825,246,364,436,206,969,66,308,625,479,467,818,538,223,830,389,132,206,559,659,382,966,347,944,802,662,424,159,380,817,901,892,995,123,770,594,668,541,552,10,349,676,687,576,15,772,138,128,280,402,51,875,921,615,150,119,794,479,375,2,595,341,423,607,854,695,147,81,845,429,406,521,624,409,784,646,713,548,484,465,520,802,104,741,528,290,881,113,290,556,350,32,802,71,662,443,372,669,188,413,388,758,28,172,950,607,418,740,990,255,599,627,792,256,21,412,292,419,556,529,778,514,986,542,271,368,570,811,344,387,133,185,284,391,484,287,643,781,110,450,840,623,756,189,559,424,503,146,300,568,11,391,406,383,256,896,293,935,357,282,160,690,630,997,721,814,882,457,896,69,644,658,56,730,37,575,639,441,322,367,82,858,360,775,72,222,279,961,835,105,200,268,569,755,764,320,139,915,472,574,285,168,268,78,686,691,57,937,700,159,844,291,844,294,131,11,117,638,563,823,788,567,217,481,322,469,922,381,480,712,734,343,273,703,833,858,779,826,983,171,472,872,215,374,601,10,678,496,120,422,133,914,620,940,886,244,32,247,21,562,335,334,292,186,980,145,903,638,194,648,226,860,363,531,941,931,445,321,893,560,622,728,385,985,28,685,247,560,331,908,640,875,695,523,672,636,893,732,745,177,619,602,18,60,283,904,235,520,78,646,326,8,382,632,217,956,38,208,895,101,98,347,127,834,27,880,944,159,170,640,350,849,705,362,287,339,879,516,110,238,376,890,942,296,611,236,817,186,419,442,511,580,269,155,503,288,697,35,763,162,340,46,111,264,465,825,538,156,222,796,113,229,983,420,293,441,147,73,65,103,337,858,240,653,958,331,651,32,274,327,896,387,64,199,439,794,380,21,90,958,652,12,791,844,216,746,878,992,775,841,890,759,377,711,402,680,394,977,234,909,227,99,437,678,891,496,742,105,557,125,914,187,410,722,928,319,979,513,556,574,920,568,410,524,84,595,77,113,991,90,397,597,301,314,850,438,670,715,595,455,15,623,118,173,568,362,473,607,752,975,479,266,769,842,271,944,628,450,790,847,545,483,402,881,878,941,38,462,41,717,531,922,560,200,124,984,433,229,585,562,57,828,646,468,721,798,35,635,729,425,895,764,295,998,905,215,141,625,546,610,808,206,261,775,643,184,707,245,983,913,926,67,691,748,780,597,419,78,829,946,674,749,468,163,402,894,571,577,232,499,221,919,879,367,226,851,211,135,897,283,508,443,758,58,604,18,733,358,411,158,137,40,436,334,488,689,18,979,373,935,316,367,643,77,41,591,210,851,351,526,344,417,572,949,768,996,862,672,555,696,122,883,306,521,378,607,955,32,344,559,662,614,808,248,969,500,304,371,522,48,668,337,889,654,750,110,228,780,761,702,1000,489,586,575,139,683,168,421,484,535,352,123,75,999,943,920,969,528,807,617,728,692,720,126,927,236,206,865,1,975,363,181,753,818,376,677,455,668,143,293,548,284,392,252,833,981,946,267,616,561,296,951,877,737,403,859,158,9,711,328,178,190,532,47,536,330,23,175,717,101,106,615,690,712,271,883,163,667,710,298,652,207,520,201,70,131,257,522,32,961,970,854,835,945,240,728,440,245,331,476,539,486,26,759,382,229,979,87,903,608,836,642,473,209,828,349,488,606,576,957,378,70,529,803,751,964,269,152,856,27,987,196,478,521,55,440,767,271,53,964,191,681,990,336,534,458,572,874,67,515,66,155,142,948,45,562,857,483,530,725,601,273,279,977,349,596,332,180,695,327,80,515,507,341,191,240,698,203,441,340,259,485,865,168,295,893,61,922,827,653,613,315,40,405,102,941,330,424,811,234,582,690,63,17,478,566,906,531,990,997,414,293,90,725,532,285,966,675,399,266,89,250,105,668,62,376,213,476,498,196,122,923,541,821,609,579,986,943,917,849,952,460,823,903,212,904,734,761,325,945,116,587,979,693,816,678,48,325,613,455,329,662,471,194,429,880,293,194,916,813,788,416,24,56,750,401,113,231,333,288,986,266,175,866,216,894,959,496,260,723,947,429,115,657,91,417,980,959,887,372,24,571,533,209,387,663,2,906,939,734,472,834,236,387,68,589,260,113,859,449,995,419,310,909,983,871,516,216,291,940,762,168,5,594,4,569,596,432,388,623,686,996,798,536,441,270,68,419,752,569,424,684,622,142,36,9,789,333,900,240,742,540,4,565,735,34,380,18,836,893,779,717,501,577,376,53,812,707,12,47,503,735,844,71,387,880,475,122,118,564,340,298,864,625,678,506,219,326,553,749,803,976,709,512,166,803,850,566,545,41,214,701,842,532,86,114,395,705,48,520,491,609,606,755,643,423,905,147,951,428,46,872,748,364,807,249,852,447,852,282,131,80,404,814,96,893,116,309,829,572,182,805,416,116,859,434,712,464,330,793,855,35,975,224,954,943,641,622,341,912,916,997,610,268,449,630,302,362,138,8,536,243,842,38,859,430,148,48,18,699,20,89,944,375,210,533,396,59,440,689,929,816,460,548,362,772,491,521,926,231,892,26,48,965,561,984,151,195,669,114,279,927,39,799,248,757,184,400,320,598,441,807,621,529,658,28,769,86,546,736,734,519,107,434,318,750,526,411,703,895,172,930,629,611,457,401,633,604,313,359,593,454,937,819,843,914,960,500,160,340,285,823,697,548,679,361,793,211,445,529,119,519,602,871,955,387,553,408,27,432,112,821,171,250,796,570,38,955,713,131,751,200,807,253,829,407,498,280,603,33,613,870,533,571,897,25,182,394,908,131,665,753,748,517,532,141,901,581,467,725,29,652,125,358,409,875,878,847,689,793,579,648,349,113,703,797,477,862,462,191,675,699,361,500,580,346,74,677,403,122,669,554,503,728,639,308,338,873,446,613,252,752,575,441,57,417,760,176,840,812,714,234,24,472,353,9,836,243,814,40,655,68,576,319,378,708,677,773,116,632,948,167,503,625,300,399,24,35,303,830,124,147,836,996,601,820,669,654,126,878,284,739,173,467,221,774,808,118,869,499,742,195,354,457,619,182,256,268,909,618,335,529,415,188,13,329,745,445,915,343,281,306,909,808,217,953,93,704,585,790,932,335,309,383,19,851,46,983,336,531,307,85,530,827,790,203,586,297,926,13,316,251,346,571,309,864,579,442,331,722,886,503,222,769,271,300,726,836,660,109,211,778,832,213,527,763,216,275,101,136,770,274,114,337,357,549,440,661,809,511,590,537,576,473,156,166,285,522,258,215,546,575,74,569,944,498,910,789,637,492,440,737,922,557,810,927,635,268,689,319,871,295,906,672,968,96,383,91,287,862,15,795,954,214,867,744,311,75,772,912,567,150,718,855,324,425,820,675,131,906,93,152,117,454,652,299,413,748,34,771,570,363,883,506,801,374,699,430,205,249,4,304,667,911,474,152,699,834,128,735,735,941,586,549,350,407,418,69,962,23,432,530,114,458,475,410,782,127,453,41,14,779,789,274,975,956,677,639,591,820,364,408,709,844,62,478,156,442,68,166,876,830,378,766,747,824,119,24,915,64,225,935,758,378,648,145,703,706,324,739,533,316,419,138,299,660,582,707,910,178,344,226,412,515,309,175,814,838,703,994,673,86,883,783,106,885,471,287,127,507,938,339,274,314,85,962,46,364,691,971,43,947,493,413,656,494,904,282,673,466,396,806,529,582,417,256,110,973,150,306,633,666,422,876,171,591,752,109,316,536,40,144,471,420,555,106,801,671,714,238,94,810,152,502,492,425,54,426,375,700,240,31,581,627,636,402,326,662,186,404,498,172,780,990,466,151,522,213,136,958,327,980,846,896,197,600,235,558,131,515,656,899,238,985,527,570,216,975,57,908,107,672,889,91,785,502,920,279,797,96,483,497,269,246,707,384,240,514,769,896,394,80,991,862,817,282,844,862,589,284,144,613,384,281,361,179,47,828,212,358,927,613,648,798,953,926,473,549,32,714,890,875,317,889,665,440,876,491,509,905,19,157,575,729,959,296,397,420,637,668,988,486,183,224,625,926,721,443,158,292,382,832,17,946,641,857,470,390,684,812,305,294,991,637,141,115,500,736,228,293,216,785,360,94,47,59,976,877,44,465,17,489,654,442,871,445,49,666,730,553,145,412,305,9,82,519,654,802,940,394,39,716,678,192,98,818,39,385,150,818,692,82,442,450,605,504,198,249,688,462,1000,729,562,131,958,657,610,964,33,825,545,970,308,433,880,753,650,497,842,887,466,772,816,917,695,937,81,70,897,596,345,996,796,436,207,952,5,778,244,494,656,373,203,150,613,632,864,775,371,452,60,353,9,276,255,891,446,163,429,215,17,473,20,577,256,949,699,751,62,129,803,213,660,894,247,494,73,392,6,604,85,157,245,378,374,72,738,151,133,703,418,260,578,252,676,229,339,392,993,421,649,210,861,647,557,266,603,788,304,667,88,839,882,217,470,302,843,645,695,884,792,969,80,213,603,341,315,157,956,860,486,489,348,972,675,202,215,189,750,293,129,874,504,48,760,768,581,602,663,874,654,384,850,636,141,853,879,185,872,93,515,514,68,830,719,826,381,323,145,995,804,464,558,471,848,587,167,565,934,692,226,661,895,93,449,543,148,948,474,136,376,260,116,324,478,164,633,982,498,628,826,201,316,856,618,371,951,445,640,983,428,737,237,999,475,281,50,244,67,718,945,944,936,898,397,731,510,845,966,705,610,749,997,498,501,195,375,877,157,325,647,782,475,808,663,930,245,681,480,907,107,923,387,541,92,782,767,878,663,764,364,753,570,265,76,996,749,966,837,136,858,8,978,624,557,511,702,879,653,943,964,689,954,910,769,898,612,660,735,336,615,7,103,507,691,793,899,294,210,242,882,325,142,78,421,330,123,496,516,152,496,50,16,253,29,861,255,62,174,236,900,854,455,305,382,331,180,685,695,646,86,96,874,856,894,367,227,120,352,410,101,755,627,936,520,264,389,720,770,568,942,235,222,143,873,820,669,303,751,2,132,501,595,566,301,175,566,862,553,679,297,646,43,231,142,865,113,481,723,405,654,562,651,376,654,466,211,742,132,202,988,651,458,759,711,162,546,992,350,248,626,492,364,891,352,144,556,585,674,585,511,918,420,847,740,74,666,726,199,176,281,294,284,63,843,188,95,256,818,676,85,760,350,547,360,372,272,478,575,707,573,185,555,751,650,686,894,574,855,435,123,55,233,803,274,299,196,170,369,659,402,602,899,602,992,427,643,575,706,511,110,615,680,505,622,98,759,73,728,629,188,315,888,381,29,663,331,765,491,993,540,171,525,753,475,91,156,74,985,245,178,607,668,784,639,993,860,304,664,715,563,492,830,986,950,714,981,883,566,391,880,4,999,882,400,830,57,113,387,127,574,637,71,762,97,462,687,240,672,535,302,521,560,582,423,281,837,849,841,8,88,949,680,672,743,577,771,344,535,743,71,431,69,734,238,283,728,785,997,905,647,488,425,684,717,10,524,252,687,819,468,478,923,419,855,168,383,10,190,121,505,673,419,572,333,799,741,520,338,891,424,953,599,415,173,926,18,725,156,213,854,33,422,473,454,12,328,167,836,985,289,662,422,798,493,542,557,107,657,6,195,881,453,471,375,626,148,419,754,636,670,198,184,11,490,7,818,44,45,822,488,146,893,819,768,798,696,893,901,26,897,850,697,359,139,173,74,459,664,292,998,818,187,527,867,612,414,433,277,336,620,897,783,762,363,982,344,374,799,383,42,399,687,814,444,415,206,64,72,371,987,990,925,958,724,107,665,150,157,237,142,218,929,346,278,398,932,196,434,338,211,160,438,266,520,175,668,567,158,833,64,700,600,222,27,610,137,726,872,653,904,342,918,852,54,690,719,901,54,674,932,809,721,629,988,490,339,243,554,777,207,904,604,904,78,645,806,579,394,92,304,507,201,852,966,990,73,735,98,764,750,563,807,417,675,359,419,752,559,374,51,16,629,738,95,104,513,115,894,888,357,46,328,343,788,695,331,378,967,736,443,14,335,926,71,941,282,337,330,741,73,499,249,362,537,380,583,376,103,14,458,476,16,270,992,271,416,320,54,937,658,422,457,857,358,998,228,454,442,517,450,410,21,1000,617,280,959,951,316,720,873,870,990,899,379,645,319,513,897,139,347,116,448,758,102,573,479,740,675,491,763,419,781,858,670,515,406,798,527,800,581,737,962,88,185,810,964,624,770,995,462,20,867,112,826,229,545,585,418,611,660,840,400,147,713,800,720,705,460,194,106,252,423,894,557,533,762,588,536,924,364,291,568,896,764,194,887,336,856,248,680,424,912,787,564,899,369,488,397,209,604,597,737,187,467,312,463,139,250,700,29,734,996,791,317,200,221,6,107,470,223,865,601,520,98,20,935,960,431,143,300,796,977,628,591,867,716,583,431,56,226,473,313,116,652,866,248,598,759,510,23,279,248,257,729,174,788,101,383,160,79,52,384,592,128,601,404,865,559,818,418,791,335,467,558,683,442,222,103,231,264,101,108,978,611,151,382,800,35,840,758,246,653,499,468,890,36,693,407,723,313,819,241,832,812,42,490,959,508,777,125,474,758,979,362,243,326,39,983,654,376,929,921,624,911,354,377,26,248,864,507,60,340,742,976,869,600,910,447,93,658,918,842,574,616,13,622,700,733,549,568,499,436,877,159,931,101,58,241,284,573,40,662,102,182,258,265,700,562,180,816,596,268,96,474,700,719,546,458,567,509,541,194,224,310,522,155,417,17,606,982,68,453,327,292,357,483,255,642,715,660,405,411,283,285,229,609,89,596,96,70,160,722,710,629,546,197,225,540,970,520,518,436,470,54,318,619,113,718,961,963,761,14,772,313,589,479,326,978,175,489,1,739,639,109,153,418,664,29,983,571,44,711,135,444,718,44,818,638,128,351,112,675,427,713,443,53,936,976,714,216,873,125,946,66,698,139,718,638,962,601,459,845,862,176,883,63,816,671,514,563,264,680,27,152,406,298,136,775,934,20,642,657,568,809,625,130,680,77,985,612,834,15,450,491,751,38,195,727,506,244,90,261,65,327,624,130,802,414,941,689,639,828,20,133,902,368,193,323,934,260,736,606,58,892,639,863,713,628,553,278,291,996,347,482,948,201,843,400,117,816,908,959,196,560,105,491,871,630,580,223,726,741,322,981,612,898,620,908,99,724,260,823,116,830,136,599,337,489,179,642,84,757,785,954,523,586,411,875,373,865,55,417,218,157,779,355,200,637,889,933,437,902,103,687,384,407,440,834,92,913,862,75,78,661,701,627,693,71,749,788,451,845,39,452,252,78,556,805,760,94,972,819,242,738,68,456,291,276,841,97,254,131,252,485,181,962,250,788,722,318,126,717,996,763,803,403,739,476,636,200,718,938,534,658,523,128,219,429,22,777,442,20,764,66,307,220,625,676,846,611,929,184,522,799,360,718,819,806,878,239,900,263,442,825,104,316,524,891,612,524,433,276,513,282,69,401,227,517,130,254,494,828,806,442,192,942,633,612,223,357,839,876,394,751,676,706,299,860,873,985,396,648,461,703,211,817,334,683,792,209,363,430,462,891,909,345,420,321,1000,475,799,717,397,159,625,963,464,94,320,875,330,943,83,934,270,169,865,603,988,328,726,626,418,595,949,413,307,416,423,960,125,24,274,710,768,595,109,640,906,270,786,337,684,480,696,781,154,88,167,850,242,40,295,173,205,307,999,399,751,259,689,520,32,455,312,74,537,829,44,498,844,527,466,506,306,412,186,430,19,780,782,434,23,841,690,200,484,58,652,753,399,734,237,704,569,6,523,874,273,464,784,594,194,542,641,897,913,766,370,980,456,519,100,385,441,28,631,935,888,85,618,429,694,446,511,638,181,714,9,294,726,216,458,152,406,288,93,603,998,846,920,590,913,386,214,584,111,802,483,803,212,860,712,858,143,470,554,771,858,301,755,710,158,136,30,225,136,460,934,41,747,931,292,647,479,901,178,122,326,165,424,46,945,156,522,785,357,976,536,560,378,815,73,54,218,786,573,754,766,235,322,266,621,455,358,146,1000,267,942,241,326,897,924,369,913,291,144,814,147,638,869,542,525,894,173,920,983,709,304,920,37,446,901,733,911,732,569,283,57,371,734,972,166,80,544,740,170,970,538,936,333,530,594,375,157,389,638,734,836,925,151,490,416,120,471,126,35,900,958,784,315,169,27,527,765,62,357,655,976,957,880,805,110,468,437,739,189,581,774,906,522,464,481,876,788,938,1,779,683,782,504,75,141,273,286,956,537,171,504,454,736,63,688,684,62,459,887,78,846,283,704,827,18,272,174,693,204,509,446,788,21,83,367,696,585,146,60,449,913,541,992,658,154,3,489,705,76,84,460,530,502,763,115,539,621,612,838,804,850,124,570,504,398,219,615,327,677,572,898,777,408,692,245,804,331,757,905,164,538,227,124,753,187,722,243,814,624,363,91,119,991,39,808,749,786,177,10,870,626,14,40,600,204,251,341,403,221,960,44,779,676,739,680,165,712,745,132,184,226,191,237,574,720,392,696,832,513,227,84,102,547,854,851,627,106,329,184,106,589,384,738,259,515,157,963,984,810,72,368,78,829,514,15,494,754,531,133,711,507,320,368,320,269,579,202,22,712,25,232,213,664,250,901,935,446,932,64,167,571,440,280,381,325,807,380,430,323,766,247,111,184,295,752,864,806,651,555,140,342,416,118,204,207,316,953,905,653,240,37,359,951,887,437,430,363,703,935,961,895,54,185,37,936,258,687,768,962,744,975,122,97,252,504,783,150,598,197,828,402,530,317,948,227,285,311,29,95,892,585,555,582,92,496,495,260,900,907,91,404,631,121,780,332,953,303,778,982,114,846,991,562,994,963,659,61,89,687,742,569,596,753,187,487,393,659,299,116,258,250,98,788,18,460,282,93,270,654,55,978,923,112,849,678,194,837,133,524,638,411,766,485,578,5,626,926,761,453,490,823,672,349,603,195,335,549,109,234,3,119,81,883,915,48,706,219,914,575,645,306,592,122,44,482,6,542,717,639,238,106,13,766,996,345,208,910,429,646,288,942,212,14,757,939,97,300,691,510,759,39,981,113,418,415,836,585,651,740,383,893,507,423,9,513,563,728,565,674,964,367,54,776,757,548,205,135,874,788,824,409,32,704,431,651,51,245,131,313,417,791,461,227,600,498,33,757,986,481,873,364,519,849,194,328,649,759,298,654,994,958,614,652,148,815,415,389,932,929,271,648,286,618,811,463,804,898,674,483,989,489,748,23,324,567,695,380,148,987,909,634,90,849,64,330,294,459,351,5,116,937,840,221,386,298,513,898,940,1000,149,349,871,804,666,424,960,853,912,29,803,718,453,788,364,117,942,297,504,842,133,316,702,855,850,110,935,851,445,256,460,516,838,809,635,518,849,713,925,284,234,448,85,457,353,593,461,303,970,401,81,228,619,524,762,629,666,579,456,552,911,276,417,704,706,185,963,518,799,27,138,117,485,240,910,353,740,590,454,160,151,699,324,673,428,497,664,883,790,626,231,571,946,519,227,251,228,704,167,157,382,984,990,774,148,276,737,982,386,638,359,467,727,770,299,395,753,197,748,947,577,361,22,752,897,212,761,706,229,24,783,631,712,161,109,648,173,313,565,956,696,694,870,882,313,446,848,982,336,559,619,986,511,424,296,233,300,512,965,697,180,950,157,980,674,382,263,492,172,461,126,28,261,527,621,106,503,605,631,729,555,340,55,787,18,720,368,367,819,26,450,673,693,164,735,78,416,922,358,533,496,482,280,852,633,71,940,660,66,104,100,316,807,25,754,583,471,358,693,771,131,424,867,574,759,302,586,717,883,277,710,388,800,421,231,711,931,326,784,608,442,173,706,754,150,885,268,212,942,19,432,557,767,409,587,558,350,341,457,432,306,677,906,651,364,862,967,34,98,281,709,910,287,121,995,668,415,665,586,474,363,249,796,365,464,218,398,748,826,468,480,240,232,138,579,435,617,154,42,358,634,922,522,453,439,239,760,504,892,460,537,421,100,308,222,677,64,504,943,297,449,655,615,158,487,942,935,724,439,24,734,122,546,18,688,111,277,902,420,946,465,103,697,443,540,320,732,156,605,703,519,11,141,492,203,743,385,951,68,997,853,850,505,74,821,251,662,32,459,196,429,382,139,993,722,270,779,978,504,976,606,82,81,572,126,850,136,927,627,790,833,220,349,169,29,388,663,577,358,25,358,46,901,444,549,126,633,927,225,701,865,62,751,75,890,924,698,642,782,768,899,814,154,238,802,350,737,681,260,449,815,579,907,82,549,839,143,173,887,860,125,100,856,529,822,290,270,536,639,897,285,296,131,995,1,143,154,549,255,454,652,66,295,583,253,819,630,40,61,235,626,687,939,203,166,387,956,851,377,983,714,261,684,562,647,400,216,363,454,641,191,676,518,317,995,861,366,945,227,566,334,159,855,523,37,341,551,79,934,679,961,431,733,72,130,594,899,523,319,416,949,884,7,855,417,340,24,859,384,63,600,391,317,621,628,119,60,458,176,132,804,69,874,999,653,177,216,667,624,327,291,363,592,456,561,792,790,923,914,222,870,998,93,692,473,849,223,277,978,551,69,452,703,763,482,719,486,940,589,188,887,310,991,397,219,509,76,370,785,558,415,768,54,679,920,877,582,211,74,973,973,269,655,393,898,972,281,254,635,957,603,206,431,287,604,337,326,506,32,836,795,597,286,206,144,971,830,397,819,59,51,694,57,693,34,157,37,912,854,166,856,10,570,642,850,97,757,958,576,858,858,391,760,835,98,736,544,98,80,1,593,604,255,624,307,485,687,311,634,345,488,410,442,244,316,927,392,40,933,585,17,45,520,108,967,233,678,385,537,418,360,539,609,20,829,860,176,702,801,229,857,788,275,22,963,19,455,628,186,70,707,395,248,111,231,955,844,672,441,947,75,370,479,434,765,709,52,105,489,690,63,967,122,138,249,754,289,932,691,62,854,655,117,868,340,416,969,789,976,729,577,477,956,110,488,16,544,437,175,573,793,500,457,912,453,31,73,124,663,117,278,257,273,302,857,553,594,995,530,916,365,509,149,321,638,933,406,390,842,446,240,547,367,324,588,313,479,345,453,122,667,954,336,964,660,103,474,351,96,810,626,985,816,739,756,633,102,290,928,267,368,353,361,970,604,204,786,912,514,119,449,296,732,997,528,415,672,336,392,885,898,908,455,496,2,788,707,557,658,617,392,809,871,719,390,114,88,731,369,659,292,208,920,835,729,2,68,720,183,743,310,935,875,541,526,615,495,601,53,409,412,19,721,223,370,856,511,613,790,466,52,893,4,484,363,968,638,520,914,967,280,243,449,86,282,578,445,301,649,173,805,435,938,152,905,487,342,313,34,792,20,943,283,197,966,542,295,867,932,642,773,290,147,231,266,380,766,546,51,175,977,804,829,248,642,821,620,229,480,459,947,654,1000,117,852,900,202,624,407,651,576,627,197,592,144,249,756,861,345,107,853,912,861,323,124,15,769,505,708,676,770,499,46,62,839,594,219,445,142,532,661,131,617,446,722,388,199,218,904,727,525,204,979,78,203,464,888,575,580,107,627,629,286,344,244,747,107,261,15,42,381,918,320,514,743,678,901,684,25,642,904,581,190,16,880,620,312,725,23,858,674,995,707,635,9,478,887,132,337,480,502,102,653,513,68,746,855,739,292,501,362,730,83,211,347,423,644,160,343,493,730,287,865,576,647,419,322,19,369,425,761,283,262,743,569,267,756,481,405,236,279,393,296,568,381,267,588,832,181,362,820,47,914,564,695,809,310,521,142,978,414,127,398,62,846,992,276,543,64,971,559,255,368,51,405,978,840,296,326,309,420,138,611,681,160,36,251,10,841,726,354,412,132,711,32,85,366,743,867,51,776,495,31,896,427,83,663,645,448,151,878,599,917,115,784,494,835,881,764,255,438,795,908,188,10,385,176,426,950,238,387,354,284,695,146,897,117,792,1,980,595,965,772,182,736,730,417,240,618,816,766,736,41,748,382,369,28,493,814,787,224,653,681,702,899,884,492,316,778,654,801,838,48,717,837,492,138,463,586,889,89,121,371,228,961,580,873,657,146,403,189,516,260,317,274,422,578,389,513,345,939,700,209,881,399,598,826,571,174,848,791,388,912,672,232,29,571,969,607,106,54,935,801,704,544,125,776,964,944,922,350,651,955,974,42,893,514,389,641,41,592,885,258,546,698,260,121,54,738,105,913,439,633,981,446,368,506,947,792,734,135,955,866,672,395,810,528,560,217,260,127,143,643,273,30,872,561,393,603,339,427,275,55,108,256,958,186,840,614,714,383,991,826,868,865,170,244,194,47,81,60,958,894,863,346,656,630,203,732,624,577,795,296,582,264,241,986,579,783,111,10,79,529,838,755,644,298,901,521,437,558,406,954,211,773,107,851,908,559,438,665,421,972,563,553,361,23,942,104,36,552,316,934,184,495,589,621,8,814,397,248,233,128,741,107,563,126,185,294,856,471,403,255,570,844,297,371,141,921,335,998,342,271,935,781,300,576,150,802,512,159,271,665,706,473,857,84,414,489,515,534,919,541,811,271,546,264,266,222,771,3,522,620,788,447,286,501,751,113,588,41,632,93,950,790,500,279,917,404,286,637,81,814,343,422,936,613,874,210,894,280,393,558,531,785,340,285,489,977,298,555,194,77,725,260,343,484,492,784,767,147,907,349,994,495,401,665,467,72,720,476,404,868,897,358,697,420,35,127,32,981,789,34,500,874,251,816,433,565,619,698,629,199,16,563,194,343,200,679,402,891,928,695,957,509,958,485,888,571,244,191,987,593,936,520,921,514,782,21,602,408,233,335,884,261,962,875,37,372,557,26,70,189,858,227,664,286,785,772,684,335,593,372,749,303,702,89,576,151,455,385,124,666,21,343,189,865,289,35,541,262,301,642,459,325,593,228,545,169,926,820,192,795,9,219,712,351,57,957,528,166,956,177,75,700,166,949,291,353,114,918,368,173,762,656,791,668,71,430,192,792,39,723,44,856,279,817,888,962,707,933,534,941,433,649,440,654,269,997,676,758,409,842,274,759,428,171,278,949,554,285,35,490,489,171,282,132,660,177,574,135,777,306,444,18,423,820,821,879,182,390,262,598,588,589,799,275,106,722,341,269,112,475,881,999,164,384,176,594,747,256,257,239,310,12,958,474,157,801,288,181,94,767,305,805,752,73,782,748,587,406,772,533,369,230,426,482,46,950,907,69,899,14,76,297,745,734,675,638,995,285,784,328,923,183,334,10,477,774,152,676,185,498,48,732,119,109,370,120,706,438,790,736,918,69,765,123,277,801,285,442,955,963,60,465,576,137,40,348,304,876,150,883,310,525,576,767,516,844,513,899,40,740,650,514,996,915,808,196,712,593,927,682,368,444,336,34,654,63,97,397,331,329,374,666,909,359,832,212,267,704,884,976,52,463,928,969,933,906,69,629,453,885,936,211,889,69,558,458,332,472,902,103,294,389,202,165,568,981,321,291,856,990,123,460,922,337,502,163,428,554,68,213,610,345,549,241,719,729,446,110,24,86,40,679,676,66,187,519,902,779,236,48,987,164,792,486,797,224,899,421,601,469,943,603,694,273,645,763,222,692,381,139,882,921,23,18,647,914,402,499,458,372,91,348,894,107,939,615,775,75,816,694,278,992,564,940,900,979,445,566,189,13,491,296,210,872,114,376,41,965,170,833,913,505,709,805,185,781,758,490,558,164,329,42,788,182,986,229,174,479,325,117,625,27,289,578,343,700,478,603,684,915,768,313,113,279,692,608,675,356,1,144,612,561,187,671,951,56,183,724,846,40,861,573,755,99,466,60,812,491,888,595,650,643,393,464,117,173,652,458,394,497,526,898,737,930,833,135,221,398,325,90,586,275,500,558,552,164,978,876,764,86,834,346,972,128,282,497,675,405,960,927,353,63,644,707,640,354,865,546,7,666,413,377,279,629,914,543,329,112,740,181,376,577,199,984,468,609,614,343,311,96,495,109,52,324,181,803,42,400,761,762,888,789,350,971,365,499,806,896,56,964,153,867,482,557,621,802,450,614,495,331,756,663,762,756,343,994,16,2,819,800,321,452,100,982,506,430,29,315,739,854,79,5,245,287,325,151,335,381,234,164,563,462,77,825,563,735,807,174,417,181,445,745,946,455,726,387,771,544,691,319,937,475,405,345,6,781,495,486,448,353,130,751,872,95,572,635,452,880,38,72,737,24,870,357,656,507,641,129,650,750,728,185,529,301,984,345,358,162,872,498,740,90,686,27,178,303,98,545,672,867,961,347,909,451,523,233,838,43,723,41,605,196,119,245,997,257,231,865,521,847,791,150,287,112,685,747,471,84,694,659,54,189,181,683,31,170,796,444,440,832,32,813,510,950,483,961,372,957,306,837,894,58,509,537,808,86,979,164,908,400,243,627,755,261,756,975,105,614,871,806,625,268,266,96,678,495,891,14,645,471,462,935,672,885,907,49,363,60,901,44,254,991,113,188,849,616,393,692,703,322,762,819,723,195,228,191,908,906,837,588,538,662,929,77,225,740,924,284,236,873,10,953,829,636,371,139,350,220,440,261,449,417,310,56,80,448,901,182,377,647,882,970,800,590,419,181,56,10,55,420,150,216,308,462,256,675,6,217,949,837,197,567,629,291,314,309,364,823,93,491,508,233,270,272,2,401,221,412,562,104,32,236,805,477,98,619,756,966,533,259,578,242,96,258,595,46,977,253,955,140,620,556,687,681,308,3,221,386,401,872,569,504,206,833,327,293,121,778,943,271,589,5,691,362,611,355,376,105,804,69,338,505,327,774,576,371,946,722,714,27,953,559,42,506,852,949,569,381,24,924,988,752,655,264,915,70,464,834,818,994,718,196,649,220,754,859,938,366,218,870,176,4,189,641,807,451,506,259,258,693,330,923,592,361,432,105,277,86,12,500,17,65,10,800,545,135,848,543,378,330,487,720,889,279,520,675,804,313,223,713,520,766,888,740,430,560,589,21,754,811,407,573,875,238,371,996,379,520,221,584,299,6,219,289,773,533,190,847,832,967,166,79,24,563,86,555,302,375,557,534,477,839,444,16,459,166,248,389,940,191,394,170,722,808,146,838,783,412,33,738,324,419,455,272,366,824,305,237,749,906,97,742,964,971,266,901,53,523,343,541,270,948,453,954,109,297,337,552,637,628,439,45,24,152,527,363,580,339,927,811,430,201,561,450,587,874,142,250,584,756,18,113,640,333,786,914,523,245,909,623,843,503,333,638,649,790,327,452,865,200,349,126,982,146,371,884,692,661,718,405,816,365,761,646,811,415,456,257,87,301,716,228,18,13,718,375,397,80,161,277,451,242,899,931,1000,645,901,785,28,726,428,459,780,771,507,28,497,400,193,193,694,656,996,921,731,205,237,982,498,938,447,318,300,725,872,344,743,584,732,402,693,115,876,556,159,797,661,546,15,552,309,597,296,845,16,641,121,929,357,590,455,369,589,835,436,648,792,303,977,57,817,867,641,366,385,141,537,307,20,257,102,962,128,36,946,457,658,147,673,83,336,441,956,678,830,969,454,724,447,520,660,282,564,82,168,199,5,615,107,537,695,701,431,638,234,758,850,548,544,839,798,927,567,180,261,745,208,5,555,211,168,431,346,197,857,623,682,336,804,176,746,666,213,727,9,357,803,700,778,601,51,864,48,720,77,225,354,407,613,587,103,941,951,363,939,455,319,579,589,570,958,430,132,572,789,840,926,906,200,624,192,272,59,837,992,812,235,375,123,83,334,502,956,688,996,908,233,779,365,32,803,280,359,2,692,181,880,550,329,571,775,490,241,357,111,568,53,829,20,411,825,56,824,755,743,155,144,790,128,824,865,621,378,191,992,300,668,142,613,444,313,677,804,885,577,849,259,102,572,175,370,175,45,536,403,155,738,744,915,359,786,22,320,370,516,920,330,289,23,175,466,80,663,557,782,212,710,95,257,159,172,691,328,902,44,390,539,397,807,711,886,13,453,584,69,820,310,283,815,122,235,432,224,946,599,499,10,452,674,157,530,755,873,286,795,876,404,818,654,693,143,683,744,188,28,776,297,45,952,726,608,832,774,132,845,483,766,499,326,550,943,36,77,435,120,475,938,295,458,780,369,867,749,60,626,967,531,792,74,803,565,282,173,924,530,313,276,61,682,770,674,221,833,507,169,373,704,690,264,622,69,983,448,6,481,418,279,70,452,129,823,448,548,398,546,542,280,543,125,459,411,250,330,65,969,786,996,987,358,777,254,325,114,696,784,404,266,701,281,509,962,945,597,121,849,228,142,515,307,824,113,220,49,896,663,689,538,565,460,217,887,399,796,186,152,252,367,298,302,996,520,186,616,293,261,277,457,509,700,824,729,251,887,351,210,259,123,391,469,107,563,766,599,650,944,935,436,828,313,489,896,510,482,81,176,805,78,906,375,323,947,13,194,618,331,789,142,864,655,615,325,810,755,62,155,321,959,872,911,455,136,873,257,163,343,670,770,244,695,636,66,745,147,639,260,578,434,648,573,457,867,299,994,329,339,957,45,708,783,702,132,766,197,577,372,741,952,791,908,378,567,980,993,858,567,19,619,1,248,960,553,985,493,122,968,894,846,607,193,524,380,937,278,323,755,974,635,236,409,959,528,742,129,920,413,904,161,506,521,474,185,958,905,857,381,138,567,457,270,270,606,935,765,479,365,298,645,480,341,974,397,203,970,790,48,796,751,396,476,725,569,590,227,296,953,855,964,235,817,132,687,141,754,779,994,720,565,612,354,508,86,790,103,164,334,798,75,611,57,729,732,2,937,503,982,110,748,732,372,272,97,868,155,919,413,407,929,737,89,594,956,936,997,168,239,115,494,106,477,275,429,725,609,678,531,355,395,259,402,844,134,947,497,505,194,993,54,746,676,989,199,998,702,717,724,977,370,21,80,94,941,500,227,120,777,992,74,83,351,440,604,474,641,736,404,710,833,989,658,864,154,368,86,257,832,958,536,655,988,702,678,443,480,319,221,41,963,129,757,87,112,658,344,267,852,56,159,829,38,200,870,452,531,790,911,151,37,999,102,941,317,680,159,499,216,157,589,969,167,909,867,31,581,460,232,75,191,61,14,539,924,768,366,604,659,868,882,866,835,815,407,418,329,661,202,787,480,788,615,772,196,875,427,749,453,915,289,814,941,4,427,710,97,64,760,640,37,331,296,52,376,636,582,201,813,914,590,293,797,738,644,394,847,563,242,36,37,114,383,120,714,999,642,531,489,335,277,488,41,492,568,865,782,663,900,173,688,754,393,824,317,693,954,897,440,833,107,104,411,570,773,971,554,289,373,250,353,477,507,679,399,377,259,413,408,885,672,824,603,20,107,587,208,402,793,756,442,620,983,177,919,68,403,187,961,362,937,250,970,994,613,809,164,34,904,182,910,172,586,276,311,375,684,693,105,26,340,893,847,116,731,540,651,593,994,143,530,416,344,941,315,750,481,433,541,493,662,256,607,708,821,540,320,63,557,749,379,957,718,206,359,871,56,389,229,566,225,573,797,826,715,326,828,777,408,974,924,296,73,999,399,713,573,12,339,202,862,216,378,554,477,689,744,452,310,708,347,255,438,371,561,448,802,43,918,345,836,383,524,347,121,4,664,372,545,401,247,384,333,793,840,858,297,504,818,476,392,73,492,991,985,216,400,106,490,671,635,932,614,571,684,643,753,617,839,917,832,577,294,602,661,645,283,732,971,712,102,603,682,991,211,221,953,298,365,744,292,858,677,727,847,792,961,613,195,874,457,711,748,888,628,865,454,558,332,976,474,361,592,57,46,117,700,9,768,926,325,151,573,883,933,616,128,413,42,22,299,863,630,452,764,857,437,918,166,9,85,873,76,916,153,452,569,162,858,190,505,479,164,851,650,543,36,268,604,80,168,484,573,89,371,526,873,934,420,630,384,207,646,969,349,281,315,687,163,29,265,481,760,910,95,394,343,172,752,375,253,325,113,421,695,763,98,212,989,377,399,464,796,658,679,868,361,407,811,831,358,170,669,5,288,776,152,188,658,818,543,940,148,944,5,586,625,527,520,866,23,102,936,212,474,72,322,570,303,561,311,907,906,572,525,945,747,949,241,509,781,395,419,87,778,72,237,159,852,194,599,126,500,580,19,996,18,491,717,825,349,282,459,109,754,903,201,725,997,58,653,685,105,71,223,363,800,706,236,336,574,160,99,614,681,801,296,399,863,324,996,981,574,228,814,536,360,988,30,562,15,158,189,412,859,698,827,587,32,947,631,501,349,784,241,343,460,137,494,755,686,470,477,82,914,200,573,467,78,576,10,180,695,328,199,917,661,817,634,924,55,268,323,15,386,560,207,60,980,349,884,963,732,738,203,575,177,191,216,267,487,862,339,172,801,997,57,138,429,760,122,368,42,790,324,318,446,215,319,840,102,426,559,216,221,810,217,131,335,803,43,436,826,838,250,985,464,102,309,355,745,396,381,960,218,449,327,420,908,750,516,66,843,553,531,134,22,272,25,565,996,418,198,865,919,613,774,213,763,711,592,295,971,685,176,839,952,172,569,474,974,521,23,100,281,709,534,695,989,681,114,828,926,170,158,55,608,57,834,913,236,921,956,310,482,801,220,163,407,639,945,166,591,193,696,262,19,956,757,894,374,857,449,684,768,776,335,296,430,940,459,910,338,787,32,261,575,485,625,345,195,434,281,385,447,118,493,569,38,256,478,835,664,78,95,307,434,864,357,908,778,322,982,490,635,381,984,416,62,42,174,434,999,704,323,338,158,299,460,287,873,564,759,93,754,195,631,516,339,842,476,678,728,602,890,210,830,364,963,532,930,739,721,617,499,56,259,63,108,589,157,305,675,612,858,728,616,467,837,856,147,603,878,380,805,526,698,959,978,909,538,399,71,313,451,721,596,645,906,621,682,396,348,553,436,689,276,114,506,975,873,490,607,900,214,383,408,912,596,779,26,700,365,24,118,725,224,772,523,893,65,949,630,42,485,258,286,714,879,893,22,836,886,326,276,857,612,158,712,412,920,81,969,52,552,841,435,473,790,868,78,630,726,392,828,955,633,648,480,820,811,194,72,397,601,448,648,482,524,217,659,439,651,373,991,205,640,617,443,197,174,615,868,800,227,534,336,253,560,680,381,425,337,707,549,913,977,538,876,288,506,31,769,547,558,419,284,869,978,483,610,263,405,601,124,206,741,159,471,883,765,94,356,16,623,793,738,429,802,401,235,642,848,830,623,515,442,463,59,661,979,609,381,946,542,940,80,667,21,611,785,453,244,195,630,881,406,180,592,830,380,966,314,268,515,886,931,924,112,545,451,142,526,753,429,200,216,834,331,275,461,237,350,836,385,480,371,431,220,899,867,775,480,47,651,300,78,750,137,315,790,851,684,907,355,999,826,383,207,712,523,583,537,352,253,449,223,385,972,33,371,952,289,117,949,287,675,76,249,664,421,902,434,893,997,971,413,974,930,635,798,470,116,708,192,592,685,789,645,62,78,821,406,281,335,195,31,132,69,326,291,626,455,683,323,838,641,972,64,494,523,290,664,561,662,881,393,767,527,687,951,17,399,483,902,597,436,941,721,359,139,916,254,413,91,668,406,244,21,505,324,652,121,790,697,837,147,402,692,962,810,346,408,563,971,650,646,147,646,965,631,758,923,71,800,278,656,843,636,5,835,682,617,257,425,775,509,459,126,971,434,743,454,448,858,915,78,719,254,118,780,99,242,786,258,104,921,819,887,818,816,964,682,142,850,376,257,100,371,522,103,969,765,500,44,190,973,610,388,839,323,944,902,97,185,400,958,631,855,662,33,914,693,516,197,506,74,110,303,936,229,264,409,321,3,938,904,233,560,769,170,211,184,353,537,603,819,365,461,748,569,165,859,397,966,640,524,965,813,669,656,594,998,385,983,124,897,625,125,773,625,493,51,93,939,852,465,985,95,64,50,256,450,512,127,640,682,987,882,651,503,229,107,37,887,243,546,443,270,774,418,797,771,341,393,331,415,898,826,820,732,639,564,96,83,701,754,960,230,292,375,289,567,945,839,613,911,916,663,585,550,137,819,191,781,243,913,168,900,204,862,742,980,992,954,870,195,769,458,803,991,931,349,288,860,381,159,165,351,58,302,610,219,363,580,645,818,950,9,125,509,804,878,9,396,138,790,738,296,66,431,835,776,281,273,19,566,172,460,899,241,824,67,218,787,501,5,279,586,330,556,915,206,480,616,16,122,678,354,177,739,996,219,219,602,55,290,995,883,98,675,37,410,837,85,303,835,204,981,96,233,395,329,800,323,430,70,461,12,744,323,529,947,750,905,279,155,550,93,268,538,319,610,943,238,818,294,571,853,817,783,451,134,307,204,662,475,393,103,116,115,527,275,979,756,842,463,967,837,895,294,869,737,135,830,799,795,699,796,178,660,836,406,467,184,160,839,318,30,707,237,516,695,119,694,821,958,262,573,318,700,695,323,215,370,635,196,657,165,878,640,800,404,417,959,34,11,234,291,516,774,625,860,150,567,841,87,748,680,477,23,193,526,526,381,573,256,345,1000,725,693,810,935,818,951,588,80,917,705,823,120,1,188,803,975,464,452,205,162,885,587,228,506,121,534,465,757,325,477,252,539,383,207,577,582,446,360,545,831,251,800,467,765,472,991,698,176,684,155,841,414,76,708,601,412,12,211,212,143,170,318,624,990,90,293,854,226,229,652,173,837,515,935,444,426,292,762,393,995,895,683,537,3,792,97,896,734,644,243,258,818,84,837,572,736,764,280,52,587,700,861,55,386,919,708,709,11,213,215,638,491,684,966,744,391,269,424,429,446,601,399,441,750,38,869,873,978,681,895,707,640,325,939,295,728,108,553,713,130,683,929,180,607,259,323,290,121,612,425,946,794,915,964,591,611,480,823,765,5,685,1,348,762,98,549,88,71,484,118,33,200,632,682,833,569,17,552,968,250,617,480,462,644,808,601,505,349,863,741,699,372,841,777,221,673,724,933,467,566,383,724,94,964,708,310,676,634,502,971,251,40,661,712,855,449,522,402,559,638,288,113,101,764,609,384,788,219,312,359,875,754,442,38,839,992,571,259,602,957,356,847,54,121,620,675,630,802,76,796,212,352,113,947,797,834,926,159,693,822,355,401,116,4,929,813,636,299,71,251,534,36,129,35,14,154,928,219,64,308,189,855,489,903,502,956,75,503,166,772,524,38,741,835,977,819,166,907,653,105,958,442,397,94,327,227,469,21,899,64,334,868,569,998,590,434,365,74,719,214,895,536,267,177,374,442,783,650,19,131,357,947,682,953,884,985,877,948,151,164,761,409,180,520,1000,518,427,561,229,244,972,179,547,555,117,916,722,785,661,199,210,414,661,297,897,134,688,256,211,944,257,807,279,393,570,508,123,458,391,719,418,840,663,847,215,566,877,881,276,416,457,99,288,824,590,365,833,796,422,265,248,844,197,652,471,902,94,244,39,762,358,562,365,663,635,667,938,567,845,807,306,118,479,909,285,961,572,697,52,994,850,895,895,194,931,642,492,294,16,432,878,542,258,562,894,715,15,754,41,216,451,225,120,979,273,815,99,642,138,591,612,179,31,908,138,965,892,743,123,2,25,575,852,539,258,438,17,433,700,572,424,139,778,161,645,616,681,913,458,152,622,162,467,76,676,642,680,438,35,140,591,274,293,245,679,542,566,570,880,813,617,808,80,576,191,321,866,357,298,181,213,422,644,550,312,123,117,809,444,158,677,319,983,520,781,23,637,383,186,162,429,542,588,825,443,630,518,953,573,476,690,387,637,485,450,679,153,287,352,7,703,336,952,916,399,410,842,201,682,72,240,195,81,120,83,184,206,504,217,226,389,166,360,417,616,958,912,317,230,42,224,729,39,682,946,811,451,692,616,349,710,376,958,647,111,983,271,525,617,949,513,579,316,996,815,779,894,558,159,141,189,102,482,755,672,94,592,270,665,379,790,332,307,215,473,715,261,550,799,886,765,419,909,267,556,26,59,502,166,944,52,274,148,373,258,593,830,611,787,505,776,960,618,732,547,225,277,164,439,827,902,624,828,387,203,466,383,592,572,872,911,986,473,791,922,139,140,196,44,270,505,421,136,356,111,575,894,971,282,336,678,294,801,734,750,413,736,53,334,463,52,929,260,893,947,319,420,397,756,516,522,883,913,347,808,763,653,710,746,991,497,420,631,950,306,504,214,535,420,282,107,840,738,208,872,656,101,374,559,349,348,214,240,140,790,853,329,110,968,400,881,556,835,974,439,793,927,223,851,85,845,687,344,100,382,681,947,120,129,7,335,662,3,852,158,730,588,776,453,375,531,510,745,489,439,85,201,738,712,983,937,48,42,358,432,88,888,367,677,862,889,3,538,276,685,357,593,93,83,998,583,37,921,993,914,169,297,717,144,436,511,284,710,162,660,358,154,440,850,732,944,635,859,825,575,852,878,812,385,163,432,929,427,879,409,495,488,593,287,275,925,593,661,246,419,903,735,739,357,944,228,100,171,255,445,118,390,689,943,679,474,547,443,299,834,604,72,673,201,837,525,220,536,829,637,295,69,439,65,614,442,606,71,796,757,303,608,979,183,865,240,316,718,574,382,180,250,386,185,379,643,132,601,192,804,786,373,505,691,891,399,544,338,846,898,377,773,547,425,146,598,528,187,431,757,377,127,422,641,749,681,639,385,992,554,94,378,433,713,905,125,515,744,38,260,30,184,775,628,515,279,909,76,5,318,184,685,822,499,110,720,519,879,812,213,139,334,497,386,597,430,474,233,785,80,939,360,993,833,336,785,272,528,175,101,938,317,555,486,441,190,109,805,800,472,827,790,405,81,848,480,41,134,185,869,162,719,111,614,897,446,384,607,195,74,802,288,401,284,965,559,741,781,479,276,389,479,393,195,949,204,483,436,993,343,423,712,508,542,492,617,99,194,354,762,806,105,398,196,848,747,101,19,222,284,179,542,41,564,380,183,501,208,318,174,690,93,345,403,213,812,881,486,984,652,717,46,995,337,333,330,193,69,208,531,96,231,348,284,258,163,450,874,736,760,333,10,662,134,247,955,798,720,559,349,212,884,33,809,899,773,271,960,455,143,16,935,715,317,407,407,529,793,825,891,55,89,502,160,269,833,380,99,155,958,276,942,568,231,779,587,826,370,35,722,900,297,348,843,564,120,138,753,743,818,561,391,86,884,969,295,486,957,889,781,213,16,158,507,689,737,317,367,189,153,864,754,580,111,52,375,766,837,157,719,484,247,949,76,60,155,732,244,575,270,583,742,834,199,498,249,673,12,404,905,356,8,279,194,741,943,633,906,174,720,894,763,269,191,361,197,110,633,831,608,827,662,277,300,323,981,395,804,571,554,257,518,305,972,315,933,467,44,227,898,48,7,638,707,830,490,469,362,812,652,127,194,704,731,259,385,745,8,634,83,867,905,794,445,612,749,478,364,538,389,3,559,560,792,455,930,6,538,257,184,634,910,277,85,800,39,743,171,441,286,745,679,834,265,286,114,838,107,423,33,375,564,338,888,526,878,212,13,910,301,902,11,983,610,582,488,337,400,406,247,5,130,270,663,460,964,759,896,237,559,825,804,883,979,563,576,703,871,610,508,692,278,314,591,498,875,917,34,918,339,292,35,134,599,403,810,570,994,101,402,940,12,727,800,470,628,289,537,800,809,45,809,259,592,293,443,366,215,61,45,283,3,509,66,845,556,951,727,971,452,624,44,788,803,478,140,948,42,118,15,845,814,266,157,936,63,178,317,710,315,8,440,762,976,793,765,845,946,965,738,54,443,655,920,372,296,867,649,317,985,794,372,333,739,450,678,165,746,282,439,530,794,818,785,276,4,929,518,559,172,878,557,25,500,144,996,152,993,758,508,451,916,916,541,706,339,16,299,924,991,444,870,56,423,281,559,70,578,983,763,646,182,500,922,302,194,726,80,971,989,731,352,783,488,954,799,663,546,692,89,823,360,785,752,476,635,726,580,173,786,856,519,132,938,375,361,353,741,226,304,594,64,261,707,630,883,587,614,638,363,605,787,664,280,554,171,255,225,925,637,226,361,171,17,456,665,83,131,962,218,307,407,343,36,427,504,462,302,632,682,986,166,408,917,441,583,632,855,769,103,336,147,329,296,350,573,222,416,499,37,247,590,897,888,847,996,520,698,424,418,608,925,232,580,252,786,287,855,688,658,368,288,545,480,227,831,380,430,220,994,790,468,631,23,430,726,483,163,469,467,809,202,181,270,9,97,464,980,573,415,492,758,481,193,533,471,670,154,449,517,537,469,802,89,877,613,351,202,197,829,495,131,635,445,209,178,587,739,788,117,278,399,954,607,606,3,241,220,950,150,418,313,114,82,893,349,899,551,326,36,407,7,406,215,24,860,491,86,404,903,904,321,14,54,863,118,547,184,357,22,73,14,492,684,442,34,729,137,229,762,882,473,258,619,5,33,71,808,276,448,278,462,555,734,701,753,729,794,28,266,440,967,602,732,749,150,823,190,904,948,604,636,516,350,238,423,570,602,686,573,113,984,169,475,822,388,579,410,362,344,200,671,137,688,848,239,770,551,916,578,376,734,178,456,428,837,813,164,598,477,919,562,614,456,789,688,139,779,500,516,539,431,445,658,514,39,755,30,769,119,741,887,292,99,976,279,177,791,334,743,239,283,276,527,287,738,833,620,40,857,531,725,678,257,624,113,204,230,213,458,358,906,501,448,312,107,243,513,615,231,453,15,168,747,937,176,52,251,333,441,373,27,904,828,821,407,802,708,131,230,836,242,458,466,141,243,635,286,220,188,550,691,831,726,82,142,83,309,929,910,589,216,203,247,331,510,356,766,547,662,172,993,725,856,441,502,660,40,330,740,876,68,168,821,383,591,612,713,526,373,903,297,384,661,545,433,773,971,595,680,919,302,102,826,791,13,618,940,180,314,709,48,999,719,201,818,603,318,308,273,714,199,372,969,159,391,426,672,383,595,376,936,701,675,735,994,529,540,750,555,433,153,638,909,785,148,687,605,585,335,336,747,911,858,830,437,667,857,669,200,774,486,634,321,234,481,601,569,70,492,495,738,433,886,379,907,434,648,240,984,844,636,583,199,626,843,824,346,444,553,661,104,984,238,956,436,778,900,61,355,631,543,97,580,496,35,579,437,572,268,176,660,174,537,518,387,138,979,553,832,886,867,464,539,475,923,170,695,679,318,312,839,217,88,604,32,877,268,366,826,883,302,911,283,810,841,421,974,834,751,21,766,978,27,84,52,660,620,812,82,818,223,296,204,711,72,444,847,307,710,370,420,142,709,567,992,899,249,502,891,180,743,733,760,650,526,735,555,974,369,228,135,158,235,83,862,658,687,506,881,781,1,262,155,751,50,456,543,758,229,653,756,102,295,65,615,477,693,389,132,981,965,20,445,351,135,979,625,518,374,157,811,956,279,727,120,564,554,669,858,944,789,492,126,779,373,367,830,566,418,865,612,565,715,942,903,316,734,609,661,946,391,699,169,89,517,534,930,584,211,691,521,141,173,168,988,551,157,733,419,523,737,617,922,242,10,245,288,94,420,681,502,300,611,142,945,171,128,291,419,571,272,340,860,753,402,628,151,825,47,18,975,699,280,731,104,77,851,988,50,387,864,780,327,258,946,548,541,581,162,240,543,173,295,665,890,226,620,258,871,627,662,22,940,19,264,445,635,841,670,758,768,776,690,379,188,24,711,785,349,921,324,797,91,854,215,952,268,902,969,530,86,864,59,382,74,68,91,136,159,91,433,708,492,243,484,532,239,318,493,484,379,73,952,270,310,938,412,735,140,672,814,962,461,600,792,793,355,604,926,383,651,338,989,848,939,891,700,573,315,360,499,248,463,443,735,804,35,41,23,795,346,903,955,353,810,931,395,145,963,430,397,862,36,853,328,82,597,622,693,559,230,368,437,689,334,694,937,970,82,745,586,596,175,611,849,992,946,154,888,268,360,882,480,37,714,968,621,661,536,45,114,775,669,340,253,80,414,608,189,189,607,444,854,732,805,683,824,779,219,69,856,303,265,973,419,259,133,629,667,629,799,834,889,227,176,672,612,284,164,734,191,374,628,612,893,719,881,854,969,629,404,151,256,269,438,68,823,711,440,799,413,317,775,885,8,533,955,620,560,801,570,659,308,41,122,397,293,327,942,604,411,966,443,990,51,694,853,420,184,956,603,408,150,198,571,638,893,256,706,834,497,39,974,361,941,105,62,913,287,760,480,762,509,831,59,742,635,111,483,637,376,462,172,131,774,849,164,605,938,668,162,225,404,535,119,751,282,919,888,930,629,448,515,408,890,894,895,437,307,454,365,942,336,164,454,811,391,873,244,642,858,915,816,714,513,930,148,448,436,897,513,797,747,214,405,714,851,680,771,200,606,782,585,155,30,613,491,562,830,422,284,99,483,361,193,382,625,781,304,729,210,932,864,151,945,438,222,571,983,316,575,193,690,287,624,909,714,941,644,828,283,165,948,930,549,704,727,718,42,822,819,516,817,1,758,644,103,361,467,931,980,503,903,962,953,567,676,412,438,529,128,299,753,105,224,360,767,245,209,434,13,383,611,764,182,479,889,70,82,928,620,740,447,695,537,447,592,209,29,831,325,615,633,380,401,36,394,28,495,333,699,109,468,937,197,311,881,310,597,918,541,427,846,26,144,691,607,271,726,742,618,421,181,257,619,273,825,827,388,899,822,282,150,387,173,931,379,683,152,288,778,192,226,757,89,667,424,944,950,773,765,79,212,894,748,417,798,840,332,834,250,229,426,751,762,349,350,383,540,713,576,339,810,520,407,393,743,142,309,420,422,309,915,820,773,962,796,169,823,26,521,703,141,304,103,184,829,748,431,879,793,97,365,939,688,193,29,129,626,75,364,372,35,785,739,772,884,48,147,81,568,450,272,972,184,451,95,185,318,814,852,188,337,756,758,735,607,807,226,239,560,952,978,97,750,274,658,869,309,923,465,288,744,144,912,81,983,65,566,880,767,361,647,776,937,343,594,509,903,36,53,661,248,410,421,883,798,101,677,5,428,564,868,286,579,413,152,973,45,632,345,657,712,863,970,871,224,827,208,518,42,824,871,833,953,712,959,762,9,149,831,643,433,128,513,150,357,633,242,158,913,889,54,679,767,242,764,832,732,730,964,137,430,153,945,924,814,691,574,122,374,937,150,42,967,191,908,556,248,665,628,460,359,389,155,877,533,229,982,87,652,212,475,931,707,49,384,805,527,805,515,46,971,561,701,979,690,699,531,896,718,103,956,398,357,722,339,782,681,476,928,239,450,852,496,853,375,48,81,207,49,506,190,215,276,101,590,703,886,235,853,310,326,769,551,982,382,970,927,848,415,927,977,795,649,353,570,116,737,991,24,430,967,249,383,874,75,744,400,613,511,420,329,886,242,626,120,828,859,542,954,173,320,354,204,584,348,114,374,217,3,233,240,115,919,810,402,771,578,690,501,663,122,247,867,899,461,442,320,921,845,227,417,185,884,264,766,12,867,864,779,788,14,298,261,449,979,746,747,92,824,871,997,58,882,67,246,444,364,551,202,647,505,757,130,136,103,276,266,377,752,939,718,401,470,6,989,389,468,442,32,901,493,978,5,985,837,822,577,911,470,136,36,511,399,21,568,852,618,312,647,476,536,687,406,470,64,167,697,473,361,622,30,974,537,512,474,223,860,328,674,339,209,750,528,333,527,113,714,409,880,85,758,778,791,447,625,945,926,676,616,324,657,783,824,683,566,431,711,633,895,366,566,855,324,623,258,132,405,916,170,740,951,972,397,905,26,628,600,113,470,537,567,738,283,870,660,797,844,897,748,581,166,107,515,622,875,457,836,242,171,27,572,693,35,524,168,610,930,461,174,540,732,398,853,100,758,140,873,269,157,88,101,207,666,606,983,356,236,63,431,359,527,27,753,21,339,578,83,545,195,524,538,792,91,825,584,738,794,42,833,936,188,928,87,993,912,924,550,438,36,787,310,42,681,190,766,91,887,213,913,590,847,597,505,566,857,284,8,747,275,773,421,394,562,438,346,720,301,298,262,16,127,429,146,870,887,993,498,741,241,780,151,773,148,396,263,556,807,381,546,828,283,594,588,643,722,4,97,374,649,989,280,128,351,211,874,297,177,946,679,910,413,575,108,217,807,878,149,465,309,795,908,980,564,897,220,810,525,933,451,829,964,999,279,831,642,540,596,508,953,897,317,91,318,98,951,813,812,617,38,542,115,135,768,457,608,84,496,107,734,642,488,69,79,334,135,762,193,716,257,59,686,410,847,227,327,670,189,56,433,860,754,987,381,55,616,55,393,167,402,540,197,786,283,876,446,982,808,135,120,486,843,616,607,830,372,89,243,532,764,786,165,48,762,195,533,725,614,92,984,762,831,424,958,247,606,256,618,176,681,271,396,304,761,755,418,920,934,623,931,88,384,415,491,137,218,414,696,359,641,751,473,620,258,7,13,760,59,544,741,83,434,166,774,303,964,991,441,891,279,250,792,629,536,155,611,580,610,795,475,516,72,141,78,564,223,279,572,517,768,235,525,760,696,504,798,772,205,497,461,660,169,561,326,548,970,718,757,959,664,163,92,136,393,396,964,503,392,745,204,311,325,644,80,573,714,112,882,822,561,412,184,243,556,473,6,798,812,771,331,437,580,962,991,10,135,744,1,727,838,55,17,642,358,434,68,716,114,755,721,208,900,321,404,368,472,545,843,595,793,550,187,418,391,963,331,178,43,347,270,651,514,917,931,921,107,273,523,970,483,869,947,732,415,867,941,21,817,161,943,848,570,201,345,597,21,98,111,57,212,3,936,932,506,495,408,790,309,432,3,919,986,827,118,642,165,267,645,595,129,945,265,774,512,762,145,386,392,703,291,828,688,813,947,925,676,946,37,569,168,159,162,760,115,202,182,873,709,174,326,278,615,669,562,366,163,193,185,383,978,549,299,932,37,14,51,882,149,722,907,398,761,997,455,19,744,920,2,617,48,952,621,98,133,209,421,923,605,648,616,823,670,614,604,595,435,430,626,520,255,143,746,826,336,312,15,888,130,890,398,968,266,137,592,98,247,620,1,339,967,363,969,560,849,138,768,365,279,784,864,854,135,109,593,289,381,412,808,438,476,499,563,190,535,546,955,871,869,94,161,667,440,560,215,752,877,808,243,168,129,906,163,594,247,279,52,597,105,123,671,379,951,594,173,121,747,569,586,369,294,110,37,898,413,342,443,175,43,383,592,659,545,883,893,270,659,531,692,554,649,156,38,269,699,31,754,303,255,692,227,128,661,729,361,301,246,333,64,188,743,963,908,137,877,228,331,824,26,360,54,60,200,941,704,691,707,968,347,527,157,335,156,244,224,753,351,928,952,138,219,687,743,497,626,818,498,98,683,753,211,649,481,625,123,392,360,187,262,558,102,563,322,17,704,399,809,962,45,903,234,524,551,625,712,403,914,968,927,414,183,420,384,875,950,559,731,350,565,426,273,325,243,708,529,652,51,92,826,847,569,202,379,416,819,751,673,415,191,683,420,6,356,823,983,480,741,531,886,597,849,651,87,12,418,492,702,369,911,520,946,772,602,642,345,500,119,892,57,872,492,603,873,420,107,178,518,507,142,296,600,915,560,193,957,556,53,506,235,539,603,330,227,500,698,60,648,402,323,646,347,48,991,377,219,754,551,312,635,190,595,448,368,437,757,948,870,677,419,590,250,335,255,189,724,752,183,659,61,437,505,226,551,723,153,365,264,907,365,282,159,770,306,503,998,878,382,176,866,644,238,503,105,21,531,731,318,324,890,722,467,990,940,548,567,839,528,488,223,189,826,928,638,460,400,60,647,313,718,195,926,171,163,648,611,28,377,693,844,235,119,385,579,568,68,460,824,659,111,523,168,592,632,454,812,483,982,440,644,365,234,566,457,570,225,382,261,227,135,764,249,926,997,355,703,300,695,112,114,762,692,664,986,856,154,163,743,818,491,441,231,456,959,477,990,30,264,177,347,47,206,739,363,615,86,896,844,96,270,63,750,681,104,158,969,65,819,751,157,961,311,81,288,148,551,381,215,862,987,43,830,607,112,370,971,232,992,658,415,944,784,145,134,547,349,467,739,290,749,914,929,538,177,431,998,72,912,755,907,352,398,634,981,355,452,313,190,337,132,67,774,992,341,989,283,439,25,743,636,837,426,76,636,211,122,862,563,887,687,34,866,538,301,750,829,714,55,97,574,328,887,179,398,105,445,812,428,56,304,420,200,487,931,753,889,372,344,244,773,861,355,355,471,773,98,99,925,623,68,397,162,643,978,644,985,414,370,180,706,246,921,250,901,493,879,914,959,417,476,197,687,94,111,270,318,71,653,153,203,696,265,484,282,527,134,238,365,594,152,300,537,924,29,512,254,581,575,566,372,75,19,166,582,514,496,388,311,463,396,519,922,628,580,630,148,497,368,311,778,267,100,672,781,754,631,143,113,945,864,811,690,889,847,984,281,968,825,437,373,765,514,813,179,656,867,803,620,829,985,763,916,795,29,579,926,420,433,877,498,719,762,520,981,659,373,259,234,558,211,293,71,715,826,946,368,195,392,63,986,820,375,412,534,882,897,472,20,66,933,21,198,679,997,868,69,994,548,344,502,798,745,763,253,851,296,94,415,790,949,686,993,628,221,721,422,259,693,538,650,685,61,856,254,468,376,254,92,337,626,853,30,919,1000,545,571,62,757,405,590,684,716,958,953,483,9,402,601,697,808,426,77,120,854,295,845,169,940,769,537,29,801,735,468,675,654,753,707,752,504,280,187,814,824,853,225,808,526,435,544,41,732,920,440,448,502,15,872,625,298,320,995,775,917,411,451,684,212,269,617,81,23,547,326,286,902,586,152,861,843,84,916,62,908,423,618,122,595,782,679,368,429,709,171,875,692,699,501,291,164,20,959,982,54,510,346,629,965,26,337,702,937,952,371,909,661,658,515,795,406,863,132,478,268,585,265,371,301,28,317,53,814,671,758,748,295,27,501,243,16,487,876,425,967,722,37,127,189,758,990,380,809,322,966,698,454,549,269,305,39,778,353,673,854,775,520,999,159,669,308,784,851,541,706,971,628,633,725,198,6,499,660,941,880,336,788,853,439,131,935,409,835,594,90,255,829,24,570,586,342,182,502,623,954,805,293,470,922,327,344,147,78,301,709,263,290,745,362,10,441,418,299,834,813,939,19,224,595,132,997,519,178,118,326,945,611,862,921,13,344,52,171,702,846,300,694,418,52,855,29,154,820,575,545,530,269,799,195,501,837,834,173,760,129,420,949,567,998,134,942,218,681,595,610,209,656,381,384,841,236,44,402,663,181,918,483,183,314,266,639,243,317,3,264,15,937,358,699,838,543,440,828,555,499,6,598,322,84,181,898,149,45,682,786,673,639,673,58,636,66,636,370,446,120,955,394,627] |
笔者理解
此题是一道数组算法问题，在力扣题库中被定义为中等题。
解法
当笔者阅读完此题后，发现此题用滑动窗口更加方便快捷，先计算出老板没有技巧时的满意数，再滑动调整老板的技巧时间求最大满意数，让我们来看看具体如何实现的吧。
实现
1 | public int maxSatisfied(int[] customers, int[] grumpy, int X) { |
时间和空间效率都较高，可见此解法比较适合此题；
总结
本题是今天的每日一题，难度达到了中等，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 徐年の博客！
