Algorithms_Coursera_Part_III_Programming_Assignment_3_Parts_1_and_2.js

Algorithms_Coursera_Part_III_Programming_Assignment_3_Part_3.js

/* eslint-env node */

/**
* -------------------------- Part 3 -----------------------------
*/

/**
* In this programming problem you'll code up the dynamic programming
* algorithm for computing a maximum-weight independent set of a path graph.
*
* Download the text file below. (mwis.txt)
*
* This file describes the weights of the vertices in a path graph (with the
* weights listed in the order in which vertices appear in the path). It has
* the following format:
* [number_of_vertices]
* [weight of first vertex]
* [weight of second vertex]
* ...
*
* For example, the third line of the file is "6395702" indicating that the
* weight of the second vertex of the graph is 6395702.
*
* Your task in this problem is to run the dynamic programming algorithm (and
* the reconstruction procedure) from lecture on this data set. The question
* is: of the vertices 1, 2, 3, 4, 17, 117, 517, and 997, which ones belong to
* the maximum-weight independent set? (By "vertex 1" we mean the first vertex
* of the graph---there is no vertex 0.) In the box below, enter a 8-bit string,
*  where the ith bit should be 1 if the ith of these 8 vertices is in the
* maximum-weight independent set, and 0 otherwise. For example, if you think
* that the vertices 1, 4, 17, and 517 are in the maximum-weight independent
* set and the other four vertices are not, then you should enter the string
* 10011010 in the box below.
*/

/**
* -------------------------- FILE I/O -----------------------------
*/

const fs = require("fs");

const nodeNumVsWeight = new Map();
let numNodes;

/**
* Parse the text file.
*/
(function getInput() {
  const data = fs.readFileSync("mwis.txt", "utf8");
  const rows = data.split("\n");
  for (let i = 0; i < rows.length; i++) {
    let row = rows[i];
    // Don't include the first row, which is the total number of nodes
    if (i === 0) {
      numNodes = Number(row);
      continue;
    }
    // Get rid of empty row at EOF
    if (i === rows.length - 1) {
      continue;
    }
    // Remove excess white space at the end of the line
    row = row.trim();
    nodeNumVsWeight.set(i, Number(row));
  }
}());

// console.log(nodeNumVsWeight);

/**
* -------------------- DYNAMIC PROGRAMMING ALGORITHM -----------------------
*/

// NOTE: TRY USING CHROME DEVTOOLS DEBUGGER:
// https://medium.com/@paul_irish/debugging-node-js-nightlies-with-chrome-devtools-7c4a1b95ae27

/**
* Pseudocode for Part 3
*/

// Memoize the solutions for previous subproblems, so that A[i] = MWIS of G_i,
// where G_i is the first i vertices of G. (MWIS = maximum weight independent
// set)
const A = [...Array(numNodes)];
A[0] = 0;
A[1] = nodeNumVsWeight.get(1);
for (let i = 2; i <= numNodes; i++) {
  A[i] = Math.max(A[i - 1], (A[i - 2] + nodeNumVsWeight.get(i)));
}

// Perform reconstruction algorithm to obtain the MWIS for G
const S = new Set();
let i = numNodes;
while (i >= 1) {
  if (A[i - 1] >= (A[i - 2] + nodeNumVsWeight.get(i))) {
    // Case 1 wins
    i--;
  } else {
    // Case 2 wins
    S.add(i);
    i -= 2;
  }
}

let maxWeightedSum = 0;
const arrS = Array.from(S.values());
arrS.forEach((node) => {
  maxWeightedSum += nodeNumVsWeight.get(node);
});

console.log(S, maxWeightedSum);

// Output binary result for solution:
let result = "";
const verticesOfInterest = [1, 2, 3, 4, 17, 117, 517, 997];
for (const vertex of verticesOfInterest) {
  if (arrS.includes(vertex)) {
    result += "1";
  } else {
    result += "0";
  }
}
console.log(result);

// Solutions:
// testCase1.txt: S = Set { 10, 8, 6, 4, 2 }, maxWeightedSum = 2616
// testCase2.txt: S = Set { 9, 6, 3, 1 }, maxWeightedSum = 2533
// mwis.txt: result = 10100110

Algorithms_Coursera_Part_III_Programming_Assignment_3_Parts_1_and_2.js

/* eslint-env node */

/**
* -------------------------- Part 1 -----------------------------
*/

/**
* In this programming problem and the next you"ll code up the greedy algorithm
* from the lectures on Huffman coding.
*
* Download the text file below (huffman.txt)
*
* This file describes an instance of the problem. It has the following format:
* [number_of_symbols]
* [weight of symbol #1]
* [weight of symbol #2]
* ...
*
* For example, the third line of the file is "6852892," indicating that the
* weight of the second symbol of the alphabet is 6852892. (We"re using weights
* instead of frequencies, like in the "A More Complex Example" video.)
*
* Your task in this problem is to run the Huffman coding algorithm from lecture
* on this data set. What is the maximum length of a codeword in the resulting
* Huffman code?
*
* ADVICE: If you"re not getting the correct answer, try debugging your algorithm
* using some small test cases. And then post them to the discussion forum!
*
* Pseudocode
* 1. (File I/O section) Convert subtrees file of node weights to a sorted (from
* biggest to smallest) array of arrays, where each array element
* is a subtree
*    1.1 Each symbol starts out as its own subtree (of size 1)
*    1.2. Sort the symbols from largest to smallest probabilities (use a stack)
* 2. While # subtrees >= 2
*   2.1 Pop off the last two symbols from the stack
*   2.2. Merge them into a new subtree (computing their merged weight)
*   2.3. Add the newly merged subtree to the end of the list of subtrees
*   2.4. Resort the list of subtrees array from biggest to smallest in case the
* merge changed the ordering.
* 3. Do a DFS on the resultant tree to compute the max and min leaf depths (for
* parts 1 and 2, respectively)
*/

/**
* -------------------------- FILE I/O -----------------------------
*/

const fs = require("fs");

const subtrees = [];
let numNodes;

/**
* Parse the text file and store it as a:
* 1) sorted array, where each element in the array is the symbol's weight
*/
(function getInput() {
  const data = fs.readFileSync("huffman.txt", "utf8");
  const rows = data.split("\n");
  for (let i = 0; i < rows.length; i++) {
    let row = rows[i];
    // Don"t include the first row, which is the total number of symbols
    if (i === 0) {
      numNodes = Number(row);
      continue;
    }
    // Get rid of empty row at EOF
    if (i === (rows.length - 1)) {
      continue;
    }
    // Remove excess white space at the end of the line
    row = row.trim();
    // Break each row into a tuple of integers
    row = row.split(" ");
    subtrees.push([Number(row)]);
  }
}());

subtrees.sort((a, b) => {
  return (b[0] - a[0]);
});

// console.log(subtrees);

/**
* -------------------- Huffman's coding algorithm -----------------------
*/

/**
* 2. While # subtrees >= 2
*   2.1. Pop off the last two symbols from the sorted array of subtrees
*   2.2. Merge them into a new subtree (computing their merged weight)
*   2.3. Add the newly merged subtree to the end of the list of subtrees
*   2.4. Resort the list of subtrees array from biggest to smallest in case the
*        merge changed the ordering.
* 3. Do a DFS on the resultant tree to compute the max and min leaf depths (for
* parts 1 and 2, respectively)
*/

// The parent node does not contribute to the total weight of a merged subtree
const PARENT_NODE = 0;

// Sum all the values of the elements of the array and return the result
const reducer = (accumulator, currentValue) => {
  return accumulator + currentValue;
};

// IMPORTANT: subtreeL.length should be <= subtreeR.length; this makes
// populating the array representing the merged subtree easier, Since
// it's filled L to R, we won't have any unnecessary `null` values at the
// end of the merged subtree array.
function mergeSubtrees(subtreeL, subtreeR) {
  if (subtreeL.length === 1 && subtreeR.length === 1) {
    return [PARENT_NODE].concat(subtreeL.concat(subtreeR));
  }
  // make sure subtreeR is the largest subtree
  if (subtreeL.length > subtreeR.length) {
    [subtreeL, subtreeR] = [subtreeR, subtreeL];
  }
  // Things get a little more complicated otherwise to represent the binary
  // tree by an array...
  const mergedSubtree = [];
  // The new root node is a new parent node
  mergedSubtree.push(PARENT_NODE);
  // The previous root notes (0th elements in either subtree array) become the
  // left and right child of a new parent node.
  mergedSubtree.push(subtreeL[0]);
  mergedSubtree.push(subtreeR[0]);
  // By convention, we will say subtreeL forms the left subtree while
  // subtreeR forms the right subtree of this new merged subtree; also, 
  // subtreeR is always >= subtreeL.
  // One subtree may be longer than the other (we force this tree to be
  // subtreeR), so we will iterate through the length of subtreeR to
  // ensure all nodes in both subtreeL and subtreeR are visited.
  for (let i = 0; i < subtreeR.length; i++) {
    const subtreeLLeftChildIndex = 2 * i + 1;
    const subtreeLRightChildIndex = 2 * i + 2;
    const subtreeRLeftChildIndex = 2 * i + 1;
    const subtreeRRightChildIndex = 2 * i + 2;
    if (subtreeRRightChildIndex > subtreeR.length) {
      // Every node in the tree is going to have either 0 or 2 children,
      // so it isn't possible for a node to only have a left child.
      // If we've hit the end of the longest subtree array (subtreeR),
      // we know we're done.
      break;
    }
    const subtreeLLeftChild = subtreeL[subtreeLLeftChildIndex];
    const subtreeLRightChild = subtreeL[subtreeLRightChildIndex];
    const subtreeRLeftChild = subtreeR[subtreeRLeftChildIndex];
    const subtreeRRightChild = subtreeR[subtreeRRightChildIndex];
    // Since we are populating the array by tree level left to right,
    // even if a symbol in the left subtree doesn't have children,
    // we need to put something in the array for the array indices
    // to correctly represent the correct left and right children
    // for the right subtree in the case that it is longer than the left.
    const children = [
      subtreeLLeftChild,
      subtreeLRightChild,
      subtreeRLeftChild,
      subtreeRRightChild,
    ];
    for (const child of children) {
      // PARENT_NODE is falsy, so we have to do an extra check for it.
      if (child || child === PARENT_NODE) {
        mergedSubtree.push(child);
      } else {
        mergedSubtree.push(null);
      }
    }
  }
  return mergedSubtree;
}

// Until we have a single, final Huffman coding tree
while (subtrees.length > 1) {
  // 1. Get the next two smallest weight subtrees from our sorted array
  const subtreeL = subtrees.pop();
  const subtreeR = subtrees.pop();
  // 2. Merge them into a new subtree (computing their merged weight)
  const mergedSubtree = mergeSubtrees(subtreeL, subtreeR);
  // 3. Add the newly merged subtree to the end of the list of subtrees
  subtrees.push(mergedSubtree);
  // 4. Re-sort the list of subtrees array from biggest to smallest in case the
  //    merge changed the ordering. The weight of merged subtree is the sum of
  //    all of the merged symbols' weights in it.
  subtrees.sort((a, b) => {
    const sumA = a.reduce(reducer);
    const sumB = b.reduce(reducer);
    return sumB - sumA;
  });
}

// console.log("subtrees: ", subtrees);

/**
* BFS into the resultant tree to obtain the depth of the shallowest leaf node
* (i.e. the shortest bit length symbol)
*/
function getMinBitLength() {
  let level = 0;
  let numElesSinceThisLevelStarted = 0;
  // Recall that subtrees is an Array.array; after all the subtrees have
  // been merged together, there is only one tree left (and one array element
  // left in the subtrees array), the final tree.
  const tree = subtrees[0];
  // Check each node in our array representation of the tree for left and right
  // children. When we hit the first node that has 0 children (left and right
  // child are `null`), this is our shallowest leaf node.
  for (let i = 0; i < tree.length; i++) {
    const numElesAtThisLevel = Math.pow(2, level);
    const leftChildIndex = 2 * i + 1;
    const rightChildIndex = 2 * i + 2;
    const leftChild = tree[leftChildIndex];
    const rightChild = tree[rightChildIndex];
    // PARENT_NODE is falsy (0)
    if (leftChild !== PARENT_NODE && !leftChild
      && rightChild !== PARENT_NODE && !rightChild) {
      // this node has no children; it's a leaf node, and we're done
      break;
    }
    // Since there are 2^l elements for a level l, see what level we are at
    numElesSinceThisLevelStarted++;
    if (numElesSinceThisLevelStarted === numElesAtThisLevel) {
      numElesSinceThisLevelStarted = 0;
      level++;
    }
  }
  return level;
}

/**
* DFS into the resultant tree to obtain the depth of the deepest leaf node
* (i.e. the longest bit length symbol)
*/
function getMaxBitLength() {
  let bitLength = 0;
  let i = 0;
  let rightChildIndex = 2 * i + 2;
  // Recall that subtrees is an Array.array; after all the subtrees have
  // been merged together, there is only one tree left (and one array element
  // left in the subtrees array), the final tree.
  const tree = subtrees[0];
  while (tree[rightChildIndex] || tree[rightChildIndex] === PARENT_NODE) {
    // This node has a left child, move to its index next & increment bit length
    i = rightChildIndex;
    rightChildIndex = 2 * i + 2;
    bitLength++;
  }
  return bitLength;
}

// Since we put `null` in places where a left and right child are missing, the
// subtrees array is always a "full" binary tree (every node other than the
// leaves has two children). This lets us traverse the tree with its array
// representation easily.
// Since by convention we always said the left subtree is the smaller subtree
// and the right subtree is the larger subtree when merging them, to get
// the shortest bit length symbol, we just need to do a BFS on the tree until
// we hit our first `null` pointer. (Note: just DFSing down the left subtree
// will not always work, as the shallowest leaf could be in the right subtree
// as in testCase2).
// Similarly, for the longest bit length symbol, we just need to do a DFS on
// the right hand side of the tree until we hit `null`.
const minBitLength = getMinBitLength();
const maxBitLength = getMaxBitLength();
console.log(`minBitLength: ${minBitLength}, maxBitLength: ${maxBitLength}`);

// Solutions:
// testCase1: min: 2, max: 3
// testCase2: min: 2, max: 5
// testCase3: min: 3, max: 6
// huffman.txt: min: 9, max: 19

huffman.txt

1000
7540662
6852892
3235725
8045172
2667794
2595511
7030103
5882478
2731795
8630567
7224817
9147454
9180184
4194220
801991
8773930
7498447
5429618
1948993
4161112
7231836
3512965
6037327
8518300
2917342
547194
5015100
837907
341970
6249282
9353243
5546257
7031847
9959436
1082955
7132656
9863608
2548250
2209647
8069760
8572628
9344483
8874074
8638786
7812182
4849731
2492922
6698031
7404507
745731
8379593
4119022
4123053
4401250
5421516
8134188
8319394
9611963
3780734
6096612
6971484
7377399
6529211
6097359
6332343
5781826
279273
5153724
838231
4437902
3398506
3432892
2868587
3079930
6449351
7063764
9110714
2325311
5883213
911693
1779925
8305333
3636477
5712230
1858307
9079534
8865961
616791
2362911
2935267
3366532
1151019
7813585
6552397
3805014
7693039
795351
5346031
5699199
5297037
8236308
2817584
4715257
4633814
9478541
9933557
789849
3943007
2440768
615656
2760381
6402258
8117630
3856582
9371822
1771427
497228
8502109
1309140
624955
3397897
1765229
4908084
2070509
8862959
7276642
9603157
4934808
867218
4182171
4846509
5474314
8233899
4477188
4525386
2335033
8498281
1153072
1238992
8093006
4084086
1238317
3698397
4122987
4692437
7917039
1265714
9334428
5342919
8732807
1774206
6290125
6338581
2089654
5121265
1999595
1890100
3143107
4642901
8447001
5593021
1950231
1412270
6420175
3155741
7243071
7922116
9639930
5333616
8050203
4774305
7342538
7946249
5483937
149557
3790204
4238363
8894826
6302156
6170563
9363702
8127291
9717796
9218081
1484230
1290663
8389366
7938443
569344
5534970
1415528
7116876
555207
5342809
1536476
8972323
7654800
5165404
7464615
8864025
6119573
8440544
5171511
5722086
8015688
3042471
783373
3741722
8546605
1411550
97421
3824354
4139944
1163535
9589026
6300149
6915998
8013637
3423833
7290262
6211938
8737943
2620444
7823630
5881412
4589405
1384870
5296634
4196127
8817555
8344235
9077367
5865668
9363718
2119923
7947765
2032202
9658187
2227269
6331838
3996308
5700867
8612151
4662268
8746986
466715
5425139
6377733
413248
9594800
3646317
7285883
1395640
6757438
7333021
2218973
4656642
5395580
8923714
6945214
5570691
1452406
6348659
760824
6753343
4421015
1650139
3373557
5647807
8444917
7102932
5289986
8718721
2308480
1107383
1346546
249066
6283749
2353241
3682949
7522856
8745465
9520247
2894009
2259431
6638652
1926856
9633791
8893205
3139810
8473128
7961171
7768963
8158982
5823610
8894456
736307
8201066
7861924
6408573
3949582
4684379
4744609
9051858
380823
3122478
1573303
5250660
4415850
8808519
7080841
192204
2017931
209806
3285196
1330242
1153739
6481783
1258299
9877021
9055363
4854217
4557053
1126316
7347325
7760197
5383811
2682978
1819184
6975171
7749135
976810
6247739
6290391
3249739
4541817
3428099
9421755
8738433
1274164
7104303
3656422
9979223
3506122
1673754
3161921
2818538
4458682
6359261
6426934
782103
3901778
1857358
5484908
2875582
3738494
64537
6051223
6872740
4765176
7220104
2598270
9842137
7214217
5702910
2628894
1247848
520157
1206180
8206791
8843603
114191
4749339
2625711
9550792
841001
4233823
6276651
2664448
7474888
1262500
6593317
90939
535912
6627958
3058532
6768384
7084346
4800944
4819847
7045177
7365650
5997922
5208999
7729267
9285990
9354758
2209419
9044992
3295737
2530979
2307649
9857682
8012943
7029165
2278695
7856211
2296287
2603987
5489406
5398931
8497844
1846916
8594631
970195
6474016
9339029
2951112
9664028
2291705
6985762
4740530
4379911
9869271
9835332
4806727
5856936
1892081
3981651
4930580
9889780
962541
2562468
1336459
9593240
4338437
2215355
8528391
6434739
4655065
9130962
8311268
8211102
3917412
7652314
6019016
3368386
3959384
40882
4521749
8041559
932248
456813
5746116
6871915
8918266
2281631
7707477
1081623
5791610
5073444
8189308
3932451
6966131
2523371
3237916
8946890
4014101
2017252
1608691
166321
1873
6506530
680587
1709020
9555716
709728
8716178
5656747
1230065
8487375
7166190
4948841
6882759
6677256
270695
2600124
886140
3425484
3273528
379629
4483866
6416998
7966718
7807042
6305964
4966440
3210575
5630654
8499854
2207795
4094756
7364964
899516
8149244
5225044
7409718
8157209
7662259
7760348
9106972
2648302
1833054
1359669
9978358
9752431
7835150
7039906
4874388
7566994
6755902
9602458
7621071
4888538
7809809
2417608
7939434
7630425
2471915
1991528
2867487
4910075
3667457
2041172
6836791
7482135
9034598
5676907
107416
9568704
6633667
6493718
8509618
2403363
4521616
4142717
3825501
5734943
6781157
7043308
2714778
2562210
4467454
3294809
57802
6843026
616277
3807379
9353508
3101183
1360510
8348712
9455063
4007404
2990314
4679226
3439397
2400452
3794129
2600105
1850113
2659662
3127710
849244
1161427
1119946
8386556
8696999
5684375
4978411
6673706
9201552
8456014
7509368
3452778
8664366
8113437
8983823
652742
2057013
5920285
8530242
4010767
3315346
2524081
651730
341040
9448969
83429
2642101
1433786
3649759
555199
5474772
8325637
2263107
9288002
2097012
4012152
9496180
7599357
3119784
6849327
7368417
3918571
5019143
7816600
3698908
9386292
506213
1687743
169883
4473394
5880820
3370978
8525526
7720062
6094764
6975371
9034588
1049472
7472233
8616597
1331899
6725820
505108
5111362
1803917
3482963
3605378
5407258
2625367
1465096
2464278
758393
1121696
1968038
6320843
2917881
7807840
2199230
2691670
7583934
5029628
3055273
5523150
2603228
5666836
4305906
7922171
9787624
3164901
8298150
3720363
8155910
5145168
545323
2847654
3121259
7952235
829684
1456967
6839437
7253416
535893
3020761
3333465
3851724
7438085
9679393
1155576
5070284
6891277
8752837
8278436
8723147
5467399
1256676
794517
7395024
6524438
6111922
4388265
8132181
3389703
8089365
9807139
7057278
8063236
7392465
304460
9879636
6993002
2860509
810943
8727902
6823970
5760205
8982619
1189333
996638
1990671
394075
6710898
2970241
4769175
705755
8960359
7919966
9844247
4457249
6305295
3384562
9311730
3696071
569367
8026529
9018656
8786437
2822849
2612451
683042
1573997
1246625
4810066
4034299
6398176
8102279
6927406
4128359
3912623
4172411
1280821
4502892
8938413
3101492
4503602
1783438
6081576
7492446
6859568
6592440
37164
8126217
4756682
7950114
159892
4227759
8409663
7049520
9553411
7991122
5404616
9273380
5784690
8079351
8558865
5545395
9572785
4647771
2388923
2925254
3882138
9879739
2654229
7803982
1062936
4082368
2165077
3042587
9968891
7262102
1385141
2525180
8501245
8452218
1851594
3527804
8873317
3087832
9582323
4555928
5802025
4306883
9407054
1531412
6514736
1116902
12710
3310966
8556302
715468
6235973
4604649
133947
405875
5439070
4206464
5313145
9218187
356432
5883301
9827097
6358863
7705902
1774454
3446979
247376
7127672
771293
1017408
3591569
4932798
5856066
3079629
7487083
6682658
5442652
5734430
4286579
1614167
9061552
7636648
6215627
4503170
9236790
8521382
7749368
5247205
1358976
6368177
2272567
8007799
8902975
6620440
8001611
934209
2180122
192218
8075767
5278246
3030695
9357701
1528193
6081372
4032029
7152249
8534425
6093548
1219060
9407116
931792
3580190
8788289
5694987
7424854
3671960
61282
3572962
1747121
2258158
4214951
9018342
7765611
9706446
2655517
9916957
5112225
141897
1339459
440233
3011010
9772019
4905242
1109382
1309337
2587005
4536352
7702653
7802187
8006005
6497708
1386887
1064131
1536730
2564491
9911792
7131759
6905830
1659776
3987281
2419919
3882653
6103143
5164890
3665750
7567713
2024175
1350643
7870654
3959682
2346297
715503
8053278
3717635
7003767
3556415
4226994
5833572
3426133
8660808
8566596
6389614
1289868
8655532
192227
201512
1618977
5113351
7114006
515470
7283473
3171828
4819908
1378107
7276455
368071
7156144
3802117
3189072
3208861
160666
8888567
3500210
5135748
8769878
218073
4917463
5767214
5972689
6261982
4140557
732979
9614188
3186821
3257410
4564278
70116
1771529
9454158
3259365
258498
3601052
636731
6993050
6485811
7986006
5499670
1379613
7351266
1797443
149350
3009608
3382161
3371230
497856
6812480
8250599
4939811
4602102
1462877
8447562
1170616
5121988
795887
804116
1281873
191692
7386698
5461863
3896473
5080401
8044456
4844078
4563360
8568320
780907
8850726
8798444
9179767

mwis.txt

1000
4962786
6395702
5601590
3803402
6784626
4944482
2882725
9310662
5247184
9819854
8398364
1470063
4199696
4623136
8160902
930850
3889157
8211214
6560984
8835416
3024392
3286693
736791
3862790
1420652
9767464
6093772
2133393
358615
4537366
6655609
5551123
9039549
469060
304701
5768649
1339317
8421671
513661
6792447
3944383
4692731
4614391
9344708
4169702
4345210
9744699
9407222
6480402
7985130
4407746
4040958
7960851
5394516
4024926
6784072
1710864
6886941
7495555
5654086
2481292
8892684
2186179
1539792
1828698
4741356
3476859
327340
7634220
808031
5101226
6958744
1511709
7231864
7447240
778642
3120423
1098518
6450468
399546
7275028
1081427
7154897
2804344
9440402
2909959
2686145
5099515
3776057
5765944
8935025
6477008
3490890
1691564
2225172
8510419
9788522
9484150
7236748
7334350
3501364
443073
3839984
511778
5938948
8542395
998674
307072
3068204
9908539
4675871
8958494
713730
489163
2908154
5500103
7463231
4256879
801111
1312026
3383096
9677883
6972318
9812223
2680217
1777191
7197988
8155531
1762267
256812
4319070
9635141
9583155
3250694
149904
9722955
6836491
5998739
7077631
2905680
8047743
5398820
5327949
8262028
6446657
6945815
5201088
1818890
3455395
2094958
1387816
73296
5562568
4138240
7411620
3236316
3526603
2889306
5881661
9746189
295106
1140760
567794
8971262
8092826
6178363
6493070
5307905
3151323
9430583
5945625
2591187
4762105
1419485
7975274
6200869
3747595
3496996
5533979
4881997
6326981
6530568
6491735
1433394
5656371
8268622
4897856
2245483
1669874
7743046
3840061
1703393
6096353
3282159
4065018
6008865
3662040
440417
6320312
9523490
6583500
1674269
6902908
8718923
4953838
4492172
1406910
7453747
9251820
1368416
9781274
8913978
1395947
5304262
2437936
9096011
368065
6977113
305541
7998419
9113264
932390
5948936
3610392
6452644
7392634
4319886
9125467
2520028
7543480
1811018
4099447
4892952
7597021
8361800
6314060
4059634
3125308
3192850
9152613
1306872
3292977
9560779
9488831
9009343
5026364
1010852
1545256
8623793
5644518
2948787
3809130
2673396
2060852
2653718
4176196
1615904
8461567
46747
1206954
7220207
9171602
3338565
3061384
9674051
2510050
382009
247219
6002436
1003287
9988055
3041426
8936322
7452194
405922
998911
9382240
4249228
9221427
4650092
1772513
2816258
8258398
1476303
320865
6700891
8695236
1180251
9260565
6330678
3891892
7567141
2845081
7192332
5252074
9132808
9208518
2096326
342578
8349742
3159129
4205011
638307
71223
4872024
4912458
2849051
4781804
6261562
7290515
5007673
7458434
4013763
8550805
8008820
2813461
2055878
7657837
7385240
4792029
7538175
5131101
9006068
3337699
9317035
1481292
8231505
9487483
3345098
449245
453983
5589565
7292106
2703366
5298881
4515612
1256237
2222110
2684520
7701606
7853799
1194554
7851668
2444712
2930373
1936058
4295952
889562
7390238
1844735
8371775
1735214
6206412
3559345
6812846
1985125
1791905
728358
7230264
428268
7286935
372152
69051
762807
8510926
2815300
9983039
3209564
6777024
4992085
2890580
562039
9194719
3176970
7526657
3493083
7967410
8786315
4059864
6382237
7073152
7545693
6431229
1028498
5789973
8113571
7564283
5817713
6832277
5002565
2265208
438557
1757079
230881
8495104
5103307
7420851
4180422
7270131
1905337
1475037
9123930
9028159
4990449
2384686
9696856
3007692
8297118
211151
5438779
939934
840794
4164074
8027683
9922110
1912779
6026895
3157619
928339
4618770
7990617
6364128
1665428
2032576
4278982
6100265
6916991
3385276
1620451
4938346
6242748
2804263
7464822
4556996
5035925
2753070
1992856
8716085
9036144
2277153
8453661
4998172
5797542
367000
950156
5886760
8153903
5106830
9327140
4457455
5022044
3052347
966685
5172349
2728196
114135
114631
950795
5526943
8218003
4491994
7829474
2789301
5316357
4262939
9673787
9578536
2523410
506950
4693798
9940156
6942521
4182321
5383012
4860281
8370920
7573431
7768171
3221024
136106
3558236
1532053
3539310
2559342
5062808
2759619
1745360
7119640
2321292
61658
3124538
7173906
2308870
7978139
6890041
6990701
9148722
7011840
1004792
8528187
3401861
2686816
5880479
4738654
8779826
3521280
2432159
6727447
7812233
6665980
8840860
8512364
3689400
7355420
3122714
5805153
5906419
2998226
9406986
5651526
7543317
972976
3346751
3019685
8516433
258788
6865579
7756334
9451512
9182658
8428446
6755965
4586583
7925989
1750013
1012874
9879336
383953
8490296
8428185
2060982
8463641
7064392
3495414
6781287
2006763
3411676
8172818
8583986
9299153
5452259
2107695
4570801
5699991
8274500
7659330
3933403
5088705
1593520
2318532
800976
5025027
7639122
1046031
792737
5459182
1592753
2170890
9789466
5809494
7911061
2539029
8128492
6194946
8695485
9659426
3269288
2485303
7917729
8230758
8239170
2859339
6147337
8804366
25181
2859231
5697800
5916890
198723
1295416
6001047
9065735
3209019
6034946
1731523
7530638
4911295
4227646
8017018
9172125
5472593
8707393
4662570
4188377
3616500
5372731
2963776
5781540
547771
6944907
4830030
3204711
9652058
3214849
8558645
1198566
5762344
6891881
1340276
4572263
9330449
1512284
9286625
4875144
3487144
456312
3686685
8103846
1473723
8969048
1880736
1759826
2660009
6476439
4195665
1902918
6541154
3688474
9839555
6651494
7451271
2178417
1800904
3486131
7961262
6080960
5622791
2353468
6091491
3704395
5007227
9766820
7489731
8204534
653479
9716090
3198448
9407622
5800774
2047472
2054300
2404336
8797243
8880009
942131
6609608
5630020
1811483
9775730
190668
9154330
5814438
2349137
87075
377384
8265014
6235364
1268556
3993536
1315177
2978348
6866975
7192230
9097204
1508552
8389823
4418343
3207064
3228001
9060408
2572469
4556887
772937
569691
8870161
8748666
5320607
591676
6746779
3049333
1098005
3201215
3678652
6987296
703728
9091928
7137459
7851264
8679414
5073340
2800891
3549720
6492278
7347897
8150917
9072915
9901590
2598922
4927088
1765561
738823
6527609
8488766
2377259
1736305
5587018
2342320
6319258
9326385
9725092
3708463
1751982
8413788
2812497
6931514
8034607
7712963
1665201
5604160
2580404
8580377
3987517
6994034
3461720
9023568
3001914
3162591
4862158
5506641
8098537
3719415
5423946
3462891
2006838
5950531
6884423
5895826
1687977
7296380
8527160
579056
929868
6727615
2911321
1839652
9883242
4019779
9351955
1506017
8878831
4904090
1116317
2857737
6748923
3853755
9070989
6055928
8495836
3285325
1291712
3948504
598342
1281879
3452434
811454
55155
69666
9746527
8211717
8216491
2913751
841852
6067475
4500451
4812117
9506317
4721179
3430293
8096704
2169682
8080867
959158
6986191
6230108
1518225
9144943
4276108
668735
7066824
5485477
6897681
9606419
411948
4773096
257689
5166916
1026383
3757232
6403261
120660
8418961
751193
4319181
1258900
7066471
5834556
9970511
694730
9718714
3113979
1798400
8577364
967966
7761512
5987361
1298629
9751177
2374549
4800917
6048397
3881601
5413145
9343996
5041981
568535
8439155
438409
776396
8795136
9114404
6175501
9079829
6773121
8172102
9880452
373909
2155676
2182504
5579551
7656805
9861114
4136374
8786839
9617640
5277095
8455766
5737131
8045592
4790400
5646144
6598950
7695887
9387672
907962
957241
7359468
5934152
8620600
130133
4298771
8000946
9967304
9170262
4052754
3583496
6095556
3813728
8025242
5871565
6064143
5217101
7327965
2436132
3590119
931544
9765838
7736249
7028875
2828882
3744219
2038808
2208794
4519737
2901376
5151574
875323
7820979
2271532
5310716
4816325
6083796
2704672
7885209
2415433
3888095
3656551
3210487
3509308
5685228
2198490
1967673
1415527
2866735
9860515
3046505
3877183
6102348
2798277
5699538
2173325
1628328
5033001
4046418
5181215
8111653
7485814
5485629
6017894
3702841
4723312
5279763
4548119
1076239
2571841
1033405
9934376
9360558
2683831
2755130
5472163
1640750
6639786
8304816
4736842
718355
8029910
3933803
6141288
3957342
1258240
758402
6150115
4312581
7783453
9346578
9585654
2180358
2487797
8664854
3572216
8748977
5218044
2273780
8092203
8420778
7982179
8496968
3197929
6429917
4356919
5303666
210350
8520887
7263348
4287969
9630021
9990728
8455483
5433316
4773035
8432976
3312796
2431648
8237261
9628820
1399389
7546051
8594344
3304589
6911311

testCase1p1and2.txt

5
5
25
32
20
18

testCase1part3.txt

10
280
618
762
908
409
34
59
277
246
779

testCase2p1and2.txt

10
37
59
43
27
30
96
96
71
8
76

testCase2part3.txt

10
460
250
730
63
379
638
122
435
705
84

testCase3p1and2.txt

15
895
121
188
953
378
849
153
579
144
727
589
301
442
327
930