pq_test.go

package pq

import (
	"testing"
	"sort"
	"github.com/stretchr/testify/assert"
)

var elList = []*Element{
	NewElement(100, 5), NewElement(90, 6), NewElement(70, 7),
	NewElement(4, 8), NewElement(5, 9), NewElement(6, 10),
	NewElement(10, 11), NewElement(15, 12), NewElement(80, 13),
}

func Test_PriorityQueue(t *testing.T) {
	pq := PQConstructor()
	for _, el := range elList {
		pq.Insert(*el)
	}

	res := make([]Element, 0)
	for pq.Len() > 0 {
		res = append(res, pq.Extract())
	}

	for i := 0; i < len(res)-1; i++ {
		if res[i].Priority < res[i+1].Priority {
			t.Fatal(res)
		}
	}
}

func Test_ExtractPanic(t *testing.T) {
	pq := PQConstructor()
	defer func() {
		if r := recover(); r != "Empty pq, cannot Extract." {
			t.Fatal("Expected panic but err is:", r)
		}
	}()
	pq.Extract()
}

func Test_Peek(t *testing.T) {
	pq := PQConstructor()
	el := NewElement(100, 5)
	pq.Insert(*el)

	if pq.Peek() != *el {
		t.Fatal(pq.Peek())
	}

	pq.Extract()

	defer func() {
		if r := recover(); r != "Empty pq, cannot Peek." {
			t.Fatal("Expected panic but err is:", r)
		}
	}()
	pq.Peek()
}

func 	Test_PQ_All(t *testing.T) {
	assert := assert.New(t)

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

	countMaps := map[int]int{}
	for _, num := range nums {
		countMaps[num]++
	}
	pQueue := PQConstructor()
	for k, v := range countMaps {
		pQueue.Insert(Element{Value: k, Priority: v})
	}
	actual := make([]int, 143)
	for i := range actual{
		actual[i] = pQueue.Extract().Value.(int)
	}
	sort.Ints(actual)

	assert.Equal(excepted, actual)
}