Leetcode 977. Squares of a Sorted Array

algorithm-i-day-2-two-pointers-977-squares_of_a_sorted_array-explanation.md

The Optimized implementation of Bubble Sort from GeeksforGeeks failed the below test case:

Code:

# @param {Integer[]} nums
# @return {Integer[]}
def sorted_squares(nums)
  nums = nums.map { |n| n*n } # square the numbers
  
  # now lets sort with bubble sort
  array_size = nums.size
  (array_size - 1).times { |i|
    swapped = false
    (array_size - i - 1).times { |j|
      if nums[j] > nums[j + 1]
        nums[j], nums[j + 1] = nums[j + 1], nums[j]
        swapped = true
      end
    }
    # we break out if there was no
    # swapping in the inner loop
    break if not swapped # or break unless swapped
  }
  nums
end

Test Case:

[-10000,-9987,-9986,-9985,-9984,-9983,-9979,-9979,-9976,-9975,-9973,-9973,-9973,-9972,-9972,-9971,-9970,-9968,-9967,-9963,-9960,-9955,-9950,-9944,-9939,-9939,-9935,-9934,-9931,-9929,-9928,-9927,-9926,-9921,-9918,-9916,-9914,-9914,-9912,-9908,-9908,-9907,-9907,-9904,-9902,-9900,-9900,-9899,-9897,-9896,-9895,-9895,-9895,-9892,-9889,-9887,-9886,-9886,-9878,-9878,-9876,-9866,-9865,-9865,-9862,-9862,-9861,-9860,-9860,-9857,-9849,-9849,-9849,-9846,-9844,-9844,-9842,-9841,-9838,-9837,-9835,-9835,-9834,-9834,-9830,-9830,-9821,-9818,-9813,-9810,-9808,-9807,-9807,-9806,-9802,-9801,-9797,-9797,-9796,-9793,-9791,-9787,-9784,-9783,-9780,-9775,-9772,-9772,-9771,-9768,-9768,-9766,-9764,-9764,-9764,-9757,-9757,-9757,-9757,-9756,-9753,-9752,-9747,-9745,-9740,-9740,-9740,-9739,-9736,-9734,-9734,-9733,-9732,-9731,-9730,-9730,-9730,-9728,-9722,-9721,-9720,-9718,-9716,-9712,-9712,-9711,-9711,-9708,-9706,-9702,-9692,-9689,-9688,-9685,-9684,-9680,-9678,-9678,-9678,-9675,-9674,-9672,-9671,-9669,-9662,-9661,-9660,-9660,-9660,-9659,-9654,-9652,-9651,-9648,-9647,-9646,-9644,-9643,-9641,-9637,-9637,-9634,-9632,-9630,-9629,-9629,-9629,-9629,-9623,-9621,-9619,-9617,-9614,-9610,-9609,-9609,-9605,-9605,-9600,-9599,-9598,-9595,-9595,-9591,-9589,-9589,-9584,-9583,-9582,-9581,-9580,-9576,-9576,-9575,-9574,-9570,-9569,-9569,-9567,-9566,-9566,-9565,-9565,-9564,-9564,-9563,-9563,-9562,-9560,-9559,-9557,-9557,-9556,-9553,-9552,-9541,-9539,-9539,-9534,-9532,-9531,-9531,-9530,-9530,-9529,-9529,-9523,-9518,-9517,-9517,-9516,-9516,-9516,-9515,-9514,-9514,-9512,-9505,-9505,-9503,-9502,-9497,-9489,-9487,-9484,-9478,-9476,-9473,-9473,-9472,-9470,-9467,-9467,-9454,-9453,-9450,-9447,-9447,-9445,-9442,-9439,-9435,-9430,-9427,-9426,-9425,-9424,-9422,-9422,-9421,-9421,-9420,-9420,-9419,-9418,-9417,-9417,-9416,-9415,-9415,-9414,-9411,-9409,-9406,-9405,-9402,-9401,-9400,-9400,-9396,-9396,-9395,-9387,-9387,-9384,-9383,-9382,-9381,-9381,-9380,-9379,-9377,-9375,-9370,-9369,-9369,-9367,-9366,-9364,-9363,-9362,-9360,-9359,-9358,-9355,-9353,-9352,-9351,-9351,-9348,-9344,-9342,-9340,-9339,-9338,-9337,-9335,-9334,-9331,-9327,-9327,-9326,-9326,-9325,-9324,-9319,-9315,-9313,-9310,-9308,-9305,-9302,-9298,-9297,-9292,-9287,-9287,-9287,-9283,-9282,-9280,-9280,-9277,-9276,-9276,-9274,-9272,-9272,-9272,-9271,-9271,-9267,-9267,-9265,-9264,-9262,-9261,-9258,-9255,-9253,-9253,-9245,-9245,-9243,-9241,-9240,-9239,-9237,-9236,-9230,-9230,-9224,-9224,-9220,-9219,-9217,-9214,-9212,-9211,-9210,-9206,-9205,-9204,-9202,-9195,-9194,-9191,-9191,-9188,-9188,-9187,-9184,-9183,-9182,-9182,-9182,-9180,-9179,-9177,-9175,-9175,-9170,-9167,-9164,-9164,-9163,-9162,-9161,-9159,-9159,-9156,-9154,-9153,-9153,-9150,-9150,-9145,-9144,-9143,-9138,-9137,-9134,-9128,-9127,-9125,-9123,-9123,-9120,-9116,-9114,-9109,-9105,-9105,-9105,-9103,-9102,-9100,-9099,-9097,-9097,-9096,-9096,-9093,-9090,-9089,-9082,-9082,-9081,-9080,-9078,-9077,-9077,-9077,-9075,-9074,-9070,-9070,-9068,-9061,-9058,-9056,-9056,-9055,-9051,-9049,-9048,-9046,-9046,-9045,-9042,-9038,-9030,-9027,-9025,-9022,-9021,-9019,-9018,-9018,-9016,-9014,-9014,-9011,-9011,-9009,-9008,-9002,-9000,-9000,-8997,-8997,-8996,-8993,-8993,-8992,-8989,-8989,-8980,-8980,-8980,-8979,-8977,-8977,-8976,-8975,-8974,-8973,-8971,-8968,-8968,-8965,-8962,-8962,-8961,-8957,-8957,-8954,-8948,-8943,-8940,-8939,-8937,-8936,-8935,-8932,-8932,-8932,-8931,-8928,-8928,-8927,-8927,-8925,-8925,-8925,-8924,-8923,-8916,-8914,-8912,-8909,-8905,-8902,-8902,-8900,-8896,-8896,-8894,-8891,-8889,-8887,-8884,-8883,-8882,-8882,-8882,-8878,-8876,-8876,-8874,-8873,-8872,-8864,-8858,-8856,-8856,-8853,-8843,-8843,-8842,-8841,-8840,-8838,-8835,-8833,-8832,-8831,-8830,-8829,-8828,-8825,-8823,-8821,-8820,-8816,-8815,-8815,-8814,-8812,-8812,-8803,-8799,-8796,-8795,-8793,-8792,-8790,-8788,-8785,-8782,-8779,-8779,-8776,-8774,-8773,-8771,-8769,-8768,-8764,-8759,-8757,-8754,-8753,-8751,-8750,-8741,-8739,-8728,-8726,-8724,-8721,-8719,-8718,-8718,-8716,-8716,-8716,-8715,-8707,-8705,-8705,-8704,-8703,-8703,-8703,-8703,-8702,-8702,-8700,-8698,-8697,-8693,-8690,-8690,-8689,-8686,-8684,-8683,-8680,-8679,-8676,-8675,-8675,-8675,-8671,-8669,-8665,-8663,-8659,-8657,-8652,-8648,-8644,-8642,-8640,-8633,-8632,-8629,-8623,-8622,-8617,-8613,-8612,-8612,-8609,-8607,-8606,-8606,-8604,-8601,-8598,-8594,-8593,-8592,-8591,-8590,-8590,-8585,-8581,-8579,-8578,-8576,-8575,-8571,-8570,-8567,-8566,-8566,-8560,-8559,-8559,-8558,-8558,-8555,-8555,-8554,-8548,-8547,-8542,-8541,-8537,-8534,-8533,-8528,-8524,-8522,-8520,-8519,-8519,-8518,-8514,-8514,-8513,-8511,-8510,-8506,-8505,-8505,-8501,-8498,-8490,-8489,-8488,-8486,-8486,-8485,-8482,-8481,-8480,-8479,-8475,-8473,-8467,-8466,-8460,-8460,-8458,-8454,-8453,-8452,-8451,-8446,-8432,-8431,-8430,-8429,-8427,-8423,-8421,-8421,-8420,-8413,-8413,-8412,-8407,-8403,-8402,-8395,-8392,-8390,-8390,-8388,-8387,-8384,-8381,-8381,-8378,-8378,-8377,-8375,-8368,-8367,-8365,-8365,-8364,-8364,-8363,-8360,-8356,-8352,-8348,-8347,-8344,-8342,-8341,-8339,-8338,-8336,-8330,-8328,-8327,-8325,-8323,-8322,-8321,-8320,-8320,-8319,-8318,-8317,-8316,-8315,-8315,-8314,-8311,-8307,-8302,-8301,-8301,-8298,-8297,-8297,-8294,-8290,-8289,-8287,-8284,-8274,-8273,-8272,-8270,-8263,-8257,-8256,-8249,-8248,-8247,-8247,-8247,-8245,-8245,-8245,-8241,-8235,-8234,-8226,-8221,-8215,-8214,-8213,-8212,-8210,-8209,-8208,-8207,-8202,-8192,-8189,-8187,-8185,-8184,-8181,-8178,-8171,-8170,-8168,-8166,-8163,-8160,-8155,-8153,-8150,-8150,-8148,-8145,-8143,-8143,-8143,-8141,-8137,-8132,-8132,-8131,-8127,-8126,-8123,-8123,-8123,-8120,-8120,-8120,-8116,-8115,-8115,-8115,-8111,-8110,-8109,-8109,-8106,-8106,-8106,-8105,-8103,-8102,-8102,-8099,-8098,-8094,-8093,-8089,-8088,-8086,-8085,-8082,-8080,-8073,-8073,-8071,-8069,-8061,-8060,-8060,-8060,-8059,-8053,-8050,-8050,-8046,-8043,-8042,-8042,-8037,-8033,-8032,-8030,-8027,-8025,-8024,-8023,-8022,-8020,-8020,-8017,-8015,-8011,-8008,-8008,-8007,-8001,-8001,-8001,-7998,-7998,-7992,-7992,-7991,-7986,-7985,-7984,-7983,-7983,-7980,-7979,-7979,-7979,-7976,-7976,-7972,-7970,-7968,-7968,-7968,-7968,-7967,-7966,-7966,-7961,-7958,-7956,-7953,-7951,-7951,-7943,-7941,-7940,-7938,-7938,-7935,-7932,-7932,-7931,-7929,-7929,-7927,-7927,-7926,-7926,-7925,-7922,-7921,-7917,-7917,-7915,-7914,-7913,-7911,-7910,-7908,-7908,-7908,-7905,-7903,-7902,-7900,-7900,-7895,-7891,-7890,-7889,-7885,-7884,-7884,-7882,-7881,-7880,-7879,-7878,-7876,-7876,-7874,-7872,-7867,-7862,-7855,-7851,-7851,-7849,-7841,-7834,-7830,-7829,-7828,-7828,-7826,-7825,-7822,-7820,-7820,-7819,-7818,-7817,-7817,-7815,-7815,-7813,-7812,-7809,-7809,-7808,-7808,-7804,-7802,-7801,-7801,-7800,-7796,-7789,-7788,-7786,-7786,-7786,-7784,-7781,-7780,-7777,-7776,-7770,-7767,-7767,-7766,-7763,-7761,-7759,-7758,-7757,-7757,-7753,-7751,-7750,-7750,-7748,-7746,-7743,-7739,-7735,-7733,-7732,-7730,-7726,-7725,-7724,-7719,-7719,-7719,-7715,-7710,-7695,-7695,-7691,-7691,-7690,-7690,-7690,-7689,-7688,-7683,-7682,-7682,-7680,-7680,-7679,-7678,-7674,-7671,-7653,-7650,-7641,-7638,-7637,-7636,-7629,-7621,-7621,-7621,-7617,-7616,-7611,-7611,-7610,-7608,-7608,-7607,-7605,-7600,-7600,-7595,-7587,-7586,-7585,-7585,-7584,-7583,-7583,-7582,-7581,-7581,-7580,-7579,-7577,-7576,-7575,-7574,-7572,-7571,-7569,-7568,-7567,-7566,-7565,-7561,-7561,-7558,-7558,-7555,-7553,-7552,-7549,-7547,-7545,-7545,-7544,-7543,-7540,-7539,-7539,-7538,-7537,-7534,-7534,-7533,-7531,-7531,-7530,-7529,-7527,-7527,-7525,-7519,-7519,-7517,-7516,-7514,-7513,-7511,-7508,-7507,-7507,-7495,-7493,-7486,-7483,-7481,-7479,-7479,-7477,-7476,-7476,-7473,-7473,-7470,-7469,-7465,-7464,-7463,-7463,-7463,-7463,-7463,-7462,-7461,-7461,-7459,-7456,-7454,-7454,-7453,-7452,-7448,-7447,-7446,-7442,-7440,-7439,-7437,-7437,-7436,-7436,-7434,-7433,-7429,-7429,-7428,-7427,-7427,-7423,-7423,-7419,-7417,-7412,-7411,-7408,-7406,-7404,-7404,-7403,-7399,-7398,-7396,-7394,-7393,-7392,-7388,-7388,-7388,-7387,-7383,-7382,-7380,-7378,-7378,-7377,-7377,-7375,-7375,-7373,-7372,-7370,-7367,-7366,-7366,-7364,-7362,-7360,-7357,-7354,-7353,-7349,-7347,-7346,-7343,-7342,-7342,-7341,-7339,-7338,-7335,-7330,-7328,-7327,-7325,-7325,-7319,-7318,-7316,-7314,-7313,-7312,-7307,-7298,-7295,-7293,-7289,-7287,-7284,-7281,-7280,-7275,-7275,-7272,-7269,-7268,-7267,-7260,-7256,-7254,-7253,-7252,-7251,-7248,-7247,-7244,-7243,-7243,-7231,-7229,-7225,-7224,-7223,-7221,-7216,-7215,-7210,-7208,-7207,-7206,-7204,-7198,-7197,-7196,-7192,-7189,-7184,-7183,-7182,-7178,-7177,-7176,-7175,-7175,-7174,-7172,-7170,-7168,-7165,-7164,-7163,-7161,-7161,-7161,-7154,-7153,-7153,-7145,-7143,-7141,-7139,-7138,-7138,-7135,-7135,-7133,-7124,-7123,-7121,-7119,-7119,-7117,-7107,-7104,-7100,-7095,-7084,-7084,-7083,-7083,-7083,-7083,-7081,-7080,-7079,-7078,-7075,-7075,-7074,-7074,-7070,-7070,-7069,-7066,-7061,-7060,-7057,-7056,-7049,-7048,-7048,-7047,-7047,-7045,-7045,-7041,-7037,-7036,-7035,-7030,-7028,-7025,-7025,-7025,-7023,-7021,-7021,-7021,-7019,-7013,-7012,-7012,-7011,-7011,-7010,-7008,-7007,-7006,-7004,-7004,-7003,-7001,-7001,-6993,-6992,-6986,-6985,-6978,-6974,-6973,-6969,-6968,-6968,-6966,-6965,-6957,-6956,-6953,-6952,-6952,-6948,-6947,-6946,-6946,-6940,-6936,-6934,-6933,-6933,-6931,-6931,-6929,-6928,-6925,-6921,-6919,-6915,-6910,-6903,-6900,-6900,-6900,-6898,-6896,-6894,-6888,-6888,-6885,-6885,-6883,-6881,-6879,-6876,-6874,-6868,-6868,-6865,-6864,-6863,-6863,-6861,-6858,-6855,-6853,-6850,-6850,-6850,-6848,-6845,-6841,-6839,-6839,-6837,-6836,-6833,-6827,-6826,-6825,-6825,-6821,-6820,-6819,-6813,-6812,-6812,-6809,-6808,-6807,-6807,-6806,-6806,-6803,-6801,-6801,-6800,-6799,-6798,-6798,-6797,-6796,-6793,-6793,-6793,-6793,-6791,-6790,-6790,-6786,-6784,-6784,-6782,-6778,-6777,-6774,-6774,-6773,-6771,-6770,-6769,-6769,-6766,-6766,-6765,-6765,-6762,-6759,-6755,-6755,-6753,-6751,-6749,-6748,-6743,-6743,-6743,-6742,-6739,-6739,-6735,-6735,-6727,-6721,-6715,-6714,-6709,-6708,-6707,-6706,-6705,-6705,-6705,-6705,-6703,-6702,-6701,-6701,-6698,-6698,-6697,-6691,-6683,-6681,-6679,-6678,-6678,-6668,-6667,-6664,-6662,-6654,-6652,-6650,-6650,-6650,-6649,-6648,-6648,-6648,-6645,-6644,-6642,-6639,-6634,-6632,-6629,-6622,-6622,-6622,-6621,-6621,-6619,-6619,-6616,-6616,-6615,-6615,-6614,-6608,-6606,-6602,-6602,-6601,-6601,-6599,-6598,-6596,-6595,-6594,-6588,-6585,-6576,-6574,-6574,-6571,-6571,-6570,-6567,-6567,-6567,-6564,-6563,-6562,-6562,-6562,-6560,-6559,-6559,-6557,-6557,-6556,-6556,-6556,-6555,-6554,-6552,-6546,-6544,-6544,-6543,-6540,-6539,-6533,-6531,-6529,-6529,-6528,-6524,-6523,-6522,-6521,-6519,-6518,-6516,-6516,-6515,-6509,-6507,-6506,-6506,-6505,-6503,-6500,-6497,-6497,-6496,-6494,-6494,-6492,-6488,-6483,-6479,-6479,-6479,-6478,-6477,-6477,-6476,-6474,-6473,-6469,-6468,-6467,-6465,-6464,-6463,-6461,-6458,-6458,-6457,-6456,-6455,-6455,-6452,-6451,-6448,-6446,-6445,-6444,-6443,-6442,-6441,-6441,-6439,-6437,-6437,-6436,-6432,-6427,-6427,-6424,-6416,-6415,-6414,-6412,-6412,-6407,-6407,-6407,-6406,-6406,-6404,-6400,-6398,-6397,-6387,-6376,-6376,-6374,-6372,-6372,-6369,-6368,-6364,-6361,-6356,-6352,-6351,-6351,-6350,-6349,-6345,-6341,-6340,-6338,-6333,-6333,-6333,-6329,-6329,-6326,-6325,-6325,-6320,-6318,-6312,-6311,-6310,-6309,-6308,-6308,-6308,-6305,-6305,-6304,-6298,-6297,-6291,-6291,-6291,-6290,-6288,-6285,-6284,-6283,-6281,-6279,-6279,-6274,-6273,-6269,-6269,-6269,-6267,-6261,-6259,-6259,-6259,-6259,-6258,-6257,-6250,-6244,-6242,-6242,-6238,-6238,-6237,-6236,-6235,-6231,-6231,-6231,-6231,-6229,-6229,-6226,-6226,-6223,-6223,-6222,-6221,-6215,-6215,-6214,-6212,-6208,-6208,-6207,-6200,-6194,-6194,-6194,-6193,-6193,-6191,-6190,-6190,-6190,-6189,-6186,-6184,-6183,-6183,-6180,-6178,-6178,-6178,-6178,-6178,-6177,-6173,-6172,-6170,-6168,-6163,-6160,-6155,-6151,-6148,-6147,-6145,-6135,-6123,-6123,-6121,-6114,-6110,-6109,-6107,-6104,-6103,-6095,-6093,-6091,-6089,-6088,-6086,-6085,-6082,-6082,-6081,-6080,-6079,-6077,-6075,-6071,-6068,-6066,-6064,-6063,-6062,-6061,-6061,-6058,-6057,-6052,-6051,-6049,-6048,-6046,-6045,-6044,-6042,-6039,-6039,-6037,-6029,-6023,-6022,-6021,-6018,-6015,-6014,-6009,-6007,-6006,-6006,-6004,-6003,-6003,-6002,-5998,-5994,-5993,-5991,-5985,-5984,-5982,-5980,-5979,-5978,-5978,-5977,-5976,-5973,-5969,-5969,-5966,-5961,-5961,-5961,-5960,-5959,-5959,-5958,-5956,-5954,-5954,-5952,-5948,-5948,-5946,-5941,-5939,-5938,-5937,-5934,-5926,-5921,-5919,-5918,-5917,-5917,-5916,-5915,-5912,-5909,-5905,-5903,-5898,-5891,-5890,-5890,-5888,-5887,-5879,-5878,-5876,-5873,-5872,-5872,-5869,-5862,-5861,-5860,-5852,-5852,-5849,-5849,-5847,-5846,-5846,-5844,-5844,-5841,-5840,-5839,-5837,-5836,-5836,-5829,-5829,-5828,-5828,-5827,-5827,-5826,-5821,-5820,-5819,-5819,-5816,-5813,-5808,-5808,-5806,-5803,-5797,-5797,-5794,-5794,-5793,-5793,-5792,-5791,-5790,-5785,-5783,-5781,-5780,-5778,-5773,-5773,-5770,-5770,-5770,-5769,-5768,-5766,-5766,-5766,-5763,-5761,-5761,-5759,-5755,-5751,-5751,-5747,-5746,-5744,-5743,-5740,-5739,-5734,-5729,-5728,-5727,-5726,-5725,-5725,-5725,-5723,-5723,-5721,-5721,-5719,-5718,-5714,-5713,-5713,-5709,-5709,-5708,-5707,-5704,-5704,-5703,-5703,-5703,-5702,-5701,-5699,-5698,-5697,-5694,-5694,-5692,-5692,-5688,-5682,-5681,-5677,-5677,-5676,-5674,-5674,-5673,-5671,-5671,-5671,-5671,-5669,-5669,-5667,-5667,-5666,-5666,-5665,-5663,-5658,-5657,-5656,-5655,-5653,-5652,-5651,-5649,-5644,-5643,-5642,-5641,-5640,-5639,-5635,-5634,-5628,-5628,-5626,-5624,-5623,-5622,-5608,-5606,-5604,-5598,-5595,-5592,-5590,-5587,-5586,-5581,-5580,-5577,-5577,-5574,-5571,-5569,-5566,-5566,-5558,-5558,-5558,-5556,-5556,-5551,-5548,-5547,-5546,-5545,-5545,-5545,-5538,-5534,-5534,-5530,-5530,-5529,-5528,-5528,-5528,-5526,-5525,-5523,-5521,-5518,-5513,-5513,-5509,-5508,-5507,-5505,-5502,-5500,-5497,-5496,-5496,-5492,-5491,-5490,-5489,-5488,-5485,-5481,-5476,-5475,-5475,-5475,-5474,-5470,-5466,-5465,-5463,-5462,-5462,-5458,-5458,-5456,-5454,-5452,-5448,-5444,-5443,-5443,-5442,-5441,-5440,-5440,-5438,-5435,-5430,-5425,-5424,-5422,-5421,-5420,-5420,-5419,-5417,-5414,-5413,-5405,-5405,-5404,-5404,-5404,-5401,-5399,-5398,-5395,-5391,-5390,-5389,-5388,-5387,-5382,-5381,-5381,-5377,-5377,-5373,-5372,-5372,-5372,-5368,-5365,-5362,-5360,-5359,-5358,-5358,-5355,-5352,-5352,-5350,-5344,-5343,-5342,-5341,-5339,-5338,-5333,-5331,-5330,-5330,-5329,-5329,-5328,-5326,-5321,-5321,-5319,-5319,-5318,-5309,-5308,-5307,-5307,-5306,-5305,-5304,-5304,-5303,-5302,-5301,-5301,-5299,-5298,-5298,-5296,-5296,-5292,-5290,-5288,-5286,-5284,-5282,-5275,-5274,-5273,-5271,-5270,-5270,-5270,-5266,-5264,-5264,-5263,-5262,-5261,-5259,-5258,-5256,-5255,-5254,-5253,-5252,-5252,-5250,-5249,-5247,-5247,-5246,-5244,-5243,-5242,-5241,-5240,-5239,-5239,-5237,-5233,-5231,-5231,-5230,-5229,-5227,-5227,-5223,-5221,-5221,-5221,-5219,-5217,-5217,-5214,-5210,-5210,-5210,-5209,-5209,-5209,-5207,-5202,-5194,-5187,-5180,-5178,-5177,-5175,-5171,-5171,-5168,-5167,-5163,-5162,-5161,-5159,-5158,-5157,-5157,-5152,-5152,-5150,-5150,-5150,-5146,-5143,-5143,-5140,-5134,-5127,-5126,-5126,-5126,-5122,-5120,-5116,-5114,-5113,-5110,-5109,-5108,-5105,-5102,-5101,-5098,-5096,-5096,-5094,-5093,-5092,-5091,-5091,-5089,-5088,-5083,-5081,-5080,-5080,-5076,-5071,-5067,-5059,-5058,-5057,-5047,-5042,-5042,-5039,-5034,-5032,-5031,-5028,-5024,-5024,-5015,-5015,-5013,-5010,-5008,-5006,-5005,-5002,-4995,-4994,-4994,-4989,-4989,-4984,-4983,-4982,-4980,-4974,-4971,-4968,-4965,-4964,-4963,-4961,-4957,-4957,-4948,-4947,-4945,-4945,-4944,-4943,-4941,-4937,-4937,-4936,-4936,-4935,-4934,-4933,-4933,-4932,-4930,-4928,-4924,-4915,-4915,-4915,-4914,-4914,-4912,-4911,-4911,-4911,-4907,-4906,-4906,-4905,-4904,-4901,-4895,-4894,-4892,-4890,-4890,-4887,-4884,-4883,-4881,-4880,-4879,-4877,-4871,-4866,-4865,-4864,-4862,-4859,-4858,-4856,-4854,-4854,-4851,-4850,-4846,-4844,-4844,-4842,-4842,-4839,-4837,-4836,-4834,-4833,-4828,-4828,-4826,-4824,-4823,-4820,-4819,-4818,-4818,-4816,-4814,-4814,-4808,-4807,-4806,-4806,-4805,-4805,-4803,-4801,-4798,-4798,-4797,-4797,-4796,-4796,-4795,-4794,-4793,-4789,-4783,-4783,-4781,-4780,-4779,-4778,-4774,-4772,-4771,-4765,-4764,-4763,-4760,-4759,-4757,-4757,-4755,-4754,-4751,-4751,-4750,-4749,-4745,-4744,-4742,-4742,-4741,-4741,-4741,-4741,-4740,-4740,-4737,-4729,-4729,-4728,-4727,-4727,-4724,-4721,-4719,-4716,-4711,-4711,-4706,-4702,-4697,-4695,-4693,-4690,-4688,-4688,-4686,-4684,-4681,-4680,-4680,-4680,-4676,-4674,-4674,-4673,-4669,-4668,-4665,-4663,-4661,-4659,-4656,-4653,-4652,-4651,-4650,-4649,-4649,-4646,-4644,-4643,-4642,-4640,-4630,-4628,-4628,-4627,-4622,-4619,-4616,-4615,-4613,-4612,-4608,-4607,-4605,-4604,-4601,-4597,-4594,-4594,-4594,-4592,-4591,-4591,-4588,-4586,-4586,-4585,-4584,-4584,-4578,-4577,-4574,-4571,-4568,-4567,-4565,-4559,-4552,-4550,-4549,-4542,-4541,-4539,-4539,-4538,-4537,-4536,-4534,-4534,-4526,-4526,-4525,-4525,-4523,-4522,-4522,-4520,-4520,-4519,-4518,-4517,-4517,-4516,-4512,-4507,-4502,-4500,-4498,-4495,-4494,-4490,-4488,-4483,-4480,-4479,-4479,-4479,-4475,-4475,-4475,-4474,-4473,-4471,-4462,-4462,-4461,-4458,-4457,-4453,-4453,-4453,-4451,-4448,-4447,-4445,-4444,-4440,-4440,-4437,-4435,-4434,-4432,-4430,-4429,-4425,-4423,-4422,-4422,-4422,-4415,-4415,-4414,-4413,-4413,-4410,-4409,-4409,-4409,-4407,-4406,-4405,-4403,-4402,-4398,-4398,-4396,-4396,-4396,-4393,-4392,-4391,-4390,-4389,-4385,-4381,-4381,-4380,-4380,-4379,-4377,-4377,-4376,-4376,-4372,-4371,-4369,-4367,-4359,-4356,-4349,-4348,-4346,-4346,-4339,-4336,-4336,-4336,-4335,-4335,-4330,-4329,-4324,-4323,-4322,-4313,-4312,-4309,-4306,-4305,-4305,-4304,-4303,-4300,-4299,-4299,-4298,-4298,-4293,-4293,-4290,-4289,-4287,-4285,-4285,-4284,-4281,-4281,-4277,-4275,-4275,-4275,-4273,-4272,-4268,-4265,-4264,-4262,-4259,-4254,-4253,-4253,-4252,-4252,-4249,-4249,-4245,-4243,-4241,-4237,-4234,-4233,-4232,-4230,-4230,-4225,-4222,-4220,-4219,-4217,-4215,-4209,-4205,-4201,-4200,-4200,-4191,-4189,-4186,-4186,-4184,-4181,-4179,-4179,-4177,-4177,-4174,-4174,-4168,-4167,-4165,-4160,-4159,-4159,-4158,-4155,-4154,-4151,-4149,-4147,-4147,-4144,-4142,-4139,-4138,-4131,-4128,-4128,-4127,-4127,-4126,-4124,-4121,-4120,-4120,-4120,-4117,-4116,-4116,-4114,-4112,-4111,-4111,-4109,-4106,-4104,-4097,-4095,-4093,-4093,-4092,-4091,-4090,-4087,-4083,-4079,-4078,-4075,-4072,-4070,-4069,-4068,-4065,-4061,-4061,-4059,-4057,-4056,-4049,-4047,-4045,-4042,-4041,-4035,-4034,-4034,-4028,-4027,-4025,-4025,-4025,-4020,-4012,-4011,-4010,-4010,-4003,-4003,-4000,-3997,-3996,-3995,-3993,-3991,-3990,-3990,-3989,-3986,-3985,-3984,-3981,-3978,-3978,-3973,-3973,-3972,-3970,-3966,-3963,-3958,-3957,-3957,-3954,-3953,-3953,-3949,-3949,-3949,-3943,-3942,-3939,-3936,-3934,-3934,-3928,-3926,-3923,-3922,-3917,-3917,-3917,-3911,-3911,-3908,-3908,-3907,-3907,-3907,-3906,-3906,-3906,-3906,-3905,-3903,-3901,-3901,-3896,-3893,-3891,-3886,-3885,-3884,-3878,-3876,-3876,-3876,-3874,-3874,-3873,-3873,-3871,-3870,-3870,-3868,-3866,-3865,-3864,-3857,-3852,-3850,-3848,-3848,-3844,-3843,-3841,-3841,-3839,-3836,-3835,-3829,-3827,-3827,-3826,-3824,-3823,-3823,-3822,-3822,-3819,-3816,-3812,-3809,-3808,-3805,-3800,-3797,-3794,-3791,-3787,-3782,-3779,-3777,-3776,-3776,-3775,-3775,-3772,-3771,-3769,-3769,-3765,-3764,-3763,-3762,-3755,-3750,-3747,-3747,-3746,-3741,-3741,-3738,-3737,-3734,-3734,-3733,-3731,-3730,-3729,-3728,-3726,-3725,-3724,-3723,-3721,-3720,-3719,-3714,-3712,-3711,-3705,-3704,-3702,-3698,-3698,-3698,-3697,-3697,-3693,-3686,-3684,-3683,-3680,-3679,-3678,-3678,-3676,-3669,-3666,-3664,-3663,-3662,-3658,-3657,-3655,-3653,-3653,-3649,-3648,-3648,-3646,-3645,-3642,-3642,-3639,-3637,-3637,-3634,-3632,-3631,-3631,-3629,-3627,-3627,-3624,-3623,-3617,-3616,-3615,-3607,-3603,-3603,-3602,-3602,-3601,-3601,-3601,-3593,-3590,-3587,-3585,-3585,-3582,-3580,-3577,-3574,-3572,-3568,-3566,-3565,-3563,-3560,-3558,-3557,-3557,-3555,-3553,-3551,-3547,-3545,-3544,-3543,-3542,-3538,-3538,-3536,-3535,-3535,-3532,-3531,-3527,-3527,-3527,-3525,-3523,-3521,-3521,-3519,-3512,-3512,-3509,-3507,-3505,-3502,-3502,-3501,-3496,-3493,-3491,-3489,-3488,-3487,-3486,-3485,-3482,-3481,-3481,-3478,-3475,-3474,-3467,-3466,-3463,-3463,-3462,-3461,-3460,-3460,-3459,-3459,-3456,-3454,-3453,-3453,-3450,-3450,-3440,-3439,-3439,-3438,-3437,-3434,-3434,-3433,-3433,-3432,-3430,-3429,-3424,-3420,-3420,-3419,-3413,-3413,-3409,-3407,-3400,-3394,-3394,-3392,-3392,-3391,-3389,-3387,-3385,-3384,-3383,-3383,-3380,-3379,-3377,-3377,-3377,-3376,-3374,-3373,-3370,-3364,-3363,-3361,-3360,-3355,-3352,-3349,-3348,-3347,-3346,-3346,-3345,-3344,-3343,-3341,-3340,-3338,-3338,-3337,-3335,-3334,-3334,-3332,-3328,-3325,-3324,-3324,-3323,-3322,-3322,-3322,-3319,-3319,-3317,-3317,-3317,-3314,-3311,-3305,-3302,-3301,-3300,-3298,-3296,-3295,-3294,-3293,-3289,-3288,-3288,-3284,-3284,-3281,-3279,-3278,-3276,-3274,-3273,-3272,-3268,-3266,-3262,-3262,-3260,-3254,-3253,-3248,-3246,-3245,-3245,-3243,-3241,-3241,-3240,-3239,-3239,-3237,-3236,-3235,-3234,-3231,-3230,-3225,-3225,-3224,-3221,-3219,-3217,-3215,-3213,-3213,-3213,-3212,-3210,-3208,-3207,-3206,-3204,-3201,-3200,-3198,-3195,-3194,-3193,-3191,-3190,-3183,-3182,-3180,-3175,-3173,-3172,-3170,-3168,-3168,-3167,-3163,-3162,-3162,-3162,-3162,-3161,-3160,-3155,-3150,-3149,-3148,-3148,-3139,-3139,-3135,-3131,-3129,-3129,-3129,-3129,-3126,-3124,-3121,-3121,-3119,-3119,-3118,-3116,-3116,-3113,-3110,-3098,-3098,-3095,-3093,-3093,-3092,-3089,-3087,-3076,-3075,-3071,-3071,-3068,-3067,-3067,-3066,-3063,-3057,-3055,-3055,-3054,-3053,-3053,-3053,-3048,-3046,-3044,-3044,-3044,-3043,-3042,-3035,-3035,-3033,-3033,-3032,-3026,-3026,-3024,-3023,-3019,-3017,-3016,-3012,-3009,-3009,-3006,-3005,-3001,-3000,-2998,-2996,-2994,-2993,-2993,-2992,-2988,-2982,-2981,-2979,-2979,-2978,-2977,-2975,-2974,-2974,-2970,-2970,-2969,-2964,-2963,-2963,-2961,-2960,-2959,-2959,-2958,-2957,-2957,-2957,-2956,-2954,-2954,-2954,-2954,-2953,-2953,-2953,-2952,-2947,-2947,-2945,-2940,-2939,-2938,-2931,-2931,-2930,-2928,-2923,-2920,-2920,-2917,-2916,-2916,-2914,-2912,-2910,-2904,-2901,-2899,-2899,-2898,-2898,-2898,-2897,-2896,-2896,-2894,-2892,-2887,-2885,-2884,-2881,-2881,-2879,-2878,-2877,-2876,-2876,-2875,-2875,-2871,-2866,-2863,-2857,-2856,-2855,-2854,-2853,-2852,-2849,-2848,-2845,-2844,-2839,-2835,-2833,-2833,-2827,-2827,-2823,-2819,-2819,-2818,-2816,-2815,-2815,-2813,-2811,-2811,-2808,-2807,-2806,-2803,-2801,-2801,-2798,-2797,-2796,-2791,-2789,-2789,-2788,-2786,-2785,-2782,-2780,-2780,-2777,-2776,-2776,-2775,-2772,-2769,-2760,-2760,-2758,-2756,-2756,-2755,-2753,-2753,-2749,-2747,-2747,-2741,-2741,-2736,-2734,-2734,-2734,-2733,-2732,-2731,-2725,-2725,-2725,-2722,-2720,-2720,-2718,-2717,-2711,-2710,-2708,-2705,-2705,-2703,-2702,-2699,-2698,-2697,-2695,-2694,-2693,-2692,-2689,-2689,-2689,-2684,-2684,-2681,-2679,-2673,-2671,-2668,-2667,-2666,-2666,-2664,-2664,-2663,-2662,-2661,-2653,-2650,-2650,-2647,-2642,-2640,-2637,-2634,-2631,-2628,-2627,-2627,-2625,-2624,-2620,-2620,-2620,-2620,-2619,-2615,-2612,-2606,-2602,-2600,-2598,-2596,-2590,-2588,-2588,-2586,-2583,-2582,-2575,-2575,-2573,-2572,-2565,-2564,-2564,-2562,-2561,-2559,-2554,-2551,-2550,-2549,-2548,-2547,-2542,-2540,-2536,-2535,-2534,-2533,-2530,-2529,-2529,-2528,-2526,-2525,-2523,-2520,-2519,-2517,-2517,-2513,-2512,-2503,-2502,-2499,-2498,-2498,-2496,-2495,-2492,-2491,-2491,-2491,-2491,-2490,-2489,-2489,-2486,-2483,-2483,-2482,-2482,-2480,-2480,-2479,-2477,-2476,-2476,-2475,-2473,-2472,-2464,-2463,-2462,-2457,-2457,-2455,-2453,-2444,-2442,-2429,-2424,-2424,-2422,-2422,-2422,-2421,-2421,-2419,-2418,-2418,-2415,-2414,-2412,-2411,-2407,-2407,-2403,-2397,-2393,-2393,-2390,-2390,-2388,-2387,-2382,-2382,-2381,-2378,-2375,-2370,-2366,-2365,-2365,-2364,-2363,-2363,-2362,-2358,-2358,-2354,-2345,-2343,-2341,-2340,-2339,-2337,-2328,-2326,-2325,-2325,-2323,-2319,-2319,-2317,-2314,-2313,-2312,-2308,-2308,-2307,-2305,-2303,-2300,-2298,-2298,-2297,-2293,-2293,-2292,-2289,-2288,-2286,-2283,-2282,-2280,-2277,-2273,-2272,-2271,-2267,-2266,-2265,-2263,-2262,-2262,-2260,-2260,-2260,-2257,-2257,-2255,-2254,-2252,-2250,-2250,-2248,-2247,-2247,-2247,-2246,-2246,-2244,-2242,-2242,-2242,-2239,-2233,-2232,-2226,-2221,-2220,-2219,-2218,-2218,-2216,-2216,-2215,-2215,-2212,-2212,-2211,-2210,-2208,-2206,-2202,-2200,-2199,-2197,-2196,-2195,-2192,-2187,-2184,-2180,-2174,-2174,-2173,-2173,-2173,-2172,-2168,-2166,-2166,-2165,-2165,-2162,-2160,-2158,-2158,-2157,-2152,-2149,-2148,-2147,-2146,-2146,-2146,-2144,-2140,-2138,-2133,-2133,-2131,-2129,-2125,-2120,-2116,-2112,-2112,-2106,-2103,-2103,-2100,-2096,-2096,-2096,-2095,-2093,-2092,-2091,-2088,-2088,-2085,-2085,-2085,-2084,-2082,-2082,-2081,-2079,-2078,-2077,-2076,-2072,-2071,-2070,-2068,-2067,-2066,-2065,-2065,-2060,-2060,-2059,-2058,-2056,-2054,-2052,-2047,-2047,-2045,-2044,-2043,-2039,-2038,-2037,-2036,-2036,-2034,-2030,-2028,-2027,-2025,-2024,-2022,-2017,-2017,-2013,-2010,-2009,-2009,-2007,-2006,-2006,-2004,-2003,-2000,-1998,-1998,-1997,-1997,-1997,-1995,-1995,-1994,-1991,-1989,-1987,-1986,-1976,-1973,-1972,-1970,-1968,-1967,-1966,-1965,-1962,-1961,-1953,-1947,-1946,-1941,-1940,-1940,-1937,-1934,-1932,-1929,-1928,-1925,-1923,-1923,-1923,-1922,-1920,-1919,-1918,-1913,-1910,-1910,-1910,-1909,-1906,-1897,-1886,-1884,-1883,-1882,-1882,-1880,-1873,-1871,-1870,-1868,-1867,-1863,-1861,-1861,-1858,-1853,-1852,-1851,-1849,-1845,-1838,-1833,-1831,-1830,-1820,-1820,-1818,-1818,-1816,-1816,-1815,-1814,-1813,-1810,-1809,-1809,-1808,-1808,-1808,-1800,-1796,-1796,-1794,-1794,-1791,-1791,-1786,-1785,-1783,-1781,-1777,-1773,-1769,-1768,-1767,-1767,-1766,-1765,-1763,-1761,-1759,-1758,-1755,-1754,-1737,-1736,-1735,-1734,-1729,-1729,-1727,-1719,-1714,-1714,-1713,-1712,-1710,-1708,-1707,-1706,-1705,-1704,-1698,-1692,-1690,-1688,-1687,-1686,-1685,-1685,-1684,-1677,-1675,-1673,-1671,-1670,-1666,-1665,-1661,-1660,-1659,-1659,-1658,-1657,-1653,-1653,-1649,-1648,-1645,-1645,-1644,-1644,-1643,-1640,-1638,-1638,-1637,-1636,-1634,-1628,-1628,-1628,-1627,-1623,-1623,-1622,-1618,-1611,-1610,-1607,-1606,-1600,-1597,-1597,-1597,-1592,-1592,-1589,-1589,-1588,-1586,-1586,-1584,-1582,-1582,-1581,-1581,-1579,-1578,-1578,-1578,-1576,-1576,-1576,-1569,-1568,-1564,-1563,-1561,-1554,-1553,-1553,-1552,-1551,-1545,-1543,-1540,-1536,-1529,-1521,-1517,-1514,-1514,-1514,-1513,-1512,-1512,-1509,-1508,-1508,-1506,-1503,-1500,-1499,-1498,-1495,-1494,-1493,-1489,-1489,-1488,-1486,-1485,-1482,-1469,-1467,-1464,-1462,-1457,-1450,-1449,-1448,-1446,-1441,-1440,-1439,-1436,-1436,-1434,-1430,-1429,-1428,-1426,-1419,-1418,-1415,-1415,-1411,-1411,-1406,-1404,-1403,-1403,-1401,-1398,-1396,-1394,-1393,-1390,-1389,-1388,-1386,-1385,-1385,-1384,-1381,-1380,-1378,-1378,-1367,-1365,-1365,-1364,-1363,-1362,-1361,-1359,-1357,-1356,-1354,-1351,-1350,-1350,-1350,-1349,-1345,-1343,-1339,-1337,-1337,-1333,-1333,-1332,-1331,-1331,-1330,-1328,-1327,-1324,-1322,-1318,-1317,-1312,-1309,-1308,-1308,-1305,-1300,-1300,-1299,-1299,-1297,-1296,-1295,-1290,-1284,-1280,-1275,-1274,-1271,-1267,-1266,-1264,-1263,-1262,-1261,-1256,-1255,-1250,-1243,-1242,-1242,-1242,-1237,-1237,-1236,-1231,-1230,-1228,-1223,-1219,-1218,-1217,-1217,-1216,-1214,-1212,-1212,-1207,-1199,-1197,-1196,-1195,-1192,-1186,-1186,-1185,-1178,-1177,-1166,-1166,-1166,-1165,-1163,-1162,-1158,-1147,-1146,-1145,-1145,-1140,-1139,-1138,-1136,-1134,-1129,-1123,-1119,-1119,-1119,-1118,-1117,-1117,-1116,-1114,-1105,-1105,-1104,-1099,-1099,-1099,-1098,-1095,-1093,-1092,-1091,-1091,-1091,-1089,-1088,-1088,-1078,-1076,-1073,-1065,-1062,-1055,-1054,-1054,-1046,-1039,-1037,-1036,-1029,-1028,-1023,-1020,-1019,-1014,-1012,-1008,-1005,-1004,-998,-991,-987,-984,-979,-979,-979,-976,-974,-970,-964,-956,-954,-954,-954,-952,-952,-952,-948,-944,-943,-939,-938,-937,-937,-935,-929,-925,-925,-924,-923,-922,-917,-912,-911,-909,-907,-903,-902,-900,-900,-897,-896,-896,-896,-896,-896,-891,-891,-890,-890,-886,-879,-879,-869,-867,-867,-865,-865,-865,-864,-863,-861,-861,-857,-856,-851,-850,-850,-850,-848,-845,-843,-842,-840,-834,-833,-832,-831,-827,-825,-825,-823,-822,-820,-820,-817,-817,-816,-816,-813,-810,-806,-803,-801,-794,-794,-794,-793,-785,-784,-783,-783,-782,-781,-780,-769,-769,-767,-765,-765,-763,-760,-759,-758,-757,-755,-751,-750,-749,-747,-744,-743,-741,-741,-735,-733,-731,-727,-723,-719,-715,-714,-713,-712,-711,-710,-708,-707,-704,-703,-697,-697,-696,-696,-693,-690,-690,-683,-682,-681,-676,-672,-664,-664,-664,-664,-663,-661,-661,-659,-655,-655,-654,-651,-650,-650,-646,-641,-638,-635,-632,-632,-631,-627,-626,-625,-625,-623,-623,-622,-620,-614,-613,-610,-608,-608,-607,-607,-606,-606,-603,-602,-602,-600,-599,-599,-594,-593,-592,-591,-587,-579,-576,-576,-574,-570,-567,-566,-565,-564,-563,-562,-558,-552,-550,-547,-541,-540,-540,-538,-538,-538,-535,-532,-531,-526,-525,-520,-518,-517,-517,-515,-515,-508,-506,-504,-502,-494,-493,-485,-482,-478,-475,-472,-470,-469,-469,-467,-463,-462,-457,-454,-454,-448,-448,-447,-446,-444,-442,-439,-435,-434,-432,-430,-425,-421,-418,-416,-415,-413,-412,-411,-406,-403,-395,-394,-391,-390,-387,-386,-382,-382,-378,-375,-373,-372,-370,-368,-362,-354,-350,-350,-348,-345,-345,-344,-340,-333,-333,-333,-332,-332,-330,-329,-323,-318,-312,-311,-310,-307,-306,-303,-303,-301,-298,-298,-295,-294,-294,-292,-291,-290,-284,-282,-274,-270,-267,-266,-262,-259,-259,-257,-257,-255,-251,-251,-251,-250,-250,-242,-239,-237,-237,-236,-236,-235,-233,-232,-229,-227,-223,-215,-214,-213,-213,-212,-210,-204,-203,-198,-197,-196,-194,-186,-185,-184,-183,-180,-178,-175,-172,-171,-168,-164,-162,-157,-152,-149,-147,-143,-139,-139,-139,-137,-136,-134,-134,-131,-130,-129,-128,-127,-120,-120,-119,-118,-107,-106,-101,-99,-98,-95,-94,-89,-88,-83,-81,-80,-78,-78,-75,-74,-73,-68,-67,-59,-56,-55,-53,-50,-44,-42,-39,-38,-38,-36,-33,-33,-32,-31,-27,-25,-23,-22,-20,-14,-14,-13,-11,-9,-7,-7,-4,-2,-2,0,2,4,8,9,9,10,10,12,14,17,18,18,19,19,25,29,38,40,42,42,42,45,46,46,47,47,47,49,51,52,55,61,61,62,62,66,67,69,71,73,77,78,80,82,85,85,86,90,91,96,97,98,98,99,100,103,104,106,107,108,113,114,115,116,118,119,124,125,127,128,129,130,131,132,132,133,134,134,135,140,141,142,142,143,143,143,158,163,164,164,164,167,169,174,180,181,181,182,184,186,189,189,191,191,196,198,199,200,203,205,208,212,213,213,215,217,218,221,223,223,224,227,227,227,228,229,229,231,239,244,244,245,246,254,256,256,260,264,267,271,274,275,275,276,276,287,288,288,289,293,296,297,297,298,299,301,305,307,308,309,314,316,319,323,323,331,332,333,335,337,338,341,342,342,344,347,350,353,353,354,356,358,360,361,363,366,367,370,371,373,373,373,374,375,378,379,379,383,384,385,385,386,392,395,399,401,401,403,405,405,406,406,408,412,412,412,414,414,414,415,421,422,433,434,434,440,441,442,442,442,442,447,447,448,453,455,456,456,456,457,460,464,464,465,466,467,469,471,474,475,475,477,479,481,484,485,485,486,486,487,488,490,490,490,492,495,496,497,499,500,500,505,505,506,507,510,511,511,512,512,512,518,524,524,528,529,534,535,535,536,536,537,540,543,544,545,547,548,553,556,557,559,561,569,571,571,577,587,590,594,594,594,595,596,596,597,603,604,604,605,606,611,613,614,616,617,618,622,625,630,632,633,637,642,643,647,648,648,650,653,654,655,655,663,665,665,666,667,671,671,672,675,675,676,681,681,684,689,690,691,693,693,693,694,695,702,703,706,707,715,717,724,725,727,728,731,732,734,735,739,743,744,746,747,749,752,753,753,757,757,759,760,768,768,768,773,775,779,781,783,783,791,794,795,795,797,798,799,801,802,802,802,803,804,805,808,808,812,812,813,813,815,817,819,821,824,826,831,832,832,833,834,835,838,839,841,845,850,852,854,854,861,864,867,875,880,883,884,887,890,891,892,893,893,894,895,903,905,906,908,909,913,915,916,918,919,919,928,934,935,936,940,945,949,954,955,956,957,960,962,962,964,965,966,969,971,975,977,978,981,984,984,986,991,991,994,994,995,996,997,1002,1004,1005,1005,1006,1007,1008,1010,1012,1014,1015,1017,1017,1018,1020,1020,1020,1022,1023,1025,1025,1027,1028,1030,1032,1033,1037,1039,1046,1047,1047,1049,1050,1054,1056,1058,1060,1068,1071,1071,1071,1072,1081,1081,1088,1089,1090,1090,1091,1092,1092,1095,1097,1101,1105,1106,1107,1108,1109,1111,1112,1116,1119,1120,1120,1121,1127,1128,1131,1132,1133,1134,1144,1148,1148,1155,1155,1155,1159,1162,1167,1169,1172,1173,1173,1173,1173,1174,1175,1176,1176,1178,1181,1186,1191,1191,1195,1196,1196,1196,1197,1197,1199,1200,1206,1208,1210,1211,1213,1216,1218,1220,1225,1231,1233,1237,1239,1240,1240,1241,1241,1245,1245,1245,1247,1250,1250,1250,1251,1252,1254,1254,1255,1258,1261,1264,1264,1271,1274,1274,1277,1278,1280,1281,1284,1285,1291,1292,1294,1294,1300,1302,1305,1305,1306,1308,1313,1315,1315,1316,1318,1326,1328,1330,1335,1343,1346,1349,1350,1350,1351,1351,1353,1353,1355,1357,1357,1359,1362,1365,1366,1367,1370,1371,1374,1376,1377,1384,1387,1388,1393,1398,1400,1401,1402,1404,1404,1408,1410,1412,1414,1414,1414,1417,1420,1422,1423,1423,1424,1424,1430,1430,1434,1435,1438,1439,1440,1440,1442,1443,1443,1445,1446,1450,1452,1455,1455,1457,1460,1461,1461,1462,1465,1465,1469,1473,1473,1474,1477,1480,1486,1487,1487,1488,1488,1489,1494,1495,1496,1497,1497,1503,1503,1505,1506,1509,1511,1511,1511,1512,1518,1518,1519,1519,1520,1521,1522,1522,1523,1526,1528,1529,1529,1532,1532,1533,1534,1537,1539,1540,1542,1543,1544,1549,1553,1555,1556,1557,1559,1561,1562,1562,1563,1564,1569,1571,1572,1574,1574,1575,1583,1584,1585,1585,1587,1588,1588,1588,1591,1592,1592,1592,1594,1596,1596,1597,1597,1600,1600,1602,1603,1604,1606,1606,1606,1608,1611,1611,1611,1611,1613,1615,1617,1618,1619,1619,1619,1619,1622,1625,1625,1626,1626,1626,1628,1629,1634,1637,1638,1642,1642,1645,1647,1647,1649,1650,1650,1650,1654,1656,1656,1658,1659,1661,1662,1663,1667,1667,1672,1675,1676,1679,1681,1684,1685,1685,1687,1688,1693,1694,1702,1703,1706,1707,1708,1716,1717,1718,1719,1719,1720,1723,1723,1724,1727,1729,1731,1733,1736,1738,1742,1742,1744,1745,1749,1755,1757,1761,1766,1766,1767,1770,1770,1770,1770,1774,1775,1778,1778,1779,1780,1780,1781,1781,1781,1781,1782,1782,1787,1789,1789,1791,1794,1794,1794,1797,1798,1798,1802,1806,1807,1808,1810,1811,1812,1817,1820,1821,1822,1822,1822,1826,1826,1827,1828,1830,1832,1833,1835,1842,1847,1849,1850,1851,1855,1861,1862,1864,1864,1865,1868,1868,1873,1875,1877,1877,1877,1877,1878,1879,1882,1883,1883,1884,1885,1889,1890,1890,1892,1896,1901,1903,1904,1906,1908,1908,1912,1913,1914,1915,1915,1916,1921,1922,1928,1929,1936,1937,1940,1947,1948,1949,1950,1954,1960,1963,1966,1967,1971,1971,1975,1976,1978,1980,1981,1982,1983,1985,1985,1986,1987,1989,1989,1991,1993,1994,1995,1996,1999,1999,2000,2001,2003,2003,2004,2004,2005,2006,2006,2006,2007,2007,2009,2012,2016,2019,2019,2021,2024,2025,2027,2028,2029,2030,2032,2033,2034,2038,2038,2043,2043,2044,2045,2045,2046,2050,2051,2053,2054,2057,2058,2060,2061,2061,2063,2064,2066,2067,2069,2073,2074,2075,2075,2076,2077,2077,2078,2082,2084,2087,2087,2090,2092,2100,2101,2103,2106,2110,2114,2118,2120,2123,2128,2132,2133,2133,2134,2135,2137,2144,2146,2148,2150,2150,2152,2153,2154,2155,2156,2157,2158,2160,2161,2162,2165,2167,2173,2178,2178,2178,2179,2183,2184,2185,2188,2189,2189,2190,2195,2197,2198,2199,2199,2201,2208,2213,2214,2216,2219,2220,2221,2222,2224,2224,2225,2231,2232,2241,2245,2252,2253,2253,2254,2256,2256,2258,2259,2262,2265,2267,2267,2268,2273,2274,2276,2276,2277,2277,2279,2281,2286,2287,2291,2292,2293,2295,2295,2298,2300,2301,2301,2301,2302,2303,2305,2308,2309,2312,2313,2313,2315,2315,2322,2322,2323,2324,2326,2327,2327,2329,2330,2331,2331,2333,2334,2337,2342,2345,2346,2347,2349,2351,2351,2353,2354,2355,2356,2358,2358,2358,2359,2361,2368,2371,2376,2381,2381,2383,2383,2384,2385,2385,2386,2386,2387,2391,2392,2392,2396,2397,2401,2402,2404,2406,2413,2413,2416,2418,2418,2421,2422,2423,2423,2426,2433,2436,2438,2439,2443,2445,2454,2456,2458,2460,2461,2465,2471,2471,2472,2472,2477,2482,2485,2485,2487,2487,2490,2490,2491,2492,2494,2494,2498,2501,2502,2503,2505,2508,2508,2509,2509,2510,2512,2514,2514,2517,2517,2518,2520,2523,2524,2525,2529,2530,2535,2536,2537,2538,2538,2539,2540,2542,2543,2543,2546,2547,2547,2547,2549,2550,2551,2552,2558,2558,2561,2563,2564,2565,2570,2573,2575,2577,2580,2581,2583,2584,2587,2590,2595,2599,2606,2607,2609,2610,2611,2613,2613,2617,2617,2618,2621,2624,2626,2626,2627,2631,2632,2637,2638,2639,2642,2642,2642,2652,2659,2660,2663,2667,2667,2674,2675,2680,2680,2680,2681,2685,2687,2688,2690,2692,2694,2694,2695,2704,2704,2705,2707,2707,2707,2708,2708,2710,2714,2718,2726,2727,2727,2732,2732,2737,2737,2738,2740,2743,2745,2749,2750,2765,2766,2766,2768,2768,2770,2775,2775,2777,2782,2782,2783,2786,2789,2792,2793,2794,2795,2799,2801,2805,2805,2808,2814,2814,2814,2815,2815,2818,2818,2819,2819,2820,2821,2822,2827,2832,2839,2839,2840,2842,2843,2844,2844,2844,2844,2846,2852,2854,2858,2859,2859,2861,2862,2863,2864,2865,2866,2866,2868,2873,2880,2883,2884,2884,2885,2885,2886,2886,2892,2892,2896,2899,2902,2910,2911,2911,2916,2920,2921,2924,2927,2935,2936,2940,2941,2944,2945,2948,2950,2951,2955,2955,2957,2958,2959,2960,2960,2960,2960,2964,2965,2966,2970,2974,2974,2979,2980,2980,2980,2981,2982,2983,2986,2988,2991,2992,2992,2993,2997,2998,2998,3005,3009,3009,3011,3012,3012,3012,3017,3019,3021,3022,3023,3025,3027,3028,3031,3031,3032,3038,3038,3039,3042,3048,3049,3049,3050,3054,3056,3057,3062,3062,3063,3067,3067,3070,3071,3071,3071,3072,3073,3074,3074,3076,3078,3080,3084,3085,3085,3087,3088,3089,3092,3094,3097,3101,3103,3105,3107,3108,3109,3109,3114,3116,3119,3122,3123,3125,3126,3138,3143,3150,3154,3154,3157,3158,3159,3159,3164,3167,3173,3173,3173,3175,3177,3180,3180,3188,3190,3197,3203,3203,3204,3207,3210,3213,3216,3223,3225,3233,3238,3238,3239,3239,3239,3239,3244,3246,3247,3248,3248,3248,3249,3251,3251,3253,3257,3260,3260,3261,3262,3264,3265,3270,3274,3274,3275,3276,3277,3277,3278,3281,3290,3291,3292,3292,3293,3293,3300,3301,3307,3310,3317,3319,3321,3325,3329,3335,3336,3336,3337,3338,3340,3341,3341,3343,3347,3349,3349,3353,3353,3354,3356,3357,3357,3358,3361,3363,3364,3366,3370,3371,3372,3374,3375,3375,3376,3379,3380,3380,3388,3392,3398,3402,3403,3403,3405,3407,3409,3412,3412,3419,3425,3428,3428,3429,3431,3432,3432,3437,3437,3440,3442,3444,3446,3452,3452,3459,3465,3467,3467,3470,3474,3479,3479,3481,3483,3483,3483,3485,3488,3489,3490,3497,3499,3503,3505,3508,3510,3512,3513,3513,3514,3515,3517,3518,3519,3520,3521,3532,3534,3536,3536,3544,3545,3545,3548,3549,3550,3551,3553,3554,3556,3564,3564,3567,3570,3571,3571,3574,3578,3582,3582,3584,3586,3586,3588,3594,3598,3598,3598,3601,3604,3604,3607,3610,3611,3611,3612,3615,3618,3632,3632,3632,3632,3634,3640,3643,3647,3647,3649,3650,3654,3655,3659,3659,3662,3663,3665,3665,3666,3669,3669,3674,3675,3675,3676,3679,3681,3681,3682,3682,3682,3683,3684,3685,3685,3686,3689,3690,3690,3692,3696,3697,3697,3698,3698,3699,3700,3703,3706,3709,3710,3710,3711,3712,3714,3715,3715,3715,3721,3724,3727,3727,3732,3733,3736,3737,3738,3738,3740,3740,3741,3755,3756,3756,3757,3758,3762,3766,3767,3768,3774,3774,3774,3774,3776,3776,3777,3782,3783,3783,3785,3786,3788,3788,3789,3789,3793,3793,3795,3796,3796,3797,3800,3801,3804,3806,3806,3814,3815,3815,3817,3817,3817,3821,3821,3823,3823,3824,3827,3829,3831,3832,3835,3835,3836,3837,3842,3843,3846,3846,3846,3849,3854,3862,3863,3864,3864,3865,3866,3867,3867,3869,3869,3869,3870,3871,3872,3872,3873,3874,3879,3882,3885,3887,3888,3888,3889,3892,3899,3901,3902,3903,3903,3904,3912,3916,3918,3922,3924,3929,3931,3933,3935,3935,3935,3936,3942,3944,3947,3951,3953,3953,3958,3961,3972,3972,3975,3976,3977,3978,3983,3985,3986,3988,3992,3992,3995,3999,4002,4002,4003,4003,4004,4005,4006,4008,4009,4009,4012,4014,4014,4015,4016,4016,4018,4021,4021,4023,4025,4025,4027,4030,4032,4033,4033,4035,4035,4040,4043,4045,4045,4049,4050,4050,4051,4052,4052,4053,4053,4058,4059,4060,4062,4063,4066,4069,4072,4075,4075,4075,4078,4079,4081,4083,4090,4091,4093,4093,4094,4095,4095,4097,4101,4104,4104,4106,4106,4110,4111,4112,4112,4113,4113,4115,4116,4118,4119,4120,4121,4122,4123,4124,4124,4125,4125,4125,4126,4127,4133,4134,4146,4150,4154,4157,4158,4158,4159,4163,4167,4168,4169,4171,4172,4175,4178,4180,4181,4185,4187,4187,4197,4199,4200,4202,4207,4208,4209,4209,4213,4216,4217,4218,4220,4223,4228,4230,4234,4236,4237,4242,4242,4247,4248,4249,4251,4251,4255,4255,4257,4257,4259,4263,4264,4265,4265,4271,4272,4275,4276,4277,4277,4279,4279,4280,4280,4285,4285,4286,4288,4291,4294,4299,4299,4300,4301,4301,4304,4308,4308,4311,4312,4313,4320,4320,4325,4328,4329,4329,4329,4331,4331,4332,4334,4335,4335,4337,4337,4338,4346,4346,4347,4347,4349,4352,4353,4356,4363,4365,4367,4372,4372,4373,4376,4379,4380,4382,4383,4384,4386,4387,4388,4390,4392,4394,4395,4396,4398,4400,4403,4408,4411,4411,4412,4413,4414,4415,4415,4418,4419,4426,4428,4429,4431,4433,4437,4439,4447,4451,4456,4456,4457,4459,4460,4461,4461,4461,4463,4463,4465,4470,4471,4475,4477,4477,4478,4480,4484,4486,4488,4489,4492,4495,4496,4502,4504,4506,4508,4509,4511,4519,4520,4524,4527,4528,4533,4533,4537,4538,4540,4541,4543,4544,4546,4549,4551,4552,4559,4561,4562,4567,4567,4569,4570,4574,4579,4580,4582,4583,4585,4586,4595,4596,4598,4599,4599,4600,4603,4605,4608,4610,4611,4612,4616,4619,4621,4621,4621,4628,4629,4631,4633,4636,4636,4637,4639,4642,4647,4647,4651,4651,4653,4659,4659,4661,4664,4668,4671,4672,4678,4678,4679,4682,4685,4685,4686,4686,4687,4687,4687,4688,4689,4693,4697,4699,4699,4701,4702,4705,4705,4705,4707,4707,4708,4717,4719,4719,4719,4720,4725,4726,4727,4732,4732,4737,4737,4740,4744,4747,4748,4751,4751,4757,4757,4757,4762,4762,4763,4764,4764,4766,4768,4769,4770,4774,4774,4776,4779,4783,4785,4786,4789,4789,4789,4793,4793,4795,4796,4797,4798,4810,4812,4812,4814,4817,4818,4820,4820,4821,4822,4822,4823,4824,4828,4832,4835,4835,4836,4839,4843,4843,4844,4846,4847,4847,4851,4852,4853,4855,4857,4858,4858,4860,4867,4867,4868,4868,4869,4873,4874,4876,4877,4878,4882,4884,4886,4887,4887,4888,4889,4893,4893,4894,4898,4899,4900,4901,4902,4905,4907,4910,4911,4911,4911,4914,4915,4918,4918,4920,4921,4922,4924,4924,4925,4930,4931,4934,4934,4940,4942,4942,4944,4945,4946,4947,4951,4952,4953,4955,4960,4960,4965,4969,4969,4973,4975,4979,4984,4988,4989,4991,4997,5002,5005,5006,5009,5014,5014,5014,5015,5015,5018,5020,5022,5030,5036,5037,5042,5042,5042,5042,5045,5047,5047,5048,5052,5053,5054,5055,5057,5057,5057,5057,5059,5060,5063,5064,5067,5067,5067,5068,5069,5071,5074,5078,5081,5083,5086,5092,5093,5098,5101,5102,5102,5102,5103,5107,5109,5114,5115,5120,5121,5122,5122,5130,5132,5137,5138,5138,5141,5142,5143,5145,5157,5157,5164,5164,5168,5170,5171,5172,5173,5174,5175,5176,5180,5180,5182,5182,5183,5184,5186,5188,5190,5191,5193,5194,5194,5198,5202,5203,5208,5210,5212,5214,5218,5220,5225,5225,5225,5226,5231,5243,5244,5246,5248,5248,5249,5250,5251,5251,5254,5261,5262,5264,5266,5266,5269,5270,5277,5277,5277,5277,5281,5283,5283,5285,5291,5294,5294,5294,5295,5298,5299,5300,5301,5304,5305,5306,5310,5313,5314,5314,5315,5316,5316,5318,5320,5321,5323,5323,5325,5325,5330,5331,5332,5335,5338,5341,5344,5345,5347,5349,5351,5359,5360,5362,5365,5366,5366,5371,5372,5373,5375,5379,5380,5390,5391,5391,5392,5395,5396,5398,5398,5406,5407,5407,5410,5415,5415,5416,5418,5418,5419,5423,5425,5430,5434,5436,5440,5440,5441,5442,5442,5442,5445,5445,5446,5447,5448,5451,5452,5458,5459,5459,5459,5461,5461,5465,5465,5466,5469,5473,5474,5479,5481,5481,5486,5495,5496,5499,5499,5499,5501,5503,5503,5505,5506,5510,5510,5510,5513,5514,5517,5517,5517,5521,5521,5522,5524,5526,5526,5526,5527,5527,5528,5535,5537,5537,5537,5539,5539,5540,5543,5546,5547,5547,5549,5549,5553,5558,5560,5561,5563,5571,5572,5572,5573,5583,5590,5590,5593,5594,5595,5596,5596,5600,5605,5606,5606,5606,5608,5608,5612,5614,5614,5618,5622,5625,5629,5631,5631,5632,5633,5635,5640,5640,5642,5643,5643,5644,5645,5645,5646,5646,5647,5649,5652,5653,5660,5661,5665,5667,5667,5668,5672,5672,5672,5673,5674,5674,5677,5678,5680,5680,5684,5691,5696,5698,5699,5699,5702,5702,5705,5706,5707,5711,5713,5716,5716,5717,5717,5723,5723,5730,5731,5731,5732,5732,5732,5736,5737,5740,5740,5741,5742,5745,5745,5745,5747,5749,5750,5750,5750,5751,5755,5759,5760,5761,5764,5768,5770,5773,5774,5784,5785,5800,5803,5804,5806,5808,5811,5813,5815,5815,5816,5816,5817,5820,5821,5823,5825,5826,5829,5832,5832,5834,5839,5840,5843,5845,5847,5848,5849,5850,5854,5855,5857,5860,5861,5862,5863,5864,5864,5865,5866,5866,5867,5872,5874,5878,5878,5882,5890,5890,5892,5892,5897,5900,5902,5903,5906,5907,5908,5910,5911,5914,5914,5915,5917,5920,5926,5927,5928,5929,5930,5932,5935,5936,5941,5942,5943,5944,5947,5947,5947,5958,5959,5961,5962,5962,5963,5965,5970,5974,5975,5980,5980,5986,5988,5990,5990,5992,5993,5994,5995,5996,5999,6000,6000,6001,6002,6003,6006,6008,6010,6013,6013,6017,6024,6027,6030,6031,6032,6033,6036,6040,6040,6040,6041,6044,6044,6044,6046,6046,6046,6055,6057,6057,6058,6058,6059,6060,6060,6063,6064,6068,6069,6069,6071,6075,6075,6079,6080,6084,6091,6096,6100,6102,6104,6105,6107,6108,6111,6111,6116,6118,6119,6121,6123,6126,6129,6134,6137,6138,6139,6139,6140,6140,6143,6143,6144,6145,6145,6147,6149,6150,6152,6152,6155,6160,6161,6161,6161,6162,6162,6165,6166,6169,6170,6170,6170,6172,6172,6174,6178,6179,6182,6183,6185,6185,6186,6187,6188,6189,6191,6197,6199,6201,6204,6212,6213,6214,6217,6219,6227,6230,6232,6233,6237,6237,6239,6239,6241,6242,6242,6242,6243,6244,6244,6245,6246,6246,6250,6255,6259,6261,6265,6266,6266,6267,6270,6272,6277,6279,6283,6284,6284,6284,6284,6286,6288,6289,6290,6294,6295,6301,6307,6311,6313,6316,6316,6317,6324,6324,6329,6329,6332,6332,6335,6346,6348,6351,6354,6356,6356,6357,6358,6360,6362,6362,6362,6362,6362,6363,6365,6366,6368,6369,6369,6373,6375,6379,6382,6382,6383,6384,6384,6387,6389,6392,6394,6395,6400,6406,6407,6416,6416,6416,6417,6421,6422,6424,6426,6428,6428,6436,6439,6443,6453,6455,6456,6458,6461,6461,6465,6465,6465,6469,6470,6471,6475,6478,6479,6481,6481,6482,6485,6486,6487,6489,6490,6492,6494,6496,6497,6497,6497,6502,6503,6506,6511,6513,6514,6515,6516,6517,6518,6518,6520,6521,6521,6522,6523,6523,6527,6530,6530,6531,6532,6532,6533,6533,6534,6536,6537,6542,6547,6547,6549,6550,6550,6551,6551,6553,6560,6570,6573,6574,6574,6577,6577,6577,6580,6582,6583,6584,6586,6587,6588,6591,6593,6595,6597,6598,6599,6599,6599,6600,6601,6601,6607,6607,6612,6614,6615,6618,6621,6624,6625,6628,6629,6631,6634,6639,6643,6647,6647,6650,6650,6652,6654,6660,6661,6664,6666,6671,6672,6690,6691,6691,6693,6693,6694,6696,6699,6699,6700,6700,6702,6703,6704,6706,6707,6707,6707,6707,6708,6711,6712,6713,6714,6714,6714,6717,6720,6723,6726,6730,6731,6731,6732,6734,6742,6742,6743,6746,6748,6752,6753,6753,6754,6762,6765,6768,6773,6774,6776,6783,6785,6785,6790,6791,6794,6796,6800,6801,6802,6804,6808,6810,6811,6813,6814,6818,6819,6820,6824,6831,6832,6832,6833,6834,6835,6844,6844,6849,6850,6853,6857,6859,6859,6863,6864,6867,6867,6867,6868,6871,6877,6877,6881,6882,6884,6888,6888,6897,6898,6901,6902,6904,6904,6904,6905,6908,6914,6917,6920,6921,6921,6922,6922,6923,6925,6927,6929,6931,6933,6933,6936,6936,6941,6942,6943,6943,6946,6950,6952,6958,6963,6963,6964,6968,6968,6971,6972,6972,6984,6989,6992,6993,6994,6999,7000,7002,7003,7005,7006,7009,7009,7015,7016,7017,7022,7022,7023,7025,7025,7027,7027,7028,7029,7029,7030,7032,7034,7037,7037,7041,7050,7051,7054,7059,7063,7066,7067,7067,7070,7070,7076,7077,7078,7080,7081,7083,7089,7093,7094,7099,7103,7107,7108,7109,7118,7127,7134,7135,7137,7138,7140,7143,7147,7147,7147,7151,7152,7155,7157,7158,7162,7163,7169,7169,7171,7178,7179,7183,7184,7184,7185,7188,7189,7191,7193,7199,7203,7204,7205,7207,7211,7212,7212,7214,7216,7218,7220,7220,7223,7224,7226,7229,7230,7230,7231,7233,7234,7234,7235,7237,7237,7238,7238,7240,7241,7242,7242,7243,7245,7246,7246,7247,7248,7249,7251,7257,7257,7259,7260,7261,7263,7263,7264,7268,7273,7274,7275,7275,7279,7287,7288,7289,7294,7297,7301,7303,7303,7303,7303,7305,7305,7311,7313,7316,7322,7325,7331,7334,7336,7341,7343,7344,7345,7345,7348,7352,7358,7359,7360,7362,7363,7363,7373,7376,7376,7377,7379,7379,7380,7384,7386,7390,7392,7396,7398,7399,7403,7405,7405,7406,7408,7408,7408,7409,7411,7411,7412,7413,7414,7414,7414,7416,7421,7422,7429,7430,7431,7440,7440,7441,7444,7444,7444,7450,7453,7454,7455,7455,7457,7459,7463,7464,7467,7469,7470,7471,7473,7475,7477,7478,7482,7483,7489,7489,7490,7491,7491,7493,7493,7494,7495,7497,7500,7500,7502,7505,7505,7507,7509,7509,7514,7516,7517,7517,7519,7519,7522,7523,7525,7527,7530,7531,7531,7532,7532,7534,7543,7547,7548,7551,7553,7557,7559,7561,7562,7564,7565,7570,7571,7571,7573,7573,7574,7576,7581,7581,7586,7587,7587,7588,7591,7593,7597,7599,7602,7603,7606,7608,7611,7612,7614,7616,7617,7617,7617,7617,7623,7624,7624,7625,7625,7626,7626,7628,7630,7631,7634,7636,7640,7642,7644,7649,7650,7653,7653,7654,7656,7658,7659,7661,7663,7665,7665,7665,7666,7666,7666,7676,7676,7680,7680,7683,7686,7688,7692,7694,7697,7701,7703,7707,7713,7713,7719,7720,7721,7721,7725,7730,7730,7733,7734,7735,7735,7736,7740,7744,7744,7747,7749,7750,7753,7755,7758,7759,7759,7762,7763,7764,7764,7767,7769,7769,7773,7774,7776,7780,7782,7790,7791,7792,7794,7796,7799,7799,7801,7802,7807,7811,7812,7815,7825,7826,7827,7829,7833,7834,7838,7839,7841,7842,7843,7843,7849,7852,7856,7859,7860,7867,7868,7869,7872,7873,7874,7875,7878,7879,7879,7881,7882,7884,7884,7885,7889,7892,7892,7902,7902,7902,7903,7903,7904,7907,7908,7909,7911,7915,7917,7922,7928,7928,7931,7931,7931,7932,7934,7934,7935,7940,7945,7947,7951,7955,7958,7958,7959,7960,7963,7964,7970,7974,7975,7975,7977,7977,7977,7979,7980,7982,7985,7988,7988,7990,7994,7996,7996,7997,8000,8002,8003,8005,8005,8006,8009,8009,8010,8010,8013,8014,8018,8019,8020,8022,8023,8024,8026,8027,8029,8029,8030,8036,8039,8042,8044,8047,8047,8048,8049,8049,8053,8053,8055,8057,8061,8061,8062,8062,8065,8069,8071,8072,8073,8074,8075,8077,8078,8078,8080,8081,8084,8089,8093,8094,8094,8095,8095,8098,8098,8098,8099,8102,8102,8102,8104,8104,8105,8106,8107,8110,8110,8113,8115,8120,8123,8126,8126,8133,8134,8135,8136,8139,8140,8141,8142,8144,8144,8147,8150,8150,8151,8153,8153,8153,8166,8167,8168,8168,8172,8173,8177,8181,8183,8184,8187,8190,8192,8194,8195,8195,8201,8201,8202,8202,8204,8204,8212,8218,8218,8223,8224,8227,8227,8229,8230,8231,8234,8237,8237,8239,8239,8244,8244,8248,8249,8251,8255,8258,8258,8263,8264,8265,8266,8267,8268,8270,8272,8272,8272,8272,8274,8280,8283,8284,8286,8287,8287,8291,8291,8293,8293,8296,8298,8306,8307,8311,8313,8316,8317,8317,8321,8323,8323,8324,8326,8327,8330,8333,8333,8334,8336,8338,8338,8343,8345,8345,8347,8348,8350,8351,8355,8358,8359,8360,8360,8364,8364,8366,8366,8369,8370,8378,8378,8381,8382,8382,8383,8383,8384,8386,8389,8393,8398,8402,8402,8405,8406,8409,8411,8413,8414,8415,8416,8417,8424,8427,8427,8427,8432,8432,8435,8438,8440,8440,8442,8444,8447,8447,8447,8447,8448,8449,8451,8451,8456,8456,8457,8464,8465,8465,8466,8467,8472,8475,8476,8476,8481,8481,8482,8483,8484,8486,8492,8494,8494,8495,8497,8498,8504,8507,8508,8509,8509,8510,8510,8511,8511,8511,8516,8516,8516,8520,8521,8521,8525,8526,8531,8534,8541,8542,8542,8547,8549,8555,8556,8563,8564,8565,8566,8566,8568,8568,8572,8573,8575,8581,8583,8583,8586,8588,8589,8591,8592,8595,8598,8600,8601,8604,8605,8607,8607,8607,8608,8608,8609,8614,8615,8620,8620,8622,8622,8623,8624,8626,8627,8632,8634,8634,8634,8638,8641,8642,8642,8642,8642,8643,8645,8646,8647,8647,8655,8657,8658,8664,8670,8671,8671,8673,8675,8680,8680,8682,8686,8699,8704,8705,8709,8715,8715,8717,8718,8722,8723,8726,8727,8728,8728,8731,8731,8732,8734,8736,8736,8738,8738,8739,8743,8746,8747,8748,8748,8748,8749,8751,8752,8753,8753,8754,8756,8759,8764,8767,8771,8772,8774,8777,8782,8784,8786,8786,8786,8788,8788,8790,8791,8792,8794,8797,8798,8801,8801,8801,8803,8805,8806,8809,8811,8813,8815,8817,8819,8819,8819,8823,8827,8829,8830,8830,8830,8833,8834,8835,8835,8838,8839,8842,8845,8847,8849,8852,8853,8858,8862,8862,8866,8866,8867,8868,8869,8871,8874,8874,8875,8877,8880,8881,8882,8883,8885,8885,8886,8888,8889,8890,8898,8901,8901,8905,8907,8908,8914,8915,8915,8917,8922,8925,8927,8930,8939,8940,8940,8946,8951,8953,8955,8958,8960,8965,8965,8967,8968,8969,8974,8976,8980,8980,8981,8983,8985,8988,8989,8991,8991,8992,8993,8993,8999,9000,9001,9001,9004,9005,9010,9011,9013,9013,9014,9015,9017,9022,9023,9025,9025,9027,9038,9041,9043,9049,9050,9051,9060,9061,9062,9066,9066,9071,9073,9074,9075,9075,9077,9082,9083,9084,9086,9086,9092,9093,9094,9099,9103,9112,9113,9115,9120,9123,9123,9126,9128,9130,9136,9136,9147,9147,9148,9150,9150,9154,9155,9156,9159,9161,9162,9162,9163,9164,9165,9166,9167,9168,9170,9171,9171,9177,9186,9186,9187,9187,9192,9193,9196,9197,9199,9200,9201,9204,9205,9205,9208,9209,9213,9215,9217,9225,9228,9229,9232,9237,9238,9241,9242,9243,9246,9246,9247,9249,9252,9256,9256,9260,9262,9264,9269,9278,9278,9281,9281,9282,9287,9288,9288,9289,9290,9290,9290,9293,9295,9299,9302,9304,9305,9305,9305,9306,9309,9309,9309,9315,9316,9318,9318,9318,9322,9322,9322,9327,9328,9329,9330,9332,9333,9333,9334,9334,9338,9342,9345,9346,9347,9348,9351,9355,9355,9359,9361,9361,9363,9364,9365,9367,9370,9371,9372,9373,9377,9388,9389,9390,9394,9394,9400,9401,9403,9404,9404,9407,9410,9411,9412,9414,9417,9418,9421,9422,9422,9423,9424,9424,9425,9426,9427,9427,9429,9431,9431,9436,9438,9441,9441,9442,9443,9443,9443,9444,9450,9450,9451,9457,9458,9464,9468,9469,9471,9473,9475,9477,9479,9483,9487,9492,9493,9494,9495,9495,9497,9499,9503,9506,9507,9508,9511,9513,9514,9518,9519,9519,9520,9521,9521,9523,9524,9526,9528,9531,9531,9533,9534,9534,9535,9535,9545,9546,9546,9546,9554,9557,9558,9558,9559,9562,9563,9564,9570,9574,9576,9577,9579,9579,9581,9587,9588,9589,9589,9590,9592,9593,9594,9602,9602,9603,9604,9605,9605,9606,9607,9608,9609,9613,9614,9615,9615,9617,9619,9621,9621,9624,9631,9633,9634,9635,9636,9636,9649,9651,9652,9652,9655,9656,9658,9658,9660,9661,9665,9665,9669,9670,9671,9681,9683,9686,9686,9692,9693,9697,9697,9698,9698,9700,9702,9704,9706,9707,9708,9710,9712,9715,9722,9724,9724,9728,9728,9729,9731,9732,9732,9733,9735,9735,9739,9741,9742,9745,9748,9748,9748,9749,9751,9752,9753,9755,9756,9757,9758,9758,9764,9767,9773,9774,9774,9776,9779,9782,9783,9783,9784,9786,9791,9792,9793,9798,9798,9799,9800,9802,9805,9809,9812,9817,9822,9824,9827,9831,9835,9840,9843,9846,9847,9853,9856,9859,9860,9862,9863,9866,9868,9872,9872,9872,9872,9876,9879,9883,9883,9886,9888,9890,9893,9893,9894,9894,9897,9898,9901,9903,9903,9905,9906,9907,9914,9915,9915,9916,9916,9919,9919,9923,9931,9934,9934,9936,9937,9938,9939,9940,9940,9946,9946,9950,9953,9954,9955,9957,9958,9961,9963,9964,9965,9965,9966,9968,9970,9972,9972,9973,9976,9979,9979,9981,9981,9982,9984,9991,9991,9992,9993,9995,9995,9996,9997,9998]

A Better Approach is using the three pointers. It is similar to the Data Structure I #88. Merge Sorted Array. Here we don't even need to square the numbers first. Instead, we create a new array and while comparing the squares at start_idx and end_idx pointers we save them accordingly in the ans array.

Solution:

# @param {Integer[]} nums
# @return {Integer[]}
def sorted_squares(nums)
  ans = [] # final sorted squares; ans means answer
  
  # using the three pointer approach
  # just like the problem in Data Structure I
  # 88. Merge Sorted Array
  
  start_idx = 0
  end_idx = nums.size - 1
  ans_idx = nums.size - 1 # similar to i in problem 88
  
  while start_idx <= end_idx
    if nums[start_idx]**2 > nums[end_idx]**2
      ans[ans_idx] = nums[start_idx]**2
      start_idx += 1
    else
      ans[ans_idx] = nums[end_idx]**2
      end_idx -= 1
    end
    ans_idx -= 1
  end
  
  ans
end