Algorithms Coursera Part III Programming Assignment 1.js

Algorithms Coursera Part III Programming Assignment 1 Part 1 and 2.js

/* eslint-env node */

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

/**
* In this programming problem and the next you'll code up the greedy algorithms
* from lecture for minimizing the weighted sum of completion times.
*
* Download the text file below. (jobs.txt)
*
* This file describes a set of jobs with positive and integral weights and
* lengths. It has the format:
* [number_of_jobs]
* [job_1_weight] [job_1_length]
* [job_2_weight] [job_2_length]
* ...
*
* For example, the third line of the file is "74 59", indicating that the
* second job has weight 74 and length 59.
*
* You should NOT assume that edge weights or lengths are distinct.
*
* Your task in this problem is to run the greedy algorithm that schedules jobs
* in decreasing order of the difference (weight - length). Recall from lecture
* that this algorithm is not always optimal. IMPORTANT: if two jobs have equal
* difference (weight - length), you should schedule the job with higher weight
* first. Beware: if you break ties in a different way, you are likely to get
* the wrong answer. You should report the sum of weighted completion times of
* the resulting schedule --- a positive integer --- in the box below.
*
* ADVICE: If you get the wrong answer, try out some small test cases to debug
* your algorithm (and post your test cases to the discussion forum).
*/

/**
* -------------------------- Part 2 -----------------------------
*/

/**
* For this problem, use the same data set as in the previous problem.
*
* Your task now is to run the greedy algorithm that schedules jobs (optimally)
* in decreasing order of the ratio (weight/length). In this algorithm, it does
* not matter how you break ties. You should report the sum of weighted
* completion times of the resulting schedule --- a positive integer ---
* in the box below. 
*/

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

const fs = require("fs");

const input = [];

/**
* Parse the text file and store it as an array (the first entry is the number
* of jobs i.e. the length of the array) of tuples of the form:
* [
*   [job_1_weight, job_1_length],
*   [job_2_weight, job_2_length],
*   ...
* ]
*/
(function getInput() {
  const data = fs.readFileSync("jobs.txt", "utf8");
  const rows = data.split("\n");
  const numJobs = rows[0];
  for (let row of rows) {
    // Ignore the first row, which is the total number of jobs
    if (row === numJobs) {
      continue;
    }
    // Get rid of empty row at EOF
    if (row === "") {
      continue;
    }
    // Remove excess white space at the end of the line
    row = row.trim();
    // Break each row into its own array, where the first element is the job
    // j's weight and the second element is job j's length.
    row = row.split(" ");
    [row[0], row[1]] = [Number(row[0]), Number(row[1])];
    input.push(row);
  }
}());

// console.log(input);
// const numJobs = input.length;

/**
* ---------------------- Greedy Scheduling Algorithm -------------------------
*/

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

/**
* Pseudocode for Part 1 (Part 2 very similar)
* 0. The ith element in the input is the tuple for job i's weight and length
* 1. Initialize:
*     - A new Map with keys of the difference and value a list of
*      - c = completion time thus far
*     - cWeightedSum = The sum of the weighted completion times thus far
* {jobNum, weight} objects (since we can have duplicate differences).
* 2. For each element in the input array
*     - Compute the difference (weight - length)
*     - If there's already an entry in Map for this difference
*        - Insert the element in the list in order of decreasing weight
*          (highest weight first).
*     - Else
*        - Add entry to Map (key = difference, value = [{ jobNum, weight}])
* 3. Create an array, A of the keys of Map and sort it in decreasing order
*    of difference.
* 4. For each key in the sorted array A
*     - Look up value of key in Map
*     - For each element of the value array (iterate in order):
*        - c += length of this job
*        - cWeightedSum += c * weight of this job
* 5. Return cWeightedSum
*/

/**
* Schedules jobs in decreasing order of the difference (weight - length)
* if "diff" is passed in as the comparison method, otherwise in decreasing
* order of the ratio (weight / length).
*/
function getSumOfWeightedCompletion(comparisonMethod) {
  const comparisonsVsJobNumAndWeight = new Map();
  let c = 0;
  let cWeightedSum = 0;

  for (let i = 0; i < input.length; i++) {
    const job = input[i];
    const weight = job[0];
    const length = job[1];
    const comparison
      = comparisonMethod === "diff" ? weight - length : weight / length;
    if (comparisonsVsJobNumAndWeight.has(comparison)) {
      // Break ties
      const jobList = comparisonsVsJobNumAndWeight.get(comparison);
      jobList.push({
        jobNum: i,
        weight,
      });
      // Sort in decreasing order of weight
      jobList.sort((a, b) => {
        return b.weight - a.weight;
      });
    } else {
      comparisonsVsJobNumAndWeight.set(comparison, [
        {
          jobNum: i,
          weight,
        },
      ]);
    }
  }

  const allComparisons = Array.from(comparisonsVsJobNumAndWeight.keys());
  // Sort in decreasing order of the difference
  allComparisons.sort((a, b) => {
    return b - a;
  });

  for (const comparison of allComparisons) {
    const sameComparisonJobsList = comparisonsVsJobNumAndWeight.get(comparison);
    for (const job of sameComparisonJobsList) {
      const weight = input[job.jobNum][0];
      const length = input[job.jobNum][1];
      c += length;
      cWeightedSum += c * weight;
    }
  }
  return cWeightedSum;
}

console.log(getSumOfWeightedCompletion()); // optionally pass in "diff" as arg

// Solutions (Part 1, for weight - length):
//  - testCase1.txt: 68615
//  - testCase2.txt: 16
//  - testCase3.txt: 32780
//  - testCase4.txt: 110 (tests tie breaking)
//  - jobs.txt: 69119377652

// Solutions (Part 2, for weight / length):
//  - jobs.txt: 67311454237

Algorithms Coursera Part III Programming Assignment 1 Part 3.js

/* eslint-env node */

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

/**
* In this programming problem you'll code up Prim's minimum spanning tree
* algorithm.
*
* Download the text file below (edges.txt).
*
* This file describes an undirected graph with integer edge costs.
* It has the format:
*
* [number_of_nodes] [number_of_edges]
* [one_node_of_edge_1] [other_node_of_edge_1] [edge_1_cost]
* [one_node_of_edge_2] [other_node_of_edge_2] [edge_2_cost]
* ...
*
* For example, the third line of the file is "2 3 -8874", indicating that
* there is an edge connecting vertex #2 and vertex #3 that has cost -8874.
*
* You should NOT assume that edge costs are positive, nor should you assume
* that they are distinct.
*
* Your task is to run Prim's minimum spanning tree algorithm on this graph.
* You should report the overall cost of a minimum spanning tree --- an integer,
* which may or may not be negative --- in the box below.
*
* IMPLEMENTATION NOTES: This graph is small enough that the straightforward
* O(mn) time implementation of Prim's algorithm should work fine.
* OPTIONAL: For those of you seeking an additional challenge, try implementing
* a heap-based version. The simpler approach, which should already give you a
* healthy speed-up, is to maintain relevant edges in a heap (with keys = edge
* costs). The superior approach stores the unprocessed vertices in the heap,
* as described in lecture. Note this requires a heap that supports deletions,
* and you'll probably need to maintain some kind of mapping between vertices
* and their positions in the heap.
*/

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

const fs = require("fs");

const adjMap = new Map();
let numNodes;
let numEdges;

/**
* Parse the text file and store it as an array of tuples of the form:
* [
*   [one_node_of_edge_1, other_node_of_edge_1, edge_1_cost],
*   [one_node_of_edge_2, other_node_of_edge_2, edge_2_cost],
*   ...
* ]
*/
(function getInput() {
  const data = fs.readFileSync("edges.txt", "utf8");
  const rows = data.split("\n");
  for (let row of rows) {
    // Don't include the first row, which is the total number nodes and edges
    if (row === rows[0]) {
      [numNodes, numEdges] = row.split(" ");
      [numNodes, numEdges] = [Number(numNodes), Number(numEdges)];
      continue;
    }
    // Get rid of empty row at EOF
    if (row === "") {
      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(" ");
    const [oneNode, otherNode, cost] = [Number(row[0]), Number(row[1]), Number(row[2])];
    if (adjMap.has(oneNode)) {
      const incidentEdges = adjMap.get(oneNode);
      incidentEdges.push({
        node: otherNode,
        cost
      });
      adjMap.set(oneNode, incidentEdges);
    } else {
      adjMap.set(oneNode, [{
        node: otherNode,
        cost
      }]);
    }
    if (adjMap.has(otherNode)) {
      const incidentEdges = adjMap.get(otherNode);
      incidentEdges.push({
        node: oneNode,
        cost
      });
      adjMap.set(otherNode, incidentEdges);
    } else {
      adjMap.set(otherNode, [{
        node: oneNode,
        cost
      }]);
    }
  }
}());

console.log(adjMap);
console.log(numNodes, numEdges);

/**
* ---------------- Prim's Minimum Spanning Tree Algorithm -------------------
*/

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

function computeMSTMinimumCost() {
  // All vertices in the graph G
  const V = new Set();
  for (let i = 1; i <= numNodes; i++) {
    V.add(i);
  }
  // Set of vertices we've spanned so far with arbitrary seed vertex
  const X = new Set([1]);
  // Set of edges; edges in T span the vertices residing in X
  const T = new Set([]);

  let overallCostOfMST = 0;

  while (X.size !== V.size) {

    // Get all frontier edges (u in X, v in V - X)
    const frontierEdges = [];
    for (const u of X) {
      const incidentEdges = adjMap.get(u);
      for (const edge of incidentEdges) {
        if (!(X.has(edge.node))) {
          frontierEdges.push(edge);
        }
      }
    }

    // Pick the cheapest edge, e, crossing the frontier
    let cheapestEdge;
    let cheapestCost = +Infinity;
    for (const edge of frontierEdges) {
      if (edge.cost < cheapestCost) {
        cheapestCost = edge.cost;
        cheapestEdge = edge;
      }
    }

    // Add e to T
    T.add(cheapestEdge);

    // Add v to X
    X.add(cheapestEdge.node);

    overallCostOfMST += cheapestEdge.cost;
  }

  return overallCostOfMST;
}

console.log(computeMSTMinimumCost());

// Solutions:
//  - testCase1.txt: 7
//  - testCase2.txt: 15
//  - edges.txt: -3612829

jobs_part1and2.txt

10000
8 50
74 59
31 73
45 79
24 10
41 66
93 43
88 4
28 30
41 13
4 70
10 58
61 34
100 79
17 36
98 27
13 68
11 34
80 50
80 22
68 73
94 37
86 46
29 92
95 58
2 54
9 45
69 91
25 97
31 4
23 67
50 25
2 54
78 9
29 34
99 82
36 14
66 15
64 37
26 70
16 95
30 2
18 96
6 5
52 99
89 24
6 83
53 67
17 38
39 45
2 98
72 29
38 59
78 98
95 5
10 32
46 76
36 99
43 100
69 13
61 58
95 9
96 69
14 31
7 63
43 66
83 53
68 22
96 13
72 2
91 32
39 58
17 91
41 80
36 7
73 99
96 20
55 24
90 61
6 27
24 7
14 71
39 95
21 45
67 35
27 95
64 39
45 91
51 60
24 48
86 18
73 40
48 86
97 86
24 21
45 69
36 16
26 35
43 12
80 53
45 96
19 97
93 16
92 34
70 98
54 48
26 11
63 12
9 78
62 26
36 69
96 77
68 40
75 32
57 2
73 61
95 85
56 90
8 16
94 70
81 56
56 7
64 3
77 9
50 32
45 39
9 98
52 50
4 32
32 15
20 76
10 81
30 24
55 61
38 46
18 26
1 57
65 98
49 5
51 51
77 13
55 98
5 82
49 66
79 100
10 30
54 84
48 8
74 23
6 77
54 25
31 67
1 45
71 86
17 99
56 34
58 77
79 67
58 12
79 15
20 38
34 92
21 63
34 98
32 89
90 74
78 5
59 1
55 61
16 48
81 31
56 47
8 39
1 27
36 58
14 15
94 61
55 19
58 86
30 16
64 3
18 44
20 68
48 70
96 4
74 4
49 86
59 60
7 31
25 33
74 4
98 21
51 32
81 4
1 21
34 59
4 77
51 35
81 80
33 75
50 43
50 72
11 80
84 71
41 24
51 72
30 19
47 100
31 22
77 25
45 59
97 72
65 61
99 52
41 4
52 2
6 81
19 75
50 14
21 26
13 84
89 18
9 51
25 96
58 12
91 67
11 94
54 66
61 43
4 53
8 42
11 1
100 28
72 88
15 26
42 18
49 43
16 75
46 74
21 12
40 55
6 30
54 90
67 57
5 61
99 93
21 17
81 68
53 40
99 2
12 17
92 72
29 72
62 46
21 41
59 54
28 51
12 64
95 34
28 28
96 32
43 17
7 16
25 2
98 62
4 25
9 37
82 16
11 17
6 74
82 21
92 70
66 28
37 29
26 85
68 50
77 47
77 67
68 21
85 92
11 59
12 45
19 19
35 26
68 90
19 15
26 19
29 30
35 28
41 55
41 97
36 84
49 66
12 53
65 77
38 76
46 11
16 93
11 48
38 100
48 16
94 80
30 65
80 2
26 90
59 34
1 90
71 18
47 39
44 39
37 22
20 97
48 89
60 88
36 36
13 85
90 85
35 68
20 16
46 77
62 26
20 32
4 99
99 40
5 4
80 66
92 8
25 66
22 55
7 51
4 33
33 42
55 78
18 1
90 66
48 23
80 18
17 49
63 30
40 9
4 58
62 53
67 22
58 97
56 31
95 56
22 13
94 28
33 45
92 99
53 57
71 4
40 15
100 67
36 22
44 53
87 20
51 11
24 70
6 44
12 32
93 17
100 72
40 71
37 92
58 34
29 78
11 84
77 90
92 35
12 5
27 92
91 23
65 91
85 14
42 28
80 85
38 71
62 82
66 3
33 33
55 60
48 78
63 11
20 51
78 42
37 21
100 13
60 57
91 53
49 15
45 19
51 2
96 22
32 2
46 62
58 11
29 6
74 38
70 97
4 22
76 19
1 90
63 55
64 44
90 51
36 16
65 95
64 59
53 93
17 15
21 61
51 69
42 48
97 88
2 35
29 72
49 76
54 72
30 94
20 72
21 65
80 31
11 81
14 43
39 83
45 29
94 76
81 1
97 48
71 88
44 34
53 62
25 1
81 79
58 24
99 15
46 63
10 11
50 19
91 56
44 56
86 35
76 22
52 27
52 60
84 15
38 80
99 1
38 86
79 85
43 16
61 68
41 8
67 29
63 64
70 91
24 79
14 62
11 41
79 1
95 8
57 52
87 32
45 40
77 85
53 9
15 55
20 29
72 71
64 48
25 44
55 9
82 53
89 64
60 20
80 57
62 88
54 100
89 45
81 67
84 75
37 10
68 35
40 85
52 50
67 68
11 90
28 74
82 96
37 75
36 32
73 29
99 71
88 98
90 47
91 12
13 64
13 82
52 31
22 14
29 51
1 60
55 93
95 31
33 60
78 80
33 73
84 82
54 23
22 57
19 92
1 97
21 5
100 30
45 76
71 17
100 81
19 89
53 29
1 63
41 50
86 84
16 60
79 60
62 83
49 55
41 82
71 29
52 45
70 96
70 11
73 24
26 20
51 32
44 47
70 71
95 11
93 65
25 62
20 21
63 62
26 35
50 91
23 61
94 29
23 82
67 69
24 23
40 18
94 65
79 57
72 42
56 37
90 29
21 3
13 17
48 47
52 73
12 24
37 6
8 34
67 54
13 26
41 54
58 34
96 40
52 59
95 61
39 30
76 99
93 34
63 77
37 47
74 65
85 93
20 43
29 60
63 46
17 28
73 49
1 71
99 93
46 29
1 44
93 64
84 73
2 10
22 87
14 70
32 58
20 87
57 17
55 55
15 16
38 67
98 78
61 13
92 32
75 64
78 25
85 34
51 28
100 30
10 45
65 52
13 80
35 8
84 1
60 11
54 92
22 26
54 30
97 54
62 59
92 64
21 69
88 27
73 20
42 5
52 93
46 71
75 63
77 18
27 14
45 72
80 36
30 89
49 79
18 24
39 9
30 27
69 7
100 56
30 77
89 97
20 65
38 17
19 92
84 99
21 49
62 52
19 78
47 62
79 29
64 36
7 9
69 80
20 24
78 93
54 79
54 96
72 76
5 63
33 20
32 36
69 69
11 35
71 79
66 46
80 76
28 88
64 38
67 35
84 76
85 56
57 100
65 94
87 34
25 48
95 31
68 66
11 83
6 15
53 42
86 92
7 61
61 13
4 31
86 1
86 68
85 89
1 87
1 96
100 3
29 84
18 37
3 90
79 26
90 23
96 6
20 92
22 75
15 63
7 84
27 20
2 31
45 76
59 63
32 37
21 9
25 48
9 12
98 1
15 97
100 46
34 63
40 55
22 87
37 11
63 74
94 36
89 72
39 22
92 14
61 58
93 44
76 69
14 16
37 92
48 70
33 35
29 44
80 7
55 8
38 4
22 48
35 50
17 60
39 51
84 87
97 86
25 23
64 82
13 52
3 96
37 55
9 81
32 31
96 15
13 37
38 10
86 20
82 11
9 10
40 68
20 67
100 21
16 78
23 43
81 82
86 31
26 37
95 46
3 34
81 57
35 18
82 82
59 6
93 61
52 2
43 45
36 56
73 44
23 14
42 82
80 19
61 30
56 83
65 33
14 96
29 5
56 12
82 11
5 52
17 62
65 6
23 14
44 37
19 95
89 44
40 3
44 71
20 13
18 33
83 98
60 74
91 20
11 12
16 79
43 46
71 63
9 84
100 10
14 51
52 66
3 18
54 100
17 85
70 43
4 16
30 58
83 65
53 55
27 28
56 60
53 87
23 30
87 50
80 99
91 4
87 44
28 86
99 88
18 32
77 62
64 15
84 33
23 12
92 72
43 34
54 31
81 5
16 88
11 82
59 87
34 41
60 37
63 39
55 27
27 13
96 22
78 42
59 55
21 98
28 52
63 33
38 5
58 6
8 44
59 40
44 98
82 66
58 6
18 13
25 85
60 100
17 41
52 47
23 94
16 50
62 50
32 97
24 97
45 51
39 32
60 36
66 2
88 38
49 21
25 95
76 4
90 87
46 44
58 33
62 79
5 3
32 21
87 31
44 68
49 45
18 50
26 74
64 17
81 49
80 58
15 6
90 8
6 28
15 16
9 98
50 96
30 27
67 99
86 63
19 54
80 4
84 24
60 22
75 35
76 3
37 80
16 51
14 51
93 49
84 82
48 9
7 79
7 68
15 11
71 59
18 47
5 57
64 38
99 35
57 9
13 14
81 25
5 14
74 63
80 78
70 48
32 54
34 40
21 95
98 25
72 59
21 49
19 2
18 93
14 81
57 41
95 69
71 64
50 35
26 72
92 51
18 11
55 26
2 95
93 35
71 47
88 22
66 90
72 66
61 11
76 10
95 24
35 75
15 95
24 76
78 58
28 23
75 73
40 40
84 18
31 91
7 97
13 96
39 17
22 85
28 79
61 73
88 36
82 27
95 31
96 59
20 13
44 13
7 29
94 27
27 27
34 82
97 93
62 10
78 25
23 41
53 16
81 93
52 53
74 78
18 27
66 62
40 50
8 20
31 77
26 82
28 60
98 94
26 30
23 49
54 80
69 28
25 32
78 7
1 73
2 31
99 78
50 95
28 53
60 78
71 52
25 85
21 16
20 78
96 96
65 1
19 18
24 18
55 69
88 76
14 23
58 17
83 43
63 9
41 6
71 7
2 20
21 63
18 36
53 95
36 11
32 64
52 48
52 11
50 48
35 49
24 89
72 33
60 57
46 3
24 90
20 95
87 8
93 1
47 2
66 45
57 75
18 76
96 67
65 92
92 41
57 60
98 98
10 64
23 86
100 20
21 93
49 54
77 77
34 98
94 4
9 75
67 4
31 82
87 26
70 26
59 86
100 22
15 61
57 73
54 54
76 82
56 63
49 46
53 71
32 1
64 48
20 71
2 60
83 80
97 30
2 57
31 82
21 63
52 46
71 55
58 94
16 9
62 67
74 79
87 31
53 27
80 11
33 52
73 2
88 80
9 38
37 3
79 24
89 75
10 97
24 63
24 47
80 56
75 23
32 58
72 80
95 28
57 37
17 48
14 85
58 61
58 1
37 14
34 76
11 63
67 7
9 8
74 38
97 56
25 67
9 34
62 58
72 77
15 15
90 36
60 39
95 61
28 44
43 56
22 12
81 13
10 91
84 46
39 35
39 65
82 41
51 19
76 99
75 88
43 89
21 83
6 35
21 47
4 21
51 76
63 43
71 39
43 16
36 78
35 68
75 81
91 97
7 82
44 73
56 39
76 21
76 87
98 6
38 96
84 96
77 84
83 28
52 100
6 52
78 7
91 96
97 62
32 26
7 80
71 25
58 23
54 74
81 4
84 35
83 58
64 42
38 30
88 87
52 95
23 31
31 55
7 20
18 84
40 14
93 40
45 69
84 30
66 6
88 41
88 98
80 69
64 1
100 48
2 89
6 21
45 73
77 31
20 70
89 30
53 33
59 8
82 63
17 10
46 49
86 9
14 68
6 15
55 36
71 64
80 59
40 60
46 24
49 45
78 38
92 43
99 78
5 83
57 76
34 11
93 71
71 54
54 29
29 74
83 72
1 6
56 22
85 35
48 29
89 86
9 59
75 24
62 73
25 36
90 57
45 99
48 96
68 84
77 44
37 38
47 63
58 43
97 4
82 82
95 89
5 56
88 84
18 66
94 57
39 52
88 91
81 33
27 30
8 15
18 26
39 27
46 58
26 8
80 52
42 60
82 66
26 95
94 65
64 30
2 73
41 54
30 33
81 60
75 41
77 90
5 19
69 87
67 63
75 99
22 28
16 28
42 10
59 36
66 62
62 33
73 20
95 4
55 32
17 5
84 75
14 12
45 9
60 6
73 93
73 16
30 14
44 81
10 6
85 50
12 10
84 49
86 8
61 81
90 64
34 67
86 1
86 43
75 92
64 94
4 99
64 62
92 78
90 98
30 13
70 61
32 66
12 14
97 51
5 24
89 23
21 17
66 78
73 13
81 77
1 42
19 76
20 44
64 82
59 83
68 53
52 62
96 18
30 28
92 87
61 57
93 2
40 12
85 71
14 71
9 86
21 58
46 98
80 100
3 84
68 20
70 38
30 100
19 19
6 16
38 16
30 25
16 67
73 97
61 79
80 72
25 46
81 78
59 55
16 9
22 9
46 53
96 12
11 61
83 11
83 11
2 61
36 21
85 7
6 9
78 25
50 94
45 17
25 82
62 86
39 4
8 23
14 96
52 84
99 58
1 57
90 2
100 11
75 96
29 92
48 82
94 21
69 16
77 25
54 65
88 96
20 94
7 6
32 79
50 31
10 88
33 75
85 71
54 12
89 65
39 89
8 63
59 17
76 78
93 78
30 91
61 52
28 22
40 41
65 78
37 6
12 85
56 76
60 40
50 100
73 75
91 67
43 23
22 61
35 48
94 18
2 66
49 75
33 89
66 59
3 11
20 11
38 93
37 49
9 51
34 20
38 33
95 94
11 12
6 59
8 54
75 65
8 3
15 70
40 15
88 96
49 68
14 68
61 54
71 84
57 69
27 1
23 38
100 72
97 18
42 59
36 89
72 74
8 21
93 94
53 90
14 29
4 99
18 51
89 47
44 66
89 12
67 44
39 5
68 58
23 47
32 4
21 28
65 52
6 30
43 17
89 51
86 3
74 46
98 16
53 89
87 29
18 23
24 27
97 62
80 85
43 91
98 29
12 44
45 53
26 39
73 88
58 16
28 62
83 78
45 29
14 36
2 40
24 24
65 92
59 60
44 49
28 53
34 9
42 22
100 70
31 82
77 14
8 55
99 70
16 81
48 28
76 89
87 65
48 7
39 28
3 32
80 58
47 28
41 39
42 43
3 66
70 12
9 3
44 74
81 37
3 65
71 2
88 41
9 56
6 88
15 2
66 100
60 58
91 44
83 83
4 40
85 62
5 33
28 85
25 57
15 8
49 9
5 88
36 33
37 58
26 65
55 29
34 24
31 45
71 33
5 86
80 65
56 27
80 11
21 91
2 25
50 68
3 11
5 64
61 65
29 28
2 1
83 45
86 70
24 56
69 79
28 70
75 22
38 58
21 90
13 43
84 3
42 53
68 88
89 8
34 33
82 4
33 28
51 86
71 20
24 66
75 18
19 94
1 35
92 58
20 46
94 13
80 70
19 31
99 50
58 91
69 9
27 73
53 18
94 12
42 32
8 69
64 2
23 38
59 79
47 95
64 84
11 85
74 88
33 70
8 63
85 49
36 31
99 95
27 51
35 16
69 92
100 72
70 2
97 11
74 93
12 29
1 13
80 40
70 52
15 65
85 12
45 92
28 42
100 98
96 7
92 12
39 83
54 19
24 4
81 9
74 38
81 100
94 50
44 19
47 76
76 82
77 31
36 29
49 98
63 62
48 38
15 96
31 8
57 26
44 67
16 51
43 76
24 66
13 30
81 74
58 57
24 54
7 53
77 63
39 12
67 95
10 83
97 10
97 45
36 66
59 4
4 5
47 56
51 76
28 64
53 12
85 88
17 78
52 91
84 21
100 91
43 12
37 63
61 70
15 79
67 58
100 51
20 99
44 69
77 2
47 89
21 82
50 12
48 45
77 97
79 57
37 63
40 40
80 88
67 1
7 92
57 99
47 71
34 2
91 85
59 28
95 87
98 90
36 28
69 1
65 41
89 11
84 24
32 24
57 15
13 70
53 63
82 36
36 72
25 71
67 94
29 27
34 100
4 27
89 42
90 20
82 16
24 99
53 69
62 90
2 84
94 21
14 43
27 51
57 33
7 93
65 3
7 91
20 3
35 76
93 33
95 70
44 48
28 96
65 94
67 95
85 59
22 67
71 43
93 55
30 46
48 73
81 97
98 47
41 7
1 44
82 15
76 18
3 93
12 69
76 38
99 33
38 67
87 93
5 61
60 16
96 86
82 64
69 65
79 26
5 16
27 87
41 24
9 51
60 21
98 80
19 18
58 31
22 52
72 29
23 100
53 57
50 77
5 49
88 34
15 58
60 11
77 1
17 71
73 56
43 87
15 87
30 84
88 88
32 60
86 100
20 72
70 4
54 97
42 99
49 38
27 22
29 95
64 28
48 99
32 91
91 31
24 18
30 8
84 40
75 34
47 90
32 72
56 37
80 47
85 77
75 85
86 88
46 50
1 87
9 14
13 28
51 43
86 72
50 55
69 61
97 60
74 99
86 49
20 68
5 34
30 91
95 67
32 12
70 59
100 58
46 24
56 76
21 77
76 86
69 93
68 25
45 87
91 14
26 39
44 4
13 12
97 73
64 97
28 66
4 20
44 72
1 50
30 39
98 66
17 44
80 48
49 78
49 81
61 39
93 62
18 77
89 43
46 5
80 70
76 66
54 16
41 70
28 2
57 11
86 94
7 94
73 16
100 6
47 54
38 50
23 21
55 23
47 60
97 29
53 17
58 77
100 94
4 37
64 36
16 20
22 94
53 45
16 77
24 81
10 38
24 86
43 42
58 3
99 44
63 86
35 93
24 80
84 95
87 53
94 78
10 55
68 69
99 51
53 55
33 9
2 91
42 45
95 88
75 32
38 83
97 82
73 83
34 57
37 31
16 71
12 34
47 46
21 98
27 13
15 34
2 78
84 36
46 67
71 70
48 85
82 33
42 82
2 48
24 16
62 62
33 27
41 63
65 60
78 36
56 24
27 60
24 66
40 47
68 22
84 52
74 44
87 100
18 62
94 56
15 95
17 74
8 2
81 59
5 92
45 82
64 99
93 91
21 55
30 41
82 61
56 83
80 66
96 16
51 89
90 26
58 87
83 46
15 94
43 82
13 97
67 67
91 62
90 60
36 20
37 93
24 82
3 6
28 19
6 64
93 39
50 34
9 37
32 97
29 10
45 18
37 37
10 40
91 15
5 69
57 85
18 76
66 13
11 60
89 49
34 33
35 7
51 11
8 76
21 9
22 8
100 58
62 8
91 11
1 37
79 39
94 16
16 73
48 44
52 40
96 27
15 86
20 81
99 57
10 90
46 66
77 52
42 74
16 45
47 4
84 41
34 54
87 53
13 69
83 88
69 63
5 97
13 65
10 46
17 10
62 79
62 32
13 12
57 61
100 98
43 7
24 45
8 85
88 81
58 79
41 10
63 67
22 37
8 27
38 37
7 53
31 68
1 37
17 16
47 100
78 13
81 37
25 11
88 55
36 24
32 74
78 58
95 17
66 72
13 77
26 8
10 76
51 93
7 64
89 30
1 37
4 16
32 76
98 9
97 10
17 78
76 25
58 20
93 45
58 16
73 55
26 68
38 49
97 71
37 14
43 42
79 4
82 63
20 9
12 77
83 68
24 69
21 52
21 50
63 25
92 66
72 30
70 74
84 28
69 89
12 31
25 58
40 60
61 80
25 78
87 2
66 33
48 63
92 80
92 1
88 32
24 19
36 11
25 20
58 93
65 77
6 37
32 67
93 27
21 78
5 86
8 6
13 7
72 19
95 82
70 34
72 82
87 63
1 20
42 80
10 86
80 83
81 57
20 95
87 60
23 64
84 31
29 51
100 66
98 40
84 14
54 93
25 54
14 96
12 21
70 44
69 68
52 11
16 65
92 50
41 88
24 45
39 22
68 53
53 13
57 63
52 85
1 17
28 18
21 9
11 62
91 64
91 59
5 33
43 74
11 12
58 54
15 73
1 8
22 39
61 82
35 38
83 42
11 34
38 5
10 92
50 61
72 37
60 50
76 26
88 29
81 8
56 73
8 24
98 63
13 15
39 97
20 48
64 75
59 70
33 13
68 80
23 67
49 55
64 85
48 80
1 38
24 21
12 56
39 46
20 10
78 44
9 93
77 50
3 53
14 72
75 72
5 2
87 92
1 23
16 65
58 72
14 83
78 86
51 59
71 55
10 6
11 75
92 59
67 78
84 72
16 34
92 59
22 45
84 19
74 86
41 85
28 62
29 7
16 74
15 32
55 13
33 13
40 80
13 58
19 2
48 36
88 26
94 60
34 54
8 8
53 94
91 70
34 36
24 77
62 19
16 50
80 33
3 89
36 57
6 23
35 47
5 76
94 21
49 99
88 47
98 68
21 40
74 100
17 6
57 65
35 1
18 62
57 1
30 100
5 89
28 61
97 35
83 54
49 2
5 41
37 51
23 85
82 20
73 2
91 44
70 75
80 9
86 86
23 12
79 88
3 76
22 83
17 94
71 61
82 76
13 64
52 29
49 88
58 90
91 6
90 6
90 86
68 37
6 24
60 37
89 35
52 33
67 89
36 16
70 98
88 87
91 91
70 53
97 56
2 1
91 35
95 1
75 89
87 26
54 92
69 76
21 82
100 86
96 20
52 96
40 96
70 46
99 95
80 48
44 97
27 64
46 27
72 20
86 20
81 80
35 27
48 59
25 97
74 99
92 54
40 1
31 7
61 29
39 1
11 29
59 88
95 53
81 57
99 16
56 23
44 60
50 29
1 71
66 93
90 67
93 53
58 25
91 88
6 32
90 57
39 91
51 68
97 92
45 17
34 59
63 67
20 33
3 19
78 82
94 90
48 72
50 48
42 66
80 15
100 61
67 28
72 95
18 42
96 16
98 75
52 75
47 18
80 67
80 2
98 53
38 51
71 32
15 69
98 92
79 14
20 30
13 4
37 99
90 87
10 44
96 100
5 76
34 5
62 64
62 23
52 62
43 63
89 86
4 75
19 57
97 79
12 38
37 90
61 21
78 99
19 98
81 39
36 63
4 41
93 77
75 27
35 65
48 44
93 77
64 69
91 17
97 54
61 58
78 59
66 95
39 31
14 28
12 52
47 49
83 27
72 9
79 74
6 16
43 23
91 19
85 51
45 70
11 98
3 54
61 43
92 57
58 37
90 27
59 58
2 41
13 68
49 14
24 33
76 37
72 98
55 42
22 38
73 82
47 37
33 46
92 25
70 42
82 19
84 78
94 69
9 91
21 48
7 16
42 40
36 34
95 17
36 71
77 97
64 41
92 92
52 90
81 86
18 18
24 3
30 9
51 68
87 33
40 89
16 30
93 1
5 13
8 40
78 8
86 77
15 61
23 36
10 98
94 87
77 14
64 43
2 78
72 93
85 96
12 94
80 78
40 20
50 41
76 56
34 35
66 83
49 22
8 68
4 45
31 79
51 52
96 67
96 66
59 85
15 57
11 49
44 56
63 58
45 63
87 58
86 96
58 100
78 37
31 85
48 72
97 7
94 54
84 56
39 81
6 16
34 35
48 90
95 84
4 1
20 6
15 75
65 96
39 94
21 6
36 50
15 9
30 34
84 37
41 83
37 7
79 5
47 5
8 25
84 45
20 52
7 89
20 93
18 93
53 81
21 82
23 97
2 94
39 54
75 98
70 60
62 56
15 20
8 28
59 67
2 74
2 84
13 77
89 86
70 10
67 100
65 1
96 3
25 19
12 57
35 1
74 85
95 24
70 68
72 46
77 36
98 42
77 55
89 4
96 38
46 59
90 5
48 15
84 62
14 26
55 61
77 72
80 71
100 22
93 89
90 38
80 13
98 28
16 97
24 47
60 63
69 69
62 39
69 12
83 32
96 100
24 27
98 10
68 17
91 30
70 79
10 2
90 67
41 50
19 15
76 42
64 21
65 77
10 94
35 46
21 81
55 4
79 44
89 79
16 85
96 84
8 10
34 86
97 38
14 88
61 26
46 17
75 52
69 67
31 54
5 42
64 40
91 38
71 41
52 86
72 27
23 64
25 7
92 52
6 5
62 9
52 98
49 65
27 9
25 55
89 46
92 19
23 20
69 83
90 49
83 44
75 8
27 96
47 16
5 31
5 51
15 85
14 25
94 18
63 14
60 64
96 65
18 31
63 47
14 91
20 60
35 74
99 8
83 82
73 59
88 63
85 47
43 54
85 70
88 63
50 17
42 53
38 85
88 44
1 14
50 37
54 62
98 83
77 29
84 10
69 47
76 57
81 99
55 62
70 84
79 87
18 95
62 82
32 83
90 82
17 45
9 18
49 96
60 29
82 92
82 78
9 59
57 13
62 97
13 39
52 51
70 38
11 27
92 38
21 97
22 4
90 30
80 45
49 95
89 4
34 30
70 34
74 15
85 22
71 56
58 83
15 29
49 15
92 98
5 48
18 75
15 37
87 21
76 80
75 17
54 37
53 73
63 4
65 99
40 19
8 61
12 53
23 3
77 47
21 43
96 2
65 83
92 93
99 86
97 63
42 7
73 77
74 4
97 32
55 51
70 58
52 63
93 65
100 59
79 79
8 68
22 86
70 57
51 79
11 6
40 58
41 18
84 86
35 41
21 96
82 54
20 72
29 93
29 7
87 27
64 77
62 57
63 54
40 68
61 83
1 31
21 35
70 41
13 60
68 24
26 35
20 68
46 11
21 31
37 34
47 71
61 60
44 72
22 98
11 2
44 86
54 54
82 64
22 21
12 11
68 10
65 66
98 7
68 9
10 62
58 36
46 54
13 41
84 35
66 32
76 36
5 84
16 1
87 65
32 60
36 80
53 20
59 30
70 91
93 33
44 66
94 15
73 57
72 46
28 99
62 16
79 13
32 72
11 13
33 80
24 80
70 29
42 46
10 92
44 54
47 87
48 27
7 13
5 59
4 42
11 58
49 92
57 95
38 14
14 33
67 55
55 67
91 73
20 70
95 32
26 10
69 7
15 63
68 39
39 93
20 44
27 35
7 51
27 61
70 92
16 72
67 42
40 85
13 26
62 41
20 7
41 97
42 60
11 73
14 68
43 15
97 43
28 94
79 45
65 9
92 17
98 74
81 89
91 13
62 54
42 72
31 34
59 40
17 4
74 74
12 70
8 24
82 36
10 40
6 64
27 53
48 89
85 87
70 100
12 35
14 41
97 79
53 43
85 2
38 41
26 44
44 57
75 35
63 59
30 23
7 93
65 64
2 76
86 41
24 89
15 96
60 100
96 11
82 34
47 50
37 92
69 82
40 81
79 59
64 8
41 76
69 61
91 36
56 54
95 45
69 47
62 27
27 30
90 85
26 11
78 15
69 51
32 94
39 5
29 73
2 66
80 27
94 63
59 33
17 42
17 91
90 46
33 52
30 34
74 96
96 74
82 49
51 16
50 23
88 66
41 68
74 66
24 37
9 53
18 15
34 40
35 61
87 68
22 50
82 80
71 11
1 8
65 82
30 35
80 15
23 24
39 6
13 53
27 80
34 95
98 73
72 32
92 53
43 13
61 95
77 40
87 85
83 8
69 3
18 35
25 77
88 78
92 33
71 25
58 97
83 97
97 32
10 28
23 57
99 67
52 38
1 63
61 2
56 29
21 66
2 54
55 58
73 27
9 1
96 97
78 52
2 85
44 65
84 64
80 61
54 40
28 66
41 61
86 3
11 64
33 11
28 85
4 23
15 88
47 77
73 87
57 59
17 5
20 75
29 95
39 23
67 63
77 85
72 80
61 97
57 74
56 25
58 64
74 44
36 44
62 36
59 83
35 82
62 74
23 95
84 32
18 20
47 97
63 76
90 44
44 84
21 18
65 21
56 39
87 56
21 1
51 96
18 42
29 86
16 38
13 29
30 53
34 72
87 79
35 31
53 66
49 40
76 24
10 84
6 43
59 27
26 58
16 39
45 3
92 62
28 22
1 89
17 52
94 48
10 6
72 25
48 92
97 67
19 60
19 30
3 26
62 43
5 81
59 45
100 15
25 76
38 40
9 84
52 85
55 100
96 80
5 24
91 19
55 19
62 14
41 39
43 12
11 37
43 74
82 41
26 81
10 78
24 76
11 66
26 66
14 13
70 76
8 84
47 48
27 65
75 29
17 7
23 12
23 82
70 41
14 33
92 41
91 14
60 47
17 8
52 59
21 10
21 57
1 69
40 96
41 37
70 25
90 46
18 6
41 99
98 74
47 68
86 89
99 81
75 14
23 38
84 29
15 64
59 43
85 41
46 88
20 13
48 100
51 9
77 7
77 94
93 76
24 54
51 88
26 39
24 64
65 59
49 86
64 21
25 31
1 94
94 69
5 70
4 44
50 80
39 11
44 61
47 44
55 36
30 91
2 67
79 34
88 88
95 92
98 31
60 32
84 27
1 28
48 51
28 49
23 38
76 86
80 76
64 7
51 2
48 47
15 29
74 35
81 92
4 75
62 13
66 59
50 80
23 8
82 50
50 58
12 95
35 32
49 34
23 61
23 14
9 82
47 32
96 98
88 25
28 93
18 77
68 12
98 56
3 19
69 24
49 25
52 69
93 69
64 45
49 28
79 44
81 44
59 17
15 34
97 75
43 36
82 32
46 1
92 21
8 73
54 34
30 3
82 33
95 66
39 98
49 55
41 12
19 91
10 85
64 51
41 24
68 49
20 99
18 58
98 30
96 64
35 55
45 5
71 6
15 37
10 32
71 34
98 65
70 40
29 91
43 64
18 11
18 8
25 5
37 78
58 11
88 85
20 52
11 58
15 76
21 22
56 96
55 19
71 63
87 53
92 68
72 89
24 64
23 92
69 33
94 7
75 70
42 61
22 95
68 19
37 25
20 85
35 46
100 76
87 86
3 22
79 66
20 30
69 19
60 18
27 25
96 95
17 70
75 29
21 55
55 69
22 80
31 60
62 66
35 95
30 23
19 28
81 46
56 3
76 66
37 95
99 94
78 77
43 45
34 70
47 9
82 93
9 6
57 70
87 28
31 93
96 62
17 87
78 33
73 57
45 89
89 35
38 58
12 10
34 77
71 11
92 52
22 32
31 11
24 76
89 28
44 1
20 18
52 80
4 82
49 97
11 45
4 5
88 45
36 84
82 74
62 47
89 32
35 45
92 3
63 58
82 4
66 70
20 100
63 77
97 49
9 79
10 41
28 68
40 40
95 76
97 3
41 43
17 88
29 30
72 85
94 84
89 13
7 2
61 6
9 12
94 65
28 6
27 94
4 21
26 16
52 15
47 73
35 45
10 94
76 84
72 60
16 92
94 96
75 96
13 53
57 47
46 67
79 26
68 79
67 61
42 13
32 2
91 34
76 99
96 18
65 7
36 91
70 33
43 67
72 90
33 77
20 9
54 17
68 26
67 85
28 34
11 95
66 74
47 80
42 94
87 100
64 94
3 5
60 48
9 51
41 5
8 49
85 13
95 34
94 3
54 100
11 85
74 8
99 55
91 28
19 70
16 77
36 23
5 90
6 75
46 82
88 57
64 94
55 50
46 35
70 68
88 68
10 63
98 9
3 18
55 55
84 45
62 26
4 6
28 44
70 69
45 71
19 76
79 62
2 46
40 32
58 61
1 58
65 56
37 45
38 47
2 32
84 75
65 36
51 14
30 71
41 17
100 13
58 70
58 24
73 85
63 36
84 76
73 72
65 26
64 93
9 21
63 39
34 46
4 17
24 46
20 91
59 51
59 63
5 55
5 17
19 45
21 96
24 96
87 79
7 78
18 87
64 57
89 64
80 74
93 5
76 38
27 87
18 95
8 76
27 9
70 95
70 72
27 87
42 70
11 46
14 8
79 29
79 46
79 23
75 51
63 37
52 42
53 88
45 19
74 71
32 4
56 49
93 86
84 95
90 90
8 62
87 52
41 59
35 95
24 62
40 75
33 2
81 92
33 92
6 40
12 44
57 24
90 25
14 10
82 61
6 76
48 71
39 10
96 93
31 68
53 29
56 7
52 77
79 42
24 18
57 61
21 38
8 20
17 49
40 32
26 55
57 12
24 10
85 4
59 7
69 57
67 23
60 10
25 80
65 21
39 61
76 98
64 29
64 12
9 10
33 32
49 18
6 88
87 72
87 47
59 29
20 20
17 58
100 94
33 61
76 21
32 50
74 38
77 35
81 29
90 53
71 56
44 44
60 17
35 62
18 3
59 46
99 91
46 10
60 77
79 38
16 90
28 72
58 77
57 71
73 74
13 12
83 94
71 18
6 21
47 64
25 3
8 18
6 68
16 69
100 80
78 43
28 92
92 30
50 20
82 69
6 58
66 54
63 1
31 70
88 7
48 43
52 33
91 54
16 45
5 21
82 80
53 41
51 66
42 39
37 34
28 3
24 49
19 17
41 90
82 84
42 89
80 55
74 8
6 72
12 70
79 93
75 14
11 85
98 88
13 15
77 7
15 49
74 15
39 47
12 19
48 35
91 6
42 37
25 48
9 22
75 28
18 26
60 6
39 70
56 75
65 52
85 10
96 20
56 80
72 50
87 49
100 92
82 14
65 72
51 27
15 62
72 88
50 9
97 10
20 90
2 91
35 22
63 2
86 22
59 73
88 94
17 50
99 19
44 19
6 69
84 48
3 83
15 1
16 48
35 45
76 78
84 9
82 6
93 41
52 48
97 48
17 100
45 75
90 39
90 4
25 76
2 35
24 96
61 73
46 10
69 9
49 89
66 45
50 7
66 25
40 53
34 36
34 37
90 16
68 20
86 4
55 69
66 47
53 36
19 81
54 57
52 47
53 75
95 53
84 17
25 91
44 13
24 27
82 20
86 63
8 14
19 31
84 16
49 59
49 56
17 34
39 67
90 16
93 2
45 48
42 68
58 8
12 24
52 98
23 54
10 59
89 11
88 76
63 56
49 78
75 15
22 8
99 25
92 14
65 95
33 1
48 4
1 31
46 45
15 67
67 93
27 67
85 20
97 90
48 27
28 17
17 17
17 20
97 89
24 60
91 86
79 59
38 73
14 25
78 26
12 81
90 17
56 21
59 99
55 74
81 69
3 66
88 82
65 65
83 33
49 14
35 97
43 90
40 48
62 72
18 8
52 53
83 56
70 57
10 55
29 72
41 69
84 59
30 76
93 65
53 95
11 50
20 79
29 88
60 32
7 96
3 69
85 37
81 61
21 17
47 28
57 81
99 68
77 100
57 80
27 13
59 45
8 84
6 49
37 62
72 62
1 18
71 40
3 96
44 33
78 58
95 3
27 71
97 50
17 41
37 53
74 85
35 7
71 1
5 8
58 97
10 16
70 20
40 64
28 89
83 3
43 56
79 42
57 57
35 49
70 18
56 98
99 2
75 84
27 6
71 59
55 5
67 86
93 61
50 30
81 61
100 63
47 88
38 17
39 34
90 75
10 57
86 59
80 58
25 1
57 39
38 34
83 60
68 42
25 81
23 81
69 41
25 73
37 27
70 89
13 89
98 92
9 34
90 49
95 51
77 69
62 71
25 79
64 2
71 59
65 54
61 45
1 92
21 62
64 33
2 9
51 6
95 13
22 89
31 60
26 81
6 82
64 26
2 55
8 88
78 72
83 57
49 80
76 94
48 76
82 78
4 89
33 54
36 22
72 80
15 47
78 6
62 1
56 69
30 70
29 75
86 4
63 51
16 65
2 11
59 37
65 88
32 46
84 5
53 90
86 64
12 7
80 47
52 45
59 39
55 39
57 24
1 13
56 14
99 34
45 3
81 82
34 3
50 1
20 38
36 100
80 43
70 33
13 7
49 52
65 74
85 97
87 28
45 25
15 68
100 69
36 95
7 92
21 11
89 61
94 58
52 30
64 32
62 62
80 7
72 89
28 10
45 31
33 38
55 21
33 12
32 80
69 7
54 88
15 12
93 79
26 6
86 78
63 94
35 9
39 56
21 76
5 61
43 30
23 14
5 77
13 74
75 98
54 60
59 71
37 64
61 57
21 36
55 27
64 73
74 35
4 25
67 71
55 76
43 4
67 89
68 87
91 71
81 71
31 70
93 88
59 47
23 43
38 65
29 36
23 48
60 17
20 81
93 41
12 27
66 25
73 6
83 44
93 63
18 1
29 60
31 96
65 89
55 35
6 60
24 39
47 63
47 19
74 64
57 10
72 1
14 100
15 41
5 89
88 6
95 57
11 46
18 40
37 70
85 17
80 17
42 41
82 55
64 8
68 6
96 74
81 68
29 51
30 42
71 55
36 29
81 47
12 52
92 46
51 1
83 83
6 20
88 39
29 47
39 97
32 46
88 61
43 3
37 31
34 19
95 99
6 27
28 89
100 12
14 8
38 86
71 85
69 75
51 68
14 33
100 23
73 56
60 70
88 82
12 91
58 2
67 72
87 14
82 48
54 71
40 51
17 46
95 24
69 73
19 45
50 2
27 26
30 80
45 97
50 8
80 74
51 14
49 57
79 88
6 4
83 8
44 24
23 57
35 12
98 98
79 98
35 67
16 12
79 1
21 89
49 64
64 35
18 64
3 13
13 78
61 29
74 70
96 69
91 83
37 24
10 98
30 95
3 15
8 97
32 69
70 19
1 24
40 8
81 66
75 18
57 35
3 13
59 61
55 88
56 67
34 63
67 64
12 82
22 87
92 39
58 36
39 74
82 94
74 23
9 69
15 21
94 87
82 54
41 36
57 4
73 66
80 65
20 13
100 34
54 11
8 28
30 97
17 1
90 23
90 58
97 71
31 60
52 26
36 28
8 96
50 44
4 86
10 23
23 38
92 36
82 99
3 85
85 90
66 64
18 88
37 61
73 86
80 91
50 99
4 2
87 60
3 37
19 75
85 10
53 70
72 66
100 86
85 26
96 35
95 30
53 86
7 14
52 62
78 75
94 82
52 46
49 98
99 40
59 88
46 76
75 50
61 90
53 22
23 67
7 21
72 89
75 96
53 65
1 88
22 9
50 90
70 47
1 80
91 83
74 91
56 69
73 76
56 31
5 48
33 60
14 97
98 96
80 45
34 39
57 22
17 30
85 7
79 21
41 38
92 30
93 71
46 68
45 54
72 31
32 6
11 22
36 56
64 54
20 14
72 65
99 98
56 88
84 62
32 42
63 35
16 57
50 88
96 27
43 21
6 79
29 45
71 2
90 72
59 54
75 63
90 19
59 63
44 94
43 7
90 96
80 50
41 87
89 63
81 94
16 46
4 29
32 63
55 77
6 2
82 21
87 76
20 22
3 73
100 92
38 87
67 44
21 30
100 77
14 80
45 36
97 33
98 83
47 84
36 84
16 22
27 24
48 16
29 29
88 71
45 8
100 35
63 48
17 86
62 25
35 22
37 31
60 85
66 7
71 19
46 48
78 58
73 93
69 35
74 17
55 74
49 4
12 48
44 80
18 76
3 30
70 79
29 55
44 62
94 33
41 99
4 93
65 82
42 77
78 72
76 85
23 24
2 28
75 14
31 30
66 42
86 25
84 62
45 25
41 71
87 90
22 29
93 99
26 64
78 12
73 86
32 45
67 58
53 25
44 74
85 71
100 3
25 74
98 49
74 55
94 26
22 2
93 70
38 72
100 34
98 53
15 2
64 55
48 73
47 48
11 93
52 82
63 74
7 64
4 54
40 43
70 11
95 62
86 98
36 19
98 53
71 85
22 74
61 15
35 87
40 49
43 27
74 49
11 48
1 25
14 70
26 3
10 78
67 95
17 38
52 40
38 68
20 71
90 51
49 67
45 65
72 90
21 79
34 54
2 3
32 51
78 55
53 52
86 84
48 39
60 38
17 43
72 88
34 23
13 75
41 22
13 86
93 83
85 61
69 73
36 66
78 21
93 87
59 10
88 19
50 97
51 62
1 42
99 4
12 3
29 88
63 39
59 56
23 88
26 51
81 17
50 76
83 79
45 98
90 78
93 31
32 43
62 13
75 86
5 41
95 75
27 55
32 26
84 70
1 38
93 86
40 10
39 94
24 76
28 50
30 100
96 62
5 89
92 86
93 6
32 87
69 37
29 100
5 23
50 21
74 84
94 59
90 3
94 53
3 1
3 14
81 41
5 87
77 49
6 98
6 51
26 56
89 85
38 31
79 27
22 57
15 4
86 96
32 10
64 97
11 30
14 56
54 35
15 2
100 38
77 85
90 4
88 72
21 14
33 86
46 25
83 11
19 21
46 33
69 35
91 36
85 33
41 22
33 51
93 29
97 99
95 12
88 50
84 78
65 32
29 19
94 57
14 58
13 47
26 76
28 34
3 11
75 56
47 17
92 13
97 66
95 83
21 29
67 95
18 40
96 43
50 62
77 25
42 97
74 90
56 20
92 44
34 81
34 90
59 65
56 61
25 57
8 63
90 30
93 85
82 12
96 80
18 3
25 9
33 31
35 8
27 15
91 58
38 17
46 4
8 54
81 63
4 30
43 41
21 38
41 86
80 29
12 50
46 27
36 46
20 73
55 34
20 27
47 48
75 69
95 63
48 47
38 72
5 14
85 77
98 15
74 53
78 62
55 83
26 48
7 88
93 40
66 4
28 4
71 43
66 68
78 95
95 62
53 38
59 7
1 45
68 75
38 33
72 19
95 80
23 72
68 60
70 40
25 77
47 40
24 40
93 80
77 99
73 37
17 63
67 5
99 58
39 68
50 28
53 34
17 49
14 47
79 57
73 74
79 66
95 68
9 88
74 55
16 8
34 36
2 96
50 40
91 80
66 53
98 90
72 55
57 7
56 51
63 49
36 80
93 100
73 58
53 31
84 7
18 62
76 77
23 3
51 45
92 28
40 55
89 66
24 85
51 33
24 52
54 70
50 13
96 34
44 80
88 1
45 73
44 80
54 57
17 22
23 25
97 68
49 4
58 76
5 69
22 84
25 99
35 3
100 57
79 4
35 64
80 13
91 93
33 94
9 60
42 54
88 88
40 67
52 77
51 58
75 98
75 84
65 40
75 50
13 86
83 40
57 52
73 39
49 78
96 91
74 7
76 3
3 66
37 43
40 62
22 49
83 40
30 55
7 78
43 19
67 80
19 87
97 40
57 7
65 97
22 19
10 42
88 94
88 87
76 53
58 43
74 31
67 92
78 18
62 50
43 21
46 80
17 16
85 72
6 35
62 62
71 35
76 45
58 79
39 33
57 60
84 58
5 26
17 97
64 45
2 86
10 40
80 14
8 35
42 44
40 39
36 73
99 25
88 16
55 97
84 35
23 76
35 44
55 11
39 35
21 54
18 7
93 19
75 97
61 58
79 27
37 21
77 16
18 20
84 66
51 7
8 72
40 71
78 72
58 43
57 76
41 3
63 72
19 77
97 22
63 80
40 59
25 57
24 89
80 99
3 27
81 100
7 86
10 46
93 16
67 70
79 65
12 77
76 81
44 31
79 91
95 48
86 64
24 53
12 60
9 40
28 29
3 44
1 97
76 39
92 85
64 33
40 67
89 68
65 33
45 69
59 12
32 78
30 53
46 19
14 92
56 78
6 1
23 31
1 42
4 63
91 97
12 77
6 55
47 81
1 91
33 50
58 58
37 33
23 2
73 15
42 45
56 9
15 55
14 99
48 97
26 81
78 62
70 72
67 78
23 93
2 67
13 2
11 25
27 71
100 67
4 33
79 87
26 17
37 51
40 45
99 94
25 11
6 51
78 13
35 94
14 54
58 29
26 76
51 26
51 81
53 60
84 30
48 79
46 91
3 92
43 1
73 3
28 61
10 49
32 1
49 6
40 13
49 72
53 75
35 45
90 7
46 35
19 1
41 35
92 60
68 8
98 81
78 100
55 46
5 86
57 90
54 49
24 99
96 92
40 84
1 41
94 46
37 72
70 88
26 81
94 88
33 62
11 40
58 49
86 98
85 7
62 41
46 86
51 13
84 47
49 99
100 58
28 93
80 67
22 1
84 52
6 100
74 49
61 86
56 56
96 21
55 52
53 67
78 95
22 52
81 27
4 83
53 45
21 3
6 97
71 89
6 72
38 80
67 63
32 8
4 71
48 92
88 88
13 21
86 39
43 6
61 23
70 59
38 48
76 2
52 34
65 53
50 36
3 35
91 70
75 3
91 75
22 51
30 16
90 10
20 8
18 73
69 85
97 67
28 30
10 18
68 88
60 48
61 87
19 33
45 13
54 67
97 56
28 4
97 48
61 15
59 64
1 88
97 15
1 92
66 29
33 51
76 82
41 59
76 7
59 16
64 51
72 40
12 54
16 37
20 80
61 61
53 68
7 96
82 49
59 70
51 38
94 6
65 56
100 62
46 83
37 15
41 7
58 95
78 98
26 99
37 53
13 87
20 2
98 76
8 44
49 52
54 29
66 8
49 34
86 97
77 45
81 73
21 47
38 67
28 50
6 34
46 47
24 44
3 80
73 20
47 17
97 7
58 38
87 84
15 38
7 43
52 96
59 96
73 48
100 49
71 16
54 23
16 23
95 95
74 94
13 37
62 36
5 80
13 9
75 94
22 52
69 49
49 18
53 15
3 90
16 97
71 49
40 54
29 43
67 46
49 55
49 85
36 31
97 15
90 41
49 51
34 41
87 10
26 25
64 69
41 35
40 19
73 40
72 26
92 95
23 25
46 47
95 70
60 39
15 4
16 23
28 48
92 17
64 99
59 6
52 77
93 66
10 92
17 30
48 34
57 83
83 79
49 15
59 92
38 92
9 37
36 28
97 13
70 14
93 45
27 16
83 48
54 91
63 34
68 32
33 98
89 32
61 70
33 12
54 50
74 8
66 62
61 27
47 70
79 65
86 71
84 28
34 42
33 61
58 86
97 62
16 98
82 18
89 50
94 78
69 42
93 14
67 1
35 21
31 39
16 9
56 42
92 79
56 61
15 79
31 62
57 13
16 49
51 96
89 44
28 2
89 89
42 90
6 25
32 22
32 24
63 10
15 80
20 67
54 86
16 66
7 69
38 10
40 67
44 17
96 9
89 3
19 18
40 66
69 84
48 79
8 63
78 8
57 69
49 97
20 39
45 70
86 75
7 97
50 77
90 74
35 65
43 15
88 26
27 89
2 84
54 46
3 93
87 17
98 89
98 74
8 62
46 81
9 22
1 85
97 97
28 71
92 16
23 20
30 91
46 20
93 21
93 83
29 75
85 59
57 13
32 84
35 2
70 5
49 71
81 33
21 60
23 10
91 82
42 41
88 82
77 100
92 54
100 74
47 8
70 19
28 9
72 70
22 71
38 48
5 19
65 98
30 82
38 64
33 52
67 15
16 46
92 44
27 16
76 40
92 15
7 74
1 49
89 23
80 58
73 49
4 99
46 64
74 67
13 3
51 99
4 78
41 85
21 81
59 17
78 74
9 37
33 38
91 32
4 73
60 29
48 44
79 72
18 41
52 77
63 4
92 55
99 90
93 24
52 76
81 18
5 63
8 37
51 20
15 58
43 7
16 41
51 100
69 25
13 62
55 42
16 17
98 56
36 67
66 41
43 57
67 96
65 16
40 96
58 98
30 91
2 91
23 8
4 34
26 56
34 99
4 93
53 86
84 69
46 42
42 41
96 5
33 45
11 41
86 66
92 38
15 35
77 26
21 93
35 70
36 27
77 10
46 11
17 15
35 89
14 43
74 9
59 20
36 25
78 88
33 42
69 61
64 44
65 88
7 58
31 86
53 99
29 14
86 91
75 26
86 88
67 83
69 71
59 99
21 95
90 96
29 2
22 41
57 60
93 39
83 66
81 90
33 56
35 58
94 21
40 98
78 30
96 36
2 36
90 67
27 69
1 96
51 70
22 3
33 20
55 77
98 86
18 41
17 79
34 8
56 50
58 9
3 47
9 55
20 26
54 58
83 81
19 81
7 35
87 2
81 67
77 29
53 2
9 68
82 87
53 28
54 72
30 97
72 44
38 24
69 94
89 64
69 96
35 88
38 23
67 12
11 77
83 17
25 69
4 42
17 74
10 30
58 62
8 9
62 1
28 33
79 20
45 45
72 74
72 40
55 50
12 66
41 73
82 69
21 80
81 79
77 4
4 17
6 30
13 21
79 20
66 94
7 7
32 68
33 84
51 91
9 80
80 73
21 38
8 86
19 12
75 31
90 89
27 21
21 33
47 64
15 67
64 34
20 24
63 95
98 91
43 77
95 59
48 66
33 42
60 33
25 42
2 57
100 73
33 92
22 48
92 94
34 81
27 80
28 58
50 88
54 6
54 62
100 53
61 18
56 20
20 94
8 79
40 29
75 65
8 100
81 57
65 30
75 83
89 52
90 94
95 22
37 100
47 86
25 78
25 81
26 30
53 60
85 62
1 95
100 89
39 37
22 9
100 94
6 30
85 48
86 23
46 42
6 63
98 5
14 15
4 90
83 97
13 96
29 30
85 24
49 77
3 89
95 67
91 38
3 76
29 22
73 87
100 84
93 70
100 86
4 16
42 26
65 54
67 30
82 85
12 36
63 86
92 90
93 89
85 83
77 100
83 53
69 34
49 71
82 80
93 30
86 26
34 81
35 31
49 18
67 35
95 51
30 43
70 31
46 4
92 67
14 91
49 23
76 60
52 68
61 49
83 67
10 25
86 42
56 23
27 56
55 89
20 49
91 23
1 22
62 37
58 57
100 41
36 15
47 13
34 71
96 63
29 6
40 59
7 97
11 85
97 92
24 3
4 75
20 21
19 4
75 27
68 89
59 99
44 51
76 50
31 9
51 7
49 8
87 43
93 5
85 66
51 16
75 85
82 85
61 92
79 95
61 54
14 69
47 23
93 9
35 16
61 54
92 90
32 49
92 68
4 49
17 4
6 23
7 54
55 58
44 5
93 59
41 62
58 41
54 91
90 99
54 85
64 27
19 37
100 39
43 2
6 9
40 44
4 4
89 32
24 58
49 50
77 34
70 70
80 43
5 28
60 8
11 56
88 51
70 4
57 49
23 38
32 79
82 13
32 79
41 77
29 58
71 8
38 98
84 59
100 29
21 98
94 76
1 65
10 51
84 26
44 9
90 11
68 42
85 62
9 31
83 43
82 23
74 72
97 30
77 56
48 62
33 5
66 6
84 28
19 2
15 23
42 55
76 70
65 56
76 37
79 94
100 82
77 92
97 68
76 3
19 59
31 46
15 7
14 84
12 86
70 12
10 22
51 74
8 26
41 82
62 42
40 55
27 18
100 41
31 75
36 32
45 31
1 25
59 32
42 98
30 22
62 47
28 13
20 66
10 21
51 71
83 8
97 4
72 100
50 10
15 28
61 22
78 20
7 32
42 13
18 97
72 32
3 39
73 100
70 32
77 60
14 53
71 89
38 91
78 36
43 8
48 83
100 67
31 43
67 100
27 54
60 50
67 10
66 17
73 32
10 45
26 65
88 77
11 17
81 68
86 51
38 96
50 57
21 18
100 93
52 51
22 85
18 53
79 90
99 80
50 90
34 38
2 62
31 60
36 73
80 4
58 21
80 2
85 19
50 3
64 72
78 86
10 80
46 72
3 69
75 83
9 6
67 63
27 78
47 46
54 11
80 92
83 91
2 43
2 84
16 51
17 37
1 53
75 83
6 47
49 99
34 100
11 41
71 86
19 82
99 58
22 37
12 41
20 46
49 86
65 28
37 21
81 87
11 12
23 78
61 30
48 68
90 2
17 38
79 17
94 61
96 19
64 19
91 65
50 76
98 48
88 54
3 100
60 27
87 89
19 35
42 20
42 91
12 73
59 33
93 51
3 82
20 97
41 61
83 29
67 41
99 47
16 16
57 29
3 85
72 79
65 38
74 40
54 57
65 44
53 78
8 93
26 97
84 66
91 21
73 90
88 12
5 18
62 30
42 62
29 89
33 11
35 29
69 60
23 48
59 8
40 68
12 63
38 21
14 98
86 67
78 89
91 68
40 47
36 19
38 86
72 93
20 65
23 81
15 56
46 35
32 74
54 63
49 48
49 96
5 28
23 13
29 3
14 22
83 50
34 28
35 93
92 55
17 87
15 40
60 54
21 83
77 97
74 82
15 84
24 39
37 2
11 97
19 37
18 4
16 97
17 26
91 49
5 78
9 2
63 19
49 21
1 11
39 5
35 83
93 49
1 45
72 53
78 76
51 80
2 78
61 48
3 35
18 26
64 64
96 49
19 38
95 38
56 45
26 88
48 44
9 7
52 58
32 92
64 54
21 2
28 45
49 70
73 50
7 48
33 70
63 75
82 30
38 50
70 33
97 33
67 92
53 12
84 8
3 24
80 22
58 25
91 18
27 22
83 66
40 21
49 85
64 30
8 27
96 94
62 67
7 90
12 18
92 22
22 73
56 72
98 78
1 77
81 99
22 20
24 14
55 98
86 50
23 66
89 7
41 46
9 95
54 80
67 85
94 70
36 18
75 40
62 5
66 25
95 28
37 31
70 79
39 89
54 4
61 51
6 58
24 66
81 37
3 63
87 65
15 28
75 17
85 42
84 55
83 27
71 82
66 24
40 54
94 75
27 3
46 91
21 53
22 29
95 71
25 31
2 53
86 31
31 77
72 84
5 67
78 99
13 66
55 60
37 67
18 22
35 57
90 85
45 54
93 20
32 20
82 52
37 44
93 22
50 29
52 81
24 10
4 36
36 5
29 18
80 11
76 82
92 87
65 66
2 22
38 71
38 90
21 100
91 32
75 44
30 45
45 41
15 54
15 36
27 27
19 53
33 87
60 24
43 58
77 39
50 76
6 82
26 5
63 50
5 82
78 66
88 96
4 80
68 60
92 90
36 86
21 43
33 68
91 87
62 69
80 81
56 63
12 74
61 70
59 46
59 12
10 61
23 30
88 50
37 5
93 50
12 8
84 80
44 9
29 19
17 81
94 77
79 93
8 24
89 71
98 52
68 40
18 80
7 69
78 88
95 24
45 36
36 7
92 18
5 45
59 69
51 55
31 7
89 57
85 49
97 86
30 85
20 77
29 95
45 42
45 28
19 8
41 84
28 1
82 49
88 11
11 16
38 46
33 44
85 41
17 34
24 75
34 58
56 31
23 67
39 33
12 67
47 33
81 29
58 54
39 23
21 93
39 51
2 87
24 20
49 64
22 50
9 90
79 90
64 55
1 23
8 87
8 29
36 30
47 97
78 32
95 4
86 64
49 79
74 7
99 39
74 90
35 33
82 76
28 35
82 29
72 58
10 29
95 4
74 77
10 35
32 22
100 62
50 91
22 57
98 9
78 38
72 93
33 94
17 46
21 77
48 19
53 52
24 87
96 2
65 21
38 96
58 32
3 90
40 30
32 89
10 70
50 93
98 64
85 13
71 96
44 38
22 62
93 23
58 14
29 38
83 73
59 90
81 80
73 71
96 42
2 67
30 31
2 50
3 37
51 1
30 62
79 36
85 5
71 2
8 24
53 41
34 48
76 98
63 38
21 37
20 48
61 37
61 45
65 5
80 16
71 44
72 72
86 52
62 11
31 94
44 67
26 100
31 85
42 86
1 3
77 11
86 100
89 95
10 38
96 69
82 29
66 45
62 28
20 70
1 60
71 37
99 11
10 73
11 64
20 94
96 42
34 94
2 58
98 41
19 11
99 98
27 21
94 59
79 30
91 12
93 7
95 55
67 26
42 51
15 92
74 94
30 85
12 19
20 6
48 37
73 65
92 3
67 13
47 81
7 12
54 72
63 21
80 90
80 13
99 31
29 15
21 64
46 68
26 30
71 87
58 43
93 63
97 59
90 99
61 86
40 87
17 74
17 26
60 69
49 16
50 92
17 50
65 21
29 65
88 89
90 91
16 36
63 88
84 86
76 3
59 43
45 92
25 9
60 59
36 19
90 21
42 57
9 17
95 67
74 12
3 54
17 81
2 35
33 84
56 100
21 92
77 11
15 7
85 79
97 95
32 25
71 31
9 83
50 14
82 32
2 58
53 8
85 15
70 96
78 98
8 50
5 82
87 33
96 83
36 35
67 82
81 54
64 50
64 87
7 8
21 1
24 64
28 65
5 10
14 96
95 73
20 8
1 42
17 36
18 94
22 99
96 24
26 29
38 25
17 18
53 42
48 22
12 79
84 29
66 2
49 100
14 79
1 65
70 87
84 84
52 9
48 94
55 18
80 12
25 37
46 47
84 28
48 9
6 52
53 37
91 27
91 65
16 13
44 40
32 63
23 13
100 89
89 39
97 22
8 87
5 48
81 72
36 30
1 12
22 88
21 96
7 75
69 28
8 94
37 93
56 88
82 20
18 67
85 82
84 56
36 51
35 4
47 56
75 32
13 4
12 67
41 21
39 28
56 29
39 84
22 76
97 12
49 3
30 55
49 1
32 48
68 50
48 65
55 1
83 63
83 86
36 73
34 65
74 1
95 69
29 97
86 35
50 29
49 87
18 73
65 22
17 79
77 9
24 80
33 60
48 49
50 33
26 60
75 51
30 15
14 34
85 18
11 8
31 93
17 5
95 22
77 11
61 43
63 63
5 66
4 76
58 27
93 92
67 6
92 38
61 33
29 41
11 34
55 69
52 4
27 20
49 15
69 16
43 68
30 85
50 50
61 20
17 67
43 98
28 83
58 57
4 76
26 54
89 76
88 13
21 11
76 9
65 74
30 33
28 87
39 13
22 83
11 75
100 96
35 75
33 54
10 91
83 48
15 92
67 59
63 89
45 99
27 7
80 77
31 67
66 25
96 65
94 82
73 37
84 65
49 99
96 93
3 49
46 63
76 55
49 65
45 36
9 88
100 53
46 47
24 10
32 25
92 59
25 80
73 65
31 60
40 85
99 98
75 50
31 98
97 30
34 83
44 57
43 81
34 73
93 17
77 46
5 36
20 24
57 33
70 84
82 10
23 2
100 8
23 56
79 20
22 62
80 20
24 96
79 41
48 2
54 26
69 29
89 57
78 71
77 7
16 95
76 57
46 34
93 15
8 63
12 98
95 83
16 56
38 64
22 59
66 68
82 28
83 40
97 66
98 80
45 4
16 39
91 86
63 15
66 21
5 3
18 88
73 87
98 76
76 82
82 76
2 99
20 55
75 76
65 94
20 37
81 35
44 99
75 53
36 26
89 25
47 79
66 8
87 42
89 35
3 53
83 82
40 62
71 6
9 13
68 70
76 35
71 9
100 46
8 30
4 8
18 10
56 41
88 66
88 79
53 63
3 68
33 66
17 74
3 100
65 34
96 90
66 33
15 85
100 17
12 85
100 7
73 12
66 100
82 84
10 76
8 94
50 18
54 74
15 30
32 9
70 54
10 93
51 53
72 63
3 80
29 50
2 57
28 12
27 10
16 16
95 12
67 58
72 31
74 29
8 1
1 82
33 6
35 94
18 99
88 9
90 43
42 51
62 63
11 83
22 16
57 86
16 82
36 71
80 33
59 15
2 85
30 7
18 36
41 78
11 64
28 64
70 16
94 90
97 85
65 29
38 88
78 77
73 16
57 72
72 41
1 56
88 79
42 77
80 42
74 96
95 68
62 56
26 37
82 81
49 3
10 89
18 61
1 58
54 39
25 53
91 82
56 48
22 57
67 81
36 76
48 80
15 36
94 36
50 80
47 44
87 59
52 13
70 49
98 67
17 86
30 62
62 34
57 85
56 72
65 88
74 11
77 22
85 66
21 61
44 73
38 96
7 52
80 55
92 56
36 71
56 31
29 68
75 19
41 91
82 100
76 44
71 66
63 14
72 38
92 35
34 47
4 20
36 99
17 89
17 60
22 17
2 54
11 58
65 79
76 25
32 85
72 7
65 30
17 10
72 45
45 18
87 86
40 68
18 18
76 90
50 55
20 47
20 65
95 25
19 90
21 43
35 98
74 73
2 61
27 58
78 58
32 71
91 16
46 93
56 70
9 56
52 29
36 53
24 46
50 66
23 5
75 73
16 12
66 45
64 3
4 4
80 96
11 87
42 54
91 49
36 21
85 93
55 84
58 93
19 35
1 92
83 57
41 39
20 38
54 67
78 67
77 66
35 52
77 13
7 94
95 3
23 36
55 7
90 63
63 78
74 11
57 96
48 98
16 88
94 48
47 25
100 12
13 55
90 60
55 12
42 9
77 23
33 86
75 50
13 24
42 62
55 3
22 56
31 92
94 95
15 99
96 58
88 51
41 24
41 88
58 34
71 86
52 67
81 19
28 59
62 9
31 67
70 30
43 3
7 80
54 23
54 93
4 39
50 16
89 87
64 6
77 39
74 69
82 56
33 65
66 23
46 56
3 55
71 72
42 2
6 76
15 70
83 93
42 75
85 85
24 65
29 75
72 54
78 46
53 100
64 83
13 14
33 6
76 34
92 62
49 31
89 52
7 56
1 77
76 23
64 46
61 82
74 95
3 57
19 91
52 77
46 51
65 63
1 84
13 50
65 46
29 54
5 74
25 53
2 85
67 5
13 26
41 40
42 43
60 2
86 28
68 31
24 3
85 56
47 52
24 1
87 51
65 98
57 58
37 48
12 59
63 79
14 79
40 69
34 18
9 46
33 92
51 81
72 14
16 55
56 35
65 79
49 61
7 89
18 76
27 27
6 1
18 64
19 98
46 15
4 6
71 2
90 55
3 7
48 61
87 38
50 73
26 13
87 25
71 78
36 50
24 14
11 2
42 82
71 33
84 17
73 1
79 3
88 9
91 86
39 21
46 91
50 63
4 14
23 78
73 76
34 91
36 39
29 70
11 58
45 95
2 45
65 4
59 10
58 28
40 50
13 63
53 80
75 92
95 73
33 33
100 47
35 59
50 17
28 45
10 60
75 57
45 29
59 96
14 52
100 38
14 56
80 9
72 49
42 39
44 70
60 54
55 100
82 75
69 67
29 92
86 93
41 82
28 12
87 92
12 29
51 80
66 16
10 88
76 51
16 72
98 47
53 47
19 65
22 95
6 60
76 93
29 38
75 84
83 44
88 61
52 75
85 83
80 25
22 96
98 92
2 61
51 38
59 72
92 25
55 37
47 68
93 93
75 50
89 72
85 16
94 48
44 91
71 85
80 15
56 74
43 35
23 57
43 27
30 80
99 24
82 59
49 46
38 25
55 82
20 68
23 31
55 17
83 91
53 87
57 87
89 61
72 60
10 80
90 47
84 57
16 89
54 87
89 25
7 60
34 45
32 38
11 13
4 93
37 21
81 80
47 60
48 64
30 60
78 63
96 60
41 47
91 60
68 70
61 65
61 76
50 34
28 12
38 14
59 63
92 77
36 64
72 51
8 72
99 72
64 98
44 32
94 39
8 12
27 82
20 26
57 61
58 91
57 72
43 72
89 72
48 43
30 27
60 78
64 57
36 44
57 96
50 48
66 85
6 91
69 73
87 95
40 62
7 69
20 39
19 88
43 3
96 85
23 39
89 31
3 43
24 39
86 15
70 10
73 86
76 24
18 85
91 91
19 75
8 32
72 20
16 27
4 72
77 15
89 40
4 24
39 23
37 47
36 25
75 21
53 25
11 60
48 5
42 78
34 95
65 1
43 93
63 14
24 9
60 51
45 75
82 1
48 95
72 25
26 100
48 32
42 24
12 19
95 61
60 71
25 53
30 2
57 98
91 100
32 27
39 7
97 85
44 27
13 73
48 15
60 59
66 18
23 76
73 50
76 15
56 86
82 45
26 48
68 42
97 56
54 72
71 67
38 71
5 83
1 86
8 74
9 35
67 55
8 21
7 33
52 100
20 99
61 57
18 44
51 44
69 45
52 18
79 73
12 81
51 94
74 20
13 42
39 3
92 37
36 23
60 96
14 94
18 48
82 80
63 42
58 13
98 79
35 47
8 38
57 87
64 51
73 13
52 31
82 30
32 16
45 79
11 23
82 29
70 8
67 82
15 36
23 55
3 77
40 22
73 57
43 85
34 75
13 31
18 22
45 7
37 91
65 31
45 67
32 54
75 78
10 10
98 43
16 76
17 70
53 55
100 8
89 60
2 74
91 94
33 17
11 63
25 7
48 37
77 6
64 75
33 21
48 91
42 23
83 28
79 65
19 24
74 20
14 20
56 80
70 56
90 8
95 99
51 1
74 62
89 37
92 73
92 29
84 100
83 71
93 42
54 60
62 45
34 37
85 85
69 64
36 9
50 32
88 10
66 85
67 92
16 45
15 9
64 84
7 25
5 29
43 68
12 60
22 71
98 39
9 45
91 16
46 73
39 49
57 59
96 95
56 24
41 31
1 84
47 2
20 77
83 12
6 86
27 87
74 35
22 22
20 74
41 76
46 68
84 61
4 30
24 32
40 52
35 48
93 72
85 45
36 47
66 64
42 67
60 68
74 21
82 57
65 14
33 6
90 91
83 71
12 31
2 58
14 23
69 90
65 61
24 98
80 30
34 76
22 49
51 5
31 48
69 13
76 66
88 82
41 77
58 72
39 47
8 54
84 56
66 23
51 53
68 95
74 25
48 79
79 44
27 49
12 71
32 75
23 87
16 97
99 10
81 92
71 6
74 40
90 62
52 24
46 19
4 72
1 67
73 58
77 63
63 13
64 50
25 39
18 15
64 39
84 37
38 38
84 84
78 52
72 89
33 30
5 48
83 74
96 82
78 31
75 43
98 33
56 99
90 71
7 19
75 45
69 38
42 78
17 5
58 15
99 90
54 26
78 18
52 18
49 3
22 73
38 18
74 99
20 79
6 100
2 35
67 21
3 51
57 74
2 84
39 40
48 61
68 29
65 82
79 93
4 51
5 84
79 24
29 23
11 49
57 63
46 100
96 61
34 45
11 28
48 73
76 32
47 90
13 8
65 33
75 98
64 62
97 15
94 4
38 38
36 9
20 38
88 97
54 5
88 67
51 94
98 64
80 97
35 67
78 59
18 90
72 28
18 98
16 22
7 53
77 66
75 63
90 13
92 25
51 93
56 25
83 97
68 66
50 9
8 49
12 76
53 10
75 29
20 35
31 90
50 65
22 37
67 22
77 75
18 83
46 79
75 30
40 54
52 93
80 88
44 67
52 36
84 13
41 21
52 42
25 87
48 5
19 6
49 5
5 43
59 23
28 20
29 81
78 63
90 82
85 78
85 23
73 9
26 55
84 53
54 36
93 48
80 86
9 94
35 71
19 57
58 73
49 54
77 87
61 42
31 75
21 5
94 84
15 11
25 32
73 81
58 35
41 93
8 11
36 56
27 72
64 56
91 72
27 57
1 63
44 85
16 69
47 32
30 78
48 70
31 40
14 35
22 99
91 82
72 95
77 5
55 93
34 28
68 74
5 66
87 32
91 95
41 18
21 80
67 8
46 22
84 6
59 20
15 25
72 44
10 5
62 21
8 63
95 24
47 3
78 42
77 82
79 53
61 79
74 27
25 56
75 26
2 46
5 9
33 83
27 98
65 46
29 2
5 90
43 43
83 8
25 69
10 51
54 57
49 92
87 92
83 22
47 38
71 81
37 77
63 94
92 18
58 24
79 67
32 43
55 77
52 95
44 100
2 86
1 7
82 32
94 62
39 45
31 6
70 67
29 68
57 50
39 6
11 45
67 51
83 75
37 35
88 80
36 39
15 58
42 12
42 10
21 65
11 67
8 9
70 24
52 97
3 52
99 6
27 36
94 56
64 36
16 31
6 37
43 97
5 39
54 59
79 46
56 2
16 22
77 91
90 99
92 75
19 79
78 97
50 98
89 2
35 34
27 43
60 100
17 74
93 65
19 98
100 55
9 76
30 76
83 62
85 13
51 39
53 53
75 40
98 2
10 83
23 22
35 22
61 11
79 31
82 94
55 49
39 32
33 4
56 97
29 93
40 4
27 35
41 46
41 79
34 92
96 26
23 42
83 85
67 26
33 33
89 12
95 100
26 2
69 51
81 63
86 12
91 15
58 77
88 56
76 22
43 36
6 12
45 81
18 63
47 63
41 29
66 72
63 49
62 65
3 54
14 3
22 66
46 50
23 1
84 37
71 100
90 45
66 100
64 53
7 41
90 85
47 52
17 6
48 16
84 64
67 72
34 17
4 53
50 7
58 29
45 60
55 93
93 81
22 48
67 52
73 4
32 30
80 93
28 59
25 3
30 64
59 39
74 30
63 66
50 6
67 84
59 49
26 32
80 31
56 53
51 55
35 4
66 31
95 64
42 42
50 47
5 70
48 9
50 75
9 2
70 43
72 1
40 30
14 28
79 91
43 10
81 8
18 83
86 11
11 79
24 1
43 81
12 20
79 89
98 58
10 4
17 86
36 82
91 100
72 99
46 34
35 98
94 75
69 89
66 1
27 70
18 21
90 84
18 93
32 17
34 75
16 59
85 66
61 21
5 94
33 49
8 44
98 65
27 4
19 42
45 22
53 60
51 80
86 88
53 63
42 39
77 44
24 39
9 72
66 36
44 37
10 51
93 4
90 93
61 36
16 33
83 96
4 36
80 13
15 34
98 87
15 64
20 23
7 66
20 4
22 95
1 14
49 10
19 47
75 80
50 86
98 53
63 39
4 35
43 14
72 59
41 78
32 16
53 53
32 22
29 83
91 96
38 86
64 58
70 98
38 2
17 75
34 30
68 1
55 33
66 34
86 65
2 41
50 90
53 59
88 6
14 91
99 20
99 86
86 27
1 75
78 65
10 92
65 61
45 51
20 47
65 15
29 68
59 80
27 85
82 47
20 92
94 95
1 5
27 23
98 70
71 7
19 59
86 63
85 53
83 11
55 26
12 2
49 83
30 34
83 62
63 4
37 49
67 62
89 73
99 91
77 68
50 18
34 43
73 20
62 80
70 15
98 13
33 88
95 44
82 23
66 86
70 15
46 53
56 29
24 35
24 24
70 45
33 24
24 55
46 18
69 94
45 67
66 12
47 8
93 48
70 65
16 4
34 49
25 12
58 73
53 38
78 18
96 93
95 96
32 45
14 93
15 45
38 22
21 53
65 54
55 77
31 13
58 86
88 51
97 64
64 48
22 5
30 96
84 24
80 5
77 90
31 62
87 16
3 44
84 28
12 83
41 67
97 24
20 76
60 80
53 11
66 10
36 26
24 82
54 88
84 87
4 30
79 39
1 83
35 30
92 55
64 54
15 68
30 26
100 100
55 69
83 93
92 43
66 22
53 63
3 32
45 85
25 64
62 35
60 65
17 68
12 98
72 36
32 52
62 39
9 14
47 44
61 30
71 47
49 62
29 76
53 34
100 25
4 31
39 49
22 9
14 6
40 85
66 32
48 56
95 17
58 59
84 6
18 40
91 91
87 58
100 14
85 31
28 27
34 91
28 38
31 4
4 83
31 88
72 20
26 89
67 22
55 14
31 81
84 9
63 58
19 56
91 90
51 23
61 28
99 71
9 39
86 94
27 31
89 25
66 56
12 42
43 6
96 60
78 99
92 8
95 52
79 97
19 43
97 100
28 49
54 100
63 46
50 71
95 13
76 73
62 48
33 89
9 60
18 78
23 6
9 38
39 74
67 73
48 47
15 58
78 100
8 83
26 61
61 56
67 56
68 78
27 18
97 25
12 91
57 25
75 61
93 74
18 86
35 38
28 69
66 13
17 8
46 57
41 95
87 43
29 19
49 75
98 19
21 99
14 97
54 4
85 55
37 56
88 55
23 85
84 35
60 100
67 59
15 38
70 99
13 61
51 86
6 63
36 99
81 1
22 7
40 23
5 50
95 48
85 78
57 22
75 61
82 17
9 73
54 20
1 62
79 45
52 87
27 9
36 80
88 16
6 77
71 80
52 63
41 5
62 98
71 52
16 64
34 11
8 11
4 88
96 100
73 12
51 61
38 77
80 6
7 78
89 69
48 51
77 14
39 9
5 100
92 91
22 67
79 28
41 30
45 17
81 24
30 2
39 11
74 41
99 12
100 82
2 43
44 23
86 98
34 37
56 79
5 70
2 48
56 17
93 61
98 21
99 32
49 4
51 14
50 93
4 94
59 44
36 9
25 83
22 40
31 3
86 4
32 61
72 56
23 15
87 15
52 38
61 79
61 64
74 51
61 93
81 37
14 52
86 79
3 27
4 70
27 9
25 57
2 67
62 80
46 78
17 21
48 94
59 65
27 17
20 68
97 84
11 93
63 53
5 45
68 94
75 82
20 25
36 35
80 12
65 17
5 95
82 64
38 79
69 61
14 31
63 45
77 52
2 98
72 48
42 67
6 8
39 72
31 55
49 53
51 6
87 58
21 65
14 26
92 30
76 1
43 6
47 98
88 33
65 2
3 91
68 8
8 86
42 32
77 1
69 58
94 66
25 69
43 74
31 9
66 29
76 4
52 98
35 91
74 44
81 64
51 62
58 9
4 34
96 52
12 16
1 36
25 35
25 62
78 6
25 80
100 82
45 23
34 51
35 41
87 26
28 30
58 44
76 30
51 1
82 23
48 92
85 45
96 93
72 51
66 67
38 75
56 95
52 56
66 9
5 71
91 92
70 29
31 45
34 73
97 37
8 56
50 16
4 11
10 96
19 53
60 39
49 7
14 21
95 65
64 82
89 19
17 74
4 97
31 64
65 48
30 33
79 30
15 46
5 60
99 80
42 90
95 84
76 3
69 60
86 62
17 94
78 51
70 89
51 81
83 97
18 41
6 10
23 31
79 18
56 21
64 2
45 73
12 47
67 90
60 98
40 49
17 98
24 16
50 16
43 20
80 50
98 97
36 70
75 60
94 18
92 93
10 39
21 19
86 81
54 67
18 94
14 85
42 78
63 81
26 73
99 39
65 6
65 98
97 58
34 70
32 98
86 48
62 31
34 75
47 98
10 80
31 46
92 35
14 68
46 34
53 66
11 70
34 95
33 47
68 61
22 26
1 69
32 68
14 56
75 3
80 28
67 52
7 33
18 70
56 70
28 2
36 61
25 31
3 37
10 51
87 22
26 88
19 63
5 62
20 15
16 52
64 67
73 75
40 95
65 39
86 78
86 50
40 33
69 76
9 62
25 24
87 66
39 29
62 96
27 12
90 8
78 93
49 99
20 79
96 59
13 25
10 63
22 5
40 89
13 62
32 88
20 24
40 92
44 61
92 65
97 58
5 66
43 31
65 79
2 80
71 55
86 64
32 67
47 36
91 28
28 61
40 61
39 1
6 87
1 10
18 61
93 88
16 51
48 47
77 9
65 17
73 79
6 89
57 86
23 55
91 3
89 89
92 42
44 78
48 16
98 20
26 45
92 64
46 25
17 53
96 19
47 41
83 57
19 54
27 14
40 37
85 53
69 57
15 85
60 54
48 92
56 87
40 72
40 91
38 11
10 39
39 52
17 54
94 36
8 3
45 2
9 49
58 21
100 29
45 20
65 16
37 69
88 67
44 99
39 52
55 7
39 72
83 38
57 72
15 77
31 36
84 26
78 44
93 86
64 70
9 37
66 26
12 93
41 96
3 70
6 4
16 77
87 95
48 36
20 4
76 33
37 80
98 79
40 60
64 19
26 98
2 84
54 87
11 74
77 65
34 64
65 46
56 91
52 33
98 42
66 5
48 48
31 69
93 39
6 31
18 88
66 67
66 68
19 78
68 58
28 84
77 98
41 24
80 6
33 52
39 55
40 85
13 85
76 82
76 44
45 73
15 24
49 54
13 16
70 18
49 6
93 15
44 18
56 12
8 43
28 72
72 95
11 36
64 78
57 32
56 5
65 27
59 39
34 65
17 42
79 24
84 22
80 82
92 54
45 10
28 16
78 78
39 11
17 96
61 83
52 97
77 13
94 60
3 20
18 58
95 77
70 74
5 69
24 9
38 30
41 86
62 95
44 85
71 81
30 91
32 63
63 27
29 21
54 37
43 61
89 70
73 88
4 65
92 11
32 23
25 95
76 67
36 43
40 36
22 42
11 16
78 87
5 81
64 32
56 51
21 5
100 45
28 91
44 98
26 34
4 67
70 28
95 36
55 37
24 43
26 69
84 98
40 27
86 27
72 69
85 99
43 8
68 12
7 22
31 21
87 47
38 46
76 85
75 12
71 26
4 70
57 30
3 41
86 75
11 25
68 7
1 89
7 6
84 92
50 14
80 96
57 36
49 90
19 55
4 95
2 26
10 19
14 55
23 81
19 2
51 57
89 58
60 72
49 12
82 58
31 3
69 76
75 29
5 79
15 80
89 86
94 49
78 76
92 51
5 27
37 79
6 3
1 97
36 76
31 94
28 49
18 11
56 21
78 94
89 80
54 61
84 74
56 19
82 68
71 8
20 68
81 79
19 29
69 73
43 2
91 2
49 25
10 48
35 34
47 73
42 90
9 20
10 83
18 93
93 31
72 45
15 8
5 54
24 58
39 47
26 24
36 43
38 48
31 43
68 6
53 4
29 89
83 71
46 94
23 65
91 49
13 41
51 68
68 12
72 19
27 15
88 99
91 21
66 54
98 2
1 79
77 54
63 25
60 65
41 68
33 77
5 49
46 92
38 41
24 23
93 70
61 55
42 98
26 43
78 21
90 66
11 78
22 60
88 39
77 12
76 33
21 98
71 10
1 86
10 25
86 20
9 19
51 64
25 23
51 72
81 47
44 71
83 49
6 7
89 96
32 32
25 15
76 20
87 40
42 40
13 66
18 5
2 67
88 65
74 91
47 87
40 32
45 22
63 82
58 1
51 38
66 46
65 25
70 55
13 61
10 85
76 12
79 77
79 3
80 69
21 81
1 75
15 41
3 70
24 70
92 74
93 35
17 38
33 98
2 56
73 87
99 28
64 46
82 87
52 76
84 82
24 55
80 18
79 34
12 88
15 60
18 94
79 17
8 87
94 3
78 28
39 8
98 3
73 86
96 35
55 20
15 66
23 82
96 15
60 6
35 48
42 95
97 26
51 51
8 88
25 48
72 27
15 92
27 100
45 25
73 5
40 8
80 10
1 47
32 40
82 90
22 52
2 78
11 91
8 40
99 23
71 77
16 48
89 52
64 89
89 100
67 11
99 88
35 73
87 71
61 15
21 10
48 86
21 75
41 23
47 67
1 66
45 55
17 100
25 38
30 32
32 43
18 25
43 35
8 44
29 45
65 53
9 46
9 66
1 55
50 24
14 8
71 39
34 32
54 34
25 4
100 10
46 75
67 77
51 31
32 38
19 52
79 45
11 68
75 38
21 20
47 63
42 58
9 68
72 9
59 55
95 18
81 83
61 12
61 60
93 38
79 59
62 26
97 57
1 17
84 74
3 10
73 15
66 51
86 21
75 83
58 63
34 70
76 62
100 49
67 66
88 68
80 92
43 17
12 24
95 11
30 83
51 11
97 17
33 13
96 56
42 4
63 8
53 54
42 34
52 96
81 71
22 87
49 39
89 65
70 6
41 67
46 46
70 30
77 65
22 22
3 80
93 31
10 38
18 72
22 5
11 97
15 11
52 90
20 18
31 94
21 2
73 72
33 79
48 5
14 25
50 17
13 28
64 78
17 99
10 100
31 92
90 47
58 68
78 87
14 46
24 62
76 48
41 44
95 18
37 21
85 59
89 41
15 39
13 47
82 17
62 54
23 30
42 65
21 96
72 15
48 86
30 38
16 58
34 95
92 11
20 46
73 49
20 24
62 50
69 62
44 81
87 65
64 36
69 7
78 23
22 18
52 85
31 12
15 12
78 47
94 7
47 56
91 28
76 18
41 18
41 32
91 14
48 95
85 14
38 19
35 34
48 42
31 44
54 69
18 1
19 85
72 40
87 80
49 29
47 1
1 32
67 19
3 78
35 88
88 18
35 72
57 50
74 37
35 75
49 73
90 59
24 30
60 58
53 70
38 26
20 95
5 69
9 54
48 44
44 25
60 94
81 10
36 88
98 25
99 90
27 40
52 60
62 39
33 26
96 98
99 74
22 26
64 60
22 49
17 87
91 23
88 33
80 54
64 34
92 18
6 59
84 1
2 51
62 25
8 54
28 93
90 91
12 67
71 15
8 56
7 98
40 47
20 84
55 69
5 15
61 3
49 79
60 80
92 87
50 91
12 24
43 41
31 82
72 6
95 87
26 85
78 98
11 87
80 23
1 41
7 9
28 81
98 32
8 8
83 80
90 18
63 19
21 53
71 55
3 48
41 17
30 23
70 66
50 41
55 99
85 87
11 8
5 42
12 33
23 25
89 14
34 27
53 98
43 60
31 13
3 30
30 52
1 3
61 95
96 94
78 34
89 69
10 30
88 6
54 82
82 41
39 36
25 10
34 23
53 47
92 51
79 7
88 50
13 10
49 87
16 71
86 46
11 98
41 74
59 49
36 53
41 55
88 79
54 49
21 53
3 22
5 42
6 51
66 81
50 55
54 17
76 41
51 13
23 46
57 95
38 1
29 74
24 10
89 22
59 7
5 36
55 13
33 83
71 95
6 66
56 59
79 24
50 94
15 66
48 42
47 30
53 72
85 65
81 31
25 32
26 48
41 41
3 33
24 54
70 49
92 44
78 34
55 96
76 1
74 43
54 82
88 55
56 67
58 26
77 24
73 77
73 62
98 65
8 72
31 20
57 66
80 25
91 21
12 32
77 13
43 61
32 86
4 6
90 36
48 100
83 5
16 80
18 74
76 73
87 49
70 10
46 36
64 72
89 78
99 63
62 70
20 76
74 16
55 64
21 31
29 24
90 44
13 96
59 43
42 35
25 82
38 80
14 97
40 12
55 25
48 16
78 83
16 33
16 78
11 96
99 32
97 36
10 42
92 73
38 33
52 2
96 92
9 72
6 53
45 13
82 6
20 46
55 95
50 53
84 19
72 77
57 20
26 62
67 68
83 55
23 29
3 100
56 7
57 43
87 58
6 41
41 17
38 85
50 6
3 59
38 55
75 69
89 85
62 91
30 23
15 46
32 44
62 62
35 49
5 71
9 20
15 42
89 31
65 64
22 87
99 14
63 79
7 41
43 34
32 15
32 52
25 99
77 95
5 25
92 59
17 67
22 30
40 89
2 27
78 60
96 75
72 17
43 63
11 52
80 86
71 99
32 6
79 12
31 93
16 64
43 8
23 19
29 18
87 24
41 39
1 89
28 73
77 86
51 10
76 23
64 14
12 54
53 73
62 31
80 25
85 82
36 46
32 54
32 26
20 83
53 85
22 56
51 52
57 10
67 80
83 62
59 90
78 15
68 88
22 94
19 52
60 3
57 90
59 48
48 72
26 84
59 78
19 5
61 96
64 36
59 13
88 17
31 63
64 70
38 2
15 31
6 39
68 22
98 70
30 2
70 6
75 92
81 17
52 95
32 59
15 45
14 30
70 54
60 74
98 24
44 83
61 36
37 100
48 6
6 66
29 91
85 89
69 60
9 35
16 96
59 29
90 36
81 18
95 72
54 89
84 79
27 92
11 59
67 38
59 92
62 35
48 61
68 74
55 18
98 96
22 6
22 25
71 87
23 95
48 23
9 40
28 68
16 31
98 82
60 95
55 35
70 21
59 85
14 67
98 4
33 55
5 82
74 80
30 70
87 52
8 95
26 38
6 33
68 93
16 35
76 53
4 87
22 94
51 52
74 85
22 29
8 99
2 27
99 45
26 12
19 93
2 17
15 85
82 88
45 7
67 87
83 11
2 47
86 45
80 60
55 70
59 74
24 61
73 29
40 79
67 83
35 58
8 30
30 34
70 33
4 77
53 82
84 25
20 57
75 72
85 17
71 21
24 85
88 67
49 84
89 70
22 15
56 48
84 17
100 50
55 68
42 95
15 76
38 22
84 45
68 3
35 88
16 78
95 18
63 32
30 88
53 12
3 23
73 81
87 20
78 47
21 31
22 23
59 74
50 7
84 22
67 70
17 93
24 94
71 64
39 76
93 86
31 51
71 91
67 77
76 20
38 23
74 44
47 71
82 83
98 40
92 71
53 26
25 71
55 55
95 61
40 29
78 32
93 79
69 82
73 28
15 65
63 75
65 41
92 95
43 5
7 36
97 87
89 74
78 42
79 60
91 89
53 26
27 5
19 89
87 55
36 87
16 49
48 91
81 41
86 23
92 57
36 31
36 30
9 36
77 93
89 39
23 63
93 69
36 92
64 46
68 11
78 81
68 92
24 95
38 36
9 81
100 88
9 77
85 22
1 36
6 98
46 32
80 35
43 88
25 95
37 96
86 6
98 89
65 23
2 11
97 48
55 90
77 52
6 93
73 35
62 31
84 1
93 11
100 46
72 60
98 2
28 74
87 7
67 9
78 10
93 48
86 63
82 37
66 33
50 11
52 47
11 16
35 63
55 94
27 94
5 79
2 3
39 3
15 2
31 38
67 53
81 91
33 60
19 91
3 26
18 59
82 24
58 87
92 3
90 87
48 2
64 30
95 63
61 41
3 21
100 94
51 3
94 85
94 13
30 52
74 60
66 29
7 9
73 25
50 4
89 60
45 4
12 25
30 46
43 49
42 80
55 80
55 48
1 67
57 91
40 70
100 34
14 23
56 10
38 86
10 68
2 97
16 45
19 25
59 75
44 35
85 73
96 22
100 100
33 28
76 45
66 25
44 99
37 12
71 78
10 70
99 79
71 42
82 27
56 53
26 73
77 57
93 14
63 41
71 17
70 12
94 5
56 4
57 96
89 51
9 78
44 43
12 20
93 57
6 49
91 50
93 8
73 96
70 27
9 87
71 10
1 94
88 92
100 6
32 23
58 2
62 1
57 50
82 6
79 12
77 65
47 7
67 2
97 36
44 15
55 43
10 75
23 99
66 64
14 15
96 64
96 2
99 70
64 35
95 72
3 92
50 59
57 83
43 31
16 89
85 33
55 15
10 43
46 57
64 81
6 49
55 81
13 30
83 22
36 36
85 90
30 87
79 5
61 74
24 27
13 3
87 89
87 16
23 49
60 69
80 68
88 98
12 96
23 28
27 100
17 78
87 58
33 69
16 20
49 10
3 88
53 99
87 65
26 60
42 51
69 98
77 15
29 80
55 30
32 53
56 88
43 62
94 97
6 98
31 95
8 10
9 81
95 25
9 81
2 33
78 18
8 60
23 15
85 12
81 26
81 12
100 10
55 39
78 53
58 5
55 78
9 94
9 44
58 66
56 71
16 28
40 18
40 89
71 3
41 16
28 6
32 28
63 62
40 17
95 45
25 1
10 89
86 46
41 98
5 69
8 98
20 16
13 70
62 23
99 91
53 48
23 69
94 87
48 35
91 39
7 80
25 93
26 99
66 9
69 46
48 87
62 9
60 37
71 55
3 85
4 72
42 38
85 29
68 75
98 38
23 18
100 48
21 52
74 81
42 73
97 95
84 84
37 30
24 44
53 14
89 51
58 80
73 17
82 77
39 57
23 22
26 37
19 98
82 44
25 68
38 56
46 92
45 11
7 15
86 82
61 98
41 86
95 29
85 64
59 24
25 88
61 12
33 53
38 39
21 71
97 98
76 43
10 55
98 47
92 9
97 61
84 61
92 36
87 1
89 39
17 36
71 10
41 85
72 17
46 63
95 1
83 7
14 13
22 42
75 79
33 22
37 44
80 46
6 51
47 7
11 72
52 67
43 23
4 48
82 14
15 67
76 100
29 74
22 100
5 60
74 56
53 78
16 48
24 64
74 1
38 9
88 77
39 27
98 3
37 15
33 57
96 40
41 71
66 54
87 54
74 16
61 65
51 97
98 3
57 38
78 76
79 92
42 35
86 87
94 14
67 80
15 94
15 94
14 49
78 82
46 6
45 59
71 5
83 40
78 12
68 93
85 81
13 80
86 37
34 80
49 47
34 15
58 57
46 94
44 80
68 84
58 1
62 22
44 16
94 12
79 100
1 93
100 17
83 67
75 41
44 52
61 13
92 50
29 21
49 25
12 70
95 98
22 8
53 52
25 76
20 6
3 76
64 77
61 64
86 28
87 62
86 85
57 27
55 99
77 95
60 89
60 99
21 26
15 58
9 27
69 16
86 2
49 81
53 2
91 45
61 40
89 60
56 75
61 50
40 94
74 31
1 7
72 90
62 55
13 24
54 80
89 65
33 22
81 34
93 39
22 74
54 99
55 90
94 11
43 74
86 49
50 58
58 59
89 57
74 74
7 94
56 47
9 68
59 49
4 59
44 81
50 89
97 50
43 23
10 54
24 27
89 33
7 34
88 75
70 67
62 88
57 10
74 7
16 15
43 94
45 93
99 87
79 66
38 38
19 22
49 63
21 8
98 19
50 38
47 86
29 45
92 64
62 75
1 91
4 35
43 15
71 10
19 27
59 9
100 90
12 43
33 75
41 73
47 29
48 57
17 82
55 65
79 12
80 100
23 96
11 30
94 32
60 24
73 69
71 66
76 68
84 5
29 56
84 21
66 85
47 34
78 98
4 99
59 100
55 62
47 39
15 22
17 18
78 60
70 80
73 11
75 76
68 56
90 57
92 5
36 19
8 61
48 49
69 51
8 43
48 79
99 54
54 75
86 58
52 78
67 58
100 44
46 69
38 93
16 95
69 34
63 47
71 48
68 8
19 62
87 74
27 88
54 56
85 93
71 63
31 38
21 7
27 15
29 53
31 80
28 39
91 67
5 35
67 26
24 32
5 10
99 45
76 75
60 57
89 30
31 85
86 95
59 90
89 42
83 77
69 87
38 1
69 50
30 60
46 8
2 96
34 94
40 99
66 99
78 65
81 8
37 81
22 32
74 31
13 15
74 7
8 18
1 97
17 83
54 100
63 86
78 17
36 28
64 51
100 9
14 92
8 23
78 26
32 63
10 84
41 55
4 23
43 72
38 92
83 25
56 99
100 47
100 26
24 17
24 34
32 10
22 99
71 98
96 59
99 74
2 75
70 54
24 36
75 15
75 93
98 82
52 9
42 82
38 3
5 20
70 19
56 92
96 8
48 66
77 66
30 13
96 24
75 74
8 70
99 63
99 16
72 93
24 3
15 86
55 4
90 55
69 52
22 37
79 75
51 60
42 33
47 9
50 84
5 32
35 62
53 97
70 51
88 3
33 61
60 65
40 68
100 96
7 44
54 100
79 2
79 90
11 99
51 66
10 91
44 16
2 46
44 8
28 9
70 56
20 25
13 53
70 38
43 23
37 70
97 59
50 48
14 75
79 59
75 65
38 73
18 37
19 30
94 52
61 20
57 76
100 37
11 39
50 28
34 78
28 14
98 55
70 39
96 76
47 59
40 86
21 14
36 98
86 6
59 45
80 99
39 61
2 23
30 51
93 96
84 71
36 36
72 4
89 64
8 89
8 58
79 53
80 47
10 42
63 14
49 18
55 39
96 47
42 26
90 6
60 52
42 85
28 17
68 9
10 33
45 11
2 53
74 33
36 16
21 27
57 89
55 40
9 96
61 2
44 97
91 90
7 69
84 4
9 62
46 50
6 49
93 33
66 23
30 75
5 27
83 11
19 18
14 89
87 45
56 48
34 54
11 82
6 77
95 44
16 27
73 53
71 83
92 97
34 63
25 38
57 88
51 40
69 25
85 17
15 35
91 23
50 49
99 64
17 74
74 9
95 9
37 53
60 54
56 63
4 38
68 15

testCase1part1and2.txt

12
8 50
74 59
31 73
45 79
24 10
41 66
93 43
88 4
28 30
41 13
4 70
10 58

testCase1part3.txt

4 5
1 2 1
2 4 2
3 1 4
4 3 5
4 1 3

testCase2part1and2.txt

3
1 2
1 3
1 4

testCase2part3.txt

8 14
1 2 1
1 8 8
2 8 2
8 3 6
2 3 9
8 4 9
4 3 4
8 7 2
4 7 1
4 5 2
3 5 5
7 5 7
7 6 10
5 6 3

testCase3part1and2.txt

6
8 50
74 59
31 73
45 79
24 10
41 66

testCase4part1and2.txt

3
2 0
10 9
2 1