Problem 1¶

We will first complete an implemention of a union-find data structure with rank compression.

In [15]:

Copied!





class DisjointForests:
    def __init__(self, n):
        assert n >= 1, ' Empty disjoint forest is disallowed'
        self.n = n
        self.parents = [None]*n
        self.rank = [None]*n
        
    # Function: dictionary_of_sets
    # Convert the disjoint forest structure into a dictionary d
    # wherein d has an entry for each representative i
    # d[i] maps to each elements which belongs to the tree corresponding to i
    # in the disjoint forest.
    def dictionary_of_sets(self):
        d = {}
        for i in range(self.n):
            if self.is_representative(i):
                d[i] = set([i])
        for j in range(self.n):
            if self.parents[j] != None:
                root = self.find(j)
                assert root in d
                d[root].add(j)
        return d
    
    def make_set(self, j):
        assert 0 <= j < self.n
        assert self.parents[j] == None, 'You are calling make_set on an element multiple times -- not allowed.'
        self.parents[j] = j
        self.rank[j] = 1
        
    def is_representative(self, j):
        return self.parents[j] == j 
    
    def get_rank(self, j):
        return self.rank[j]
    
    # Function: find
    # Implement the find algorithm for a node j in the set.
    # Repeatedly traverse the parent pointer until we reach a root.
    # Implement the "rank compression" strategy by making all 
    # nodes along path from j to the root point directly to the root.
    def find(self, j):
        assert 0 <= j < self.n
        assert self.parents[j] != None, 'You are calling find on an element that is not part of the family yet. Please call make_set first.'
        # your code here
        if(self.is_representative(j)):
            return j
        else:
            return self.find(self.parents[j])
        
    
    # Function : union
    # Compute union of j1 and j2
    # First do a find to get to the representatives of j1 and j2.
    # If they are not the same, then 
    #  implement union using the rank strategy I.e, lower rank root becomes
    #  child of the higher ranked root.
    #  break ties by making the first argument j1's root the parent.
    def union(self, j1, j2):
        assert 0 <= j1 < self.n
        assert 0 <= j2 < self.n
        assert self.parents[j1] != None
        assert self.parents[j2] != None
        # your code here
        j1_parent = self.find(j1)
        j2_parent = self.find(j2)
        if(self.rank[j1_parent] >= self.rank[j2_parent]):
            self.parents[j2_parent] = j1_parent
            self.rank[j1_parent] = max(self.rank[j2_parent] + 1, self.rank[j1_parent])
        else:
            self.parents[j1_parent] = j2_parent
            self.rank[j2_parent] = max(self.rank[j1_parent] + 1, self.rank[j2_parent])
class DisjointForests:
    def __init__(self, n):
        assert n >= 1, ' Empty disjoint forest is disallowed'
        self.n = n
        self.parents = [None]*n
        self.rank = [None]*n
        
    # Function: dictionary_of_sets
    # Convert the disjoint forest structure into a dictionary d
    # wherein d has an entry for each representative i
    # d[i] maps to each elements which belongs to the tree corresponding to i
    # in the disjoint forest.
    def dictionary_of_sets(self):
        d = {}
        for i in range(self.n):
            if self.is_representative(i):
                d[i] = set([i])
        for j in range(self.n):
            if self.parents[j] != None:
                root = self.find(j)
                assert root in d
                d[root].add(j)
        return d
    
    def make_set(self, j):
        assert 0 <= j < self.n
        assert self.parents[j] == None, 'You are calling make_set on an element multiple times -- not allowed.'
        self.parents[j] = j
        self.rank[j] = 1
        
    def is_representative(self, j):
        return self.parents[j] == j 
    
    def get_rank(self, j):
        return self.rank[j]
    
    # Function: find
    # Implement the find algorithm for a node j in the set.
    # Repeatedly traverse the parent pointer until we reach a root.
    # Implement the "rank compression" strategy by making all 
    # nodes along path from j to the root point directly to the root.
    def find(self, j):
        assert 0 <= j < self.n
        assert self.parents[j] != None, 'You are calling find on an element that is not part of the family yet. Please call make_set first.'
        # your code here
        if(self.is_representative(j)):
            return j
        else:
            return self.find(self.parents[j])
        
    
    # Function : union
    # Compute union of j1 and j2
    # First do a find to get to the representatives of j1 and j2.
    # If they are not the same, then 
    #  implement union using the rank strategy I.e, lower rank root becomes
    #  child of the higher ranked root.
    #  break ties by making the first argument j1's root the parent.
    def union(self, j1, j2):
        assert 0 <= j1 < self.n
        assert 0 <= j2 < self.n
        assert self.parents[j1] != None
        assert self.parents[j2] != None
        # your code here
        j1_parent = self.find(j1)
        j2_parent = self.find(j2)
        if(self.rank[j1_parent] >= self.rank[j2_parent]):
            self.parents[j2_parent] = j1_parent
            self.rank[j1_parent] = max(self.rank[j2_parent] + 1, self.rank[j1_parent])
        else:
            self.parents[j1_parent] = j2_parent
            self.rank[j2_parent] = max(self.rank[j1_parent] + 1, self.rank[j2_parent])
        
        

In [16]:

Copied!





d = DisjointForests(10)
for i in range(10):
    d.make_set(i)

for i in range(10):
    assert d.find(i) == i, f'Failed: Find on {i} must return {i} back'
    
d.union(0,1)
d.union(2,3)
assert(d.find(0) == d.find(1)), '0 and 1 have been union-ed together'
assert(d.find(2) == d.find(3)), '2 and 3 have been union-ed together'
assert(d.find(0) != d.find(3)), '0 and 3 should be in  different trees'
assert((d.get_rank(0) == 2 and d.get_rank(1) == 1) or 
       (d.get_rank(1) == 2 and d.get_rank(0) == 1)), 'one of the nodes 0 or 1 must have rank 2'

assert((d.get_rank(2) == 2 and d.get_rank(3) == 1) or 
       (d.get_rank(3) == 2 and d.get_rank(2) == 1)), 'one of the nodes 2 or 3 must have rank 2'


d.union(3,4)
assert(d.find(2) == d.find(4)), '2 and 4 must be in the same set in the family.'

d.union(5,7)
d.union(6,8)
d.union(3,7)
d.union(0,6)

assert(d.find(6) == d.find(1)), '1 and 6 must be in the same set in the family'
assert(d.find(7) == d.find(4)), '7 and 4 must be in the same set in the family'
print('All tests passed: 10 points.')
d = DisjointForests(10)
for i in range(10):
    d.make_set(i)

for i in range(10):
    assert d.find(i) == i, f'Failed: Find on {i} must return {i} back'
    
d.union(0,1)
d.union(2,3)
assert(d.find(0) == d.find(1)), '0 and 1 have been union-ed together'
assert(d.find(2) == d.find(3)), '2 and 3 have been union-ed together'
assert(d.find(0) != d.find(3)), '0 and 3 should be in  different trees'
assert((d.get_rank(0) == 2 and d.get_rank(1) == 1) or 
       (d.get_rank(1) == 2 and d.get_rank(0) == 1)), 'one of the nodes 0 or 1 must have rank 2'

assert((d.get_rank(2) == 2 and d.get_rank(3) == 1) or 
       (d.get_rank(3) == 2 and d.get_rank(2) == 1)), 'one of the nodes 2 or 3 must have rank 2'


d.union(3,4)
assert(d.find(2) == d.find(4)), '2 and 4 must be in the same set in the family.'

d.union(5,7)
d.union(6,8)
d.union(3,7)
d.union(0,6)

assert(d.find(6) == d.find(1)), '1 and 6 must be in the same set in the family'
assert(d.find(7) == d.find(4)), '7 and 4 must be in the same set in the family'
print('All tests passed: 10 points.')

All tests passed: 10 points.

Problem 2¶

We will now explore finding maximal strongly connected components of an undirected graph using union find data structures. The undirected graph just consists of a list of edges with weights.

We will associate a non-negative weight $w_{i,j}$ for each undirected edge $(i,j)$.
We associate some extra data with vertices that will come in handy later.

Please examine the code for undirected graph data structures carefully.

In [17]:

Copied!





class UndirectedGraph:
    
    # n is the number of vertices
    # we will label the vertices from 0 to self.n -1 
    # We simply store the edges in a list.
    def __init__(self, n):
        assert n >= 1, 'You are creating an empty graph -- disallowed'
        self.n = n
        self.edges = []
        self.vertex_data = [None]*self.n
       
        
    def set_vertex_data(self, j, dat):
        assert 0 <= j < self.n
        self.vertex_data[j] = dat
        
    def get_vertex_data(self, j):
        assert 0 <= j < self.n
        return self.vertex_data[j] 
        
    def add_edge(self, i, j, wij):
        assert 0 <= i < self.n
        assert 0 <= j < self.n
        assert i != j
        # Make sure to add edge from i to j with weight wij
        self.edges.append((i, j, wij))
        
    def sort_edges(self):
        # sort edges in ascending order of weights.
        self.edges = sorted(self.edges, key=lambda edg_data: edg_data[2])
    
class UndirectedGraph:
    
    # n is the number of vertices
    # we will label the vertices from 0 to self.n -1 
    # We simply store the edges in a list.
    def __init__(self, n):
        assert n >= 1, 'You are creating an empty graph -- disallowed'
        self.n = n
        self.edges = []
        self.vertex_data = [None]*self.n
       
        
    def set_vertex_data(self, j, dat):
        assert 0 <= j < self.n
        self.vertex_data[j] = dat
        
    def get_vertex_data(self, j):
        assert 0 <= j < self.n
        return self.vertex_data[j] 
        
    def add_edge(self, i, j, wij):
        assert 0 <= i < self.n
        assert 0 <= j < self.n
        assert i != j
        # Make sure to add edge from i to j with weight wij
        self.edges.append((i, j, wij))
        
    def sort_edges(self):
        # sort edges in ascending order of weights.
        self.edges = sorted(self.edges, key=lambda edg_data: edg_data[2])
        

2A: Use union-find data-structures to compute strongly connected components.¶

We have previously seen how to use DFS to find maximal strongly connected components with a small twist.

We will consider only those edges $(i,j)$ whose weights are less than or equal to a threshold $W$ provided by the user.
Edges with weights above this threshold are not considered.

Design an algorithm to compute all the maximal strongly connected components for all eeges with threshold $W$ using the union-find data structure. What is the running time of your algorithm. Note that this is manually graded answer : you can compare your solution against our solution provided at the end of this assignment.

YOUR ANSWER HERE

Find the smallest weight edge from the graph
- If either one of the vertexs is not visited, and weight smaller than threshold $W$
  - Union them
- remove the edge

Complete the missing parts of the function in the code below to compute strongly connected components.

In [43]:

Copied!





def compute_scc(g, W):
    # create a disjoint forest with as many elements as number of vertices
    # Next compute the strongly connected components using the disjoint forest data structure
    d = DisjointForests(g.n)
    # your code here
    for i in range(g.n):
        d.make_set(i)
    g.sort_edges()
    seen = set()
    for edge in g.edges:
        print(edge)
        if ((edge[0] not in seen) or (edge[1] not in seen)) and (edge[2] <= W):
            seen.add(edge[0])
            seen.add(edge[1])
            d.union(edge[0],edge[1]) 
            
    # extract a set of sets from d
    return d.dictionary_of_sets()
def compute_scc(g, W):
    # create a disjoint forest with as many elements as number of vertices
    # Next compute the strongly connected components using the disjoint forest data structure
    d = DisjointForests(g.n)
    # your code here
    for i in range(g.n):
        d.make_set(i)
    g.sort_edges()
    seen = set()
    for edge in g.edges:
        print(edge)
        if ((edge[0] not in seen) or (edge[1] not in seen)) and (edge[2] <= W):
            seen.add(edge[0])
            seen.add(edge[1])
            d.union(edge[0],edge[1]) 
            
    # extract a set of sets from d
    return d.dictionary_of_sets()    

In [44]:

Copied!





g3 = UndirectedGraph(8)
g3.add_edge(0,1,0.5)
g3.add_edge(0,2,1.0)
g3.add_edge(0,4,0.5)
g3.add_edge(2,3,1.5)
g3.add_edge(2,4,2.0)
g3.add_edge(3,4,1.5)
g3.add_edge(5,6,2.0)
g3.add_edge(5,7,2.0)
res = compute_scc(g3, 2.0)
print('SCCs with threshold 2.0 computed by your code are:')
assert len(res) == 2, f'Expected 2 SCCs but got {len(res)}'
for (k, s) in res.items():
    print(s)
    
# Let us check that your code returns what we expect.
for (k, s) in res.items():
    if (k in [0,1,2,3,4]):
        assert (s == set([0,1,2,3,4])), '{0,1,2,3,4} should be an SCC'
    if (k in [5,6,7]):
        assert (s == set([5,6,7])), '{5,6,7} should be an SCC'

        
# Let us check that the thresholding works
print('SCCs with threshold 1.5')
res2 = compute_scc(g3, 1.5) # This cutsoff edges 2,4 and 5, 6, 7
for (k, s) in res2.items():
    print(s)
assert len(res2) == 4, f'Expected 4 SCCs but got {len(res2)}'

for (k, s) in res2.items():
    if k in [0,1,2,3,4]:
        assert (s == set([0,1,2,3,4])), '{0,1,2,3,4} should be an SCC'
    if k in [5]:
        assert s == set([5]), '{5} should be an SCC with just a single node.'
    if k in [6]:
        assert s == set([6]), '{6} should be an SCC with just a single node.'
    if k in [7]:
        assert s == set([7]), '{7} should be an SCC with just a single node.'
        
print('All tests passed: 10 points')
g3 = UndirectedGraph(8)
g3.add_edge(0,1,0.5)
g3.add_edge(0,2,1.0)
g3.add_edge(0,4,0.5)
g3.add_edge(2,3,1.5)
g3.add_edge(2,4,2.0)
g3.add_edge(3,4,1.5)
g3.add_edge(5,6,2.0)
g3.add_edge(5,7,2.0)
res = compute_scc(g3, 2.0)
print('SCCs with threshold 2.0 computed by your code are:')
assert len(res) == 2, f'Expected 2 SCCs but got {len(res)}'
for (k, s) in res.items():
    print(s)
    
# Let us check that your code returns what we expect.
for (k, s) in res.items():
    if (k in [0,1,2,3,4]):
        assert (s == set([0,1,2,3,4])), '{0,1,2,3,4} should be an SCC'
    if (k in [5,6,7]):
        assert (s == set([5,6,7])), '{5,6,7} should be an SCC'

        
# Let us check that the thresholding works
print('SCCs with threshold 1.5')
res2 = compute_scc(g3, 1.5) # This cutsoff edges 2,4 and 5, 6, 7
for (k, s) in res2.items():
    print(s)
assert len(res2) == 4, f'Expected 4 SCCs but got {len(res2)}'

for (k, s) in res2.items():
    if k in [0,1,2,3,4]:
        assert (s == set([0,1,2,3,4])), '{0,1,2,3,4} should be an SCC'
    if k in [5]:
        assert s == set([5]), '{5} should be an SCC with just a single node.'
    if k in [6]:
        assert s == set([6]), '{6} should be an SCC with just a single node.'
    if k in [7]:
        assert s == set([7]), '{7} should be an SCC with just a single node.'
        
print('All tests passed: 10 points')

(0, 1, 0.5)
(0, 4, 0.5)
(0, 2, 1.0)
(2, 3, 1.5)
(3, 4, 1.5)
(2, 4, 2.0)
(5, 6, 2.0)
(5, 7, 2.0)
SCCs with threshold 2.0 computed by your code are:
{0, 1, 2, 3, 4}
{5, 6, 7}
SCCs with threshold 1.5
(0, 1, 0.5)
(0, 4, 0.5)
(0, 2, 1.0)
(2, 3, 1.5)
(3, 4, 1.5)
(2, 4, 2.0)
(5, 6, 2.0)
(5, 7, 2.0)
{0, 1, 2, 3, 4}
{5}
{6}
{7}
All tests passed: 10 points

2B Compute Minimum Spanning Tree¶

We will now compute the MST of a given undirected weighted graph using Kruskal's algorithm. Complete the code below that uses a disjoint set forest data structure for implementing Kruskal's algorithm.

You code simply returns a list of edges with edge weights as a tuple $(i,j, wij)$ that are part of the MST along with the total weight of the MST.

In [50]:

Copied!





def compute_mst(g):
    # return a tuple of two items
    #   1. list of edges (i,j) that are part of the MST
    #   2. sum of MST edge weights.
    d = DisjointForests(g.n)
    mst_edges = []
    g.sort_edges()
    # your code here
    for i in range(g.n):
        d.make_set(i)
    mst_weight = 0
    d.dictionary_of_sets()
    for edge in g.edges:
        print(edge)
        if (d.find(edge[0]) != d.find(edge[1])) and (len(d.dictionary_of_sets())>1):
            mst_edges.append(edge)
            mst_weight += edge[2]
            d.union(edge[0],edge[1]) 
    return (mst_edges,mst_weight)
def compute_mst(g):
    # return a tuple of two items
    #   1. list of edges (i,j) that are part of the MST
    #   2. sum of MST edge weights.
    d = DisjointForests(g.n)
    mst_edges = []
    g.sort_edges()
    # your code here
    for i in range(g.n):
        d.make_set(i)
    mst_weight = 0
    d.dictionary_of_sets()
    for edge in g.edges:
        print(edge)
        if (d.find(edge[0]) != d.find(edge[1])) and (len(d.dictionary_of_sets())>1):
            mst_edges.append(edge)
            mst_weight += edge[2]
            d.union(edge[0],edge[1]) 
    return (mst_edges,mst_weight)
    
    

In [52]:

Copied!





g3 = UndirectedGraph(8)
g3.add_edge(0,1,0.5)
g3.add_edge(0,2,1.0)
g3.add_edge(0,4,0.5)
g3.add_edge(2,3,1.5)
g3.add_edge(2,4,2.0)
g3.add_edge(3,4,1.5)
g3.add_edge(5,6,2.0)
g3.add_edge(5,7,2.0)
g3.add_edge(3,5,2.0)

(mst_edges, mst_weight) = compute_mst(g3)
print('Your code computed MST: ')
for (i,j,wij) in mst_edges:
    print(f'\t {(i,j)} weight {wij}')
print(f'Total edge weight: {mst_weight}')

assert mst_weight == 9.5, 'Optimal MST weight is expected to be 9.5'

assert (0,1,0.5) in mst_edges
assert (0,2,1.0) in mst_edges
assert (0,4,0.5) in mst_edges
assert (5,6,2.0) in mst_edges
assert (5,7,2.0) in mst_edges
assert (3,5,2.0) in mst_edges
assert (2,3, 1.5) in mst_edges or (3,4, 1.5) in mst_edges

print('All tests passed: 10 points!')
g3 = UndirectedGraph(8)
g3.add_edge(0,1,0.5)
g3.add_edge(0,2,1.0)
g3.add_edge(0,4,0.5)
g3.add_edge(2,3,1.5)
g3.add_edge(2,4,2.0)
g3.add_edge(3,4,1.5)
g3.add_edge(5,6,2.0)
g3.add_edge(5,7,2.0)
g3.add_edge(3,5,2.0)

(mst_edges, mst_weight) = compute_mst(g3)
print('Your code computed MST: ')
for (i,j,wij) in mst_edges:
    print(f'\t {(i,j)} weight {wij}')
print(f'Total edge weight: {mst_weight}')

assert mst_weight == 9.5, 'Optimal MST weight is expected to be 9.5'

assert (0,1,0.5) in mst_edges
assert (0,2,1.0) in mst_edges
assert (0,4,0.5) in mst_edges
assert (5,6,2.0) in mst_edges
assert (5,7,2.0) in mst_edges
assert (3,5,2.0) in mst_edges
assert (2,3, 1.5) in mst_edges or (3,4, 1.5) in mst_edges

print('All tests passed: 10 points!')

(0, 1, 0.5)
(0, 4, 0.5)
(0, 2, 1.0)
(2, 3, 1.5)
(3, 4, 1.5)
(2, 4, 2.0)
(5, 6, 2.0)
(5, 7, 2.0)
(3, 5, 2.0)
Your code computed MST: 
	 (0, 1) weight 0.5
	 (0, 4) weight 0.5
	 (0, 2) weight 1.0
	 (2, 3) weight 1.5
	 (5, 6) weight 2.0
	 (5, 7) weight 2.0
	 (3, 5) weight 2.0
Total edge weight: 9.5
All tests passed: 10 points!

2C: Edge Threshold to Disconnect a Graph¶

Let $G$ be a weighted undirected graph that is strongly connected (i.e, the entire graph itself is an SCC). Our goal is to find a largest weight $W$ such that removing all edges of weight $\geq W$ will disconnect the graph.

Prove that the threshold $W$ is equal to the largest weight edge in the MST found by Kruskal's algorithm by proving that:

Removing all edges of weight $\geq W$ will result in a disconnected graph.
Keeping just edges of weight $\leq W$ (or removing edges of weight $> W$) will result in a connected graph.

Use the fact that a graph is strongly connected if and only if it has a minimum spanning tree.

YOUR ANSWER HERE

If $W >= $ the largest weight edge in the MST, we can always have a MST to connect all vertexs
If $W <= $ the largest weight edge in the MST, If we stil have a SCC, it's total weights must less than MST, which break the assmption of MST, therefore, it will result in a disconnected graph

Topological Data Analysis on Images (Not part of the Assignment -- just in case you are curious).¶

We illustrate an interesting connection between the graph algorithms for strongly connected components and minimum spanning trees to analyze images. Specifically, we will identify components in images as follows.

a) First, we treat an image stored as a .png or .jpg file as a matrix of pixels where pixels have color and intensity.

b) Given an image, we build a graph whose vertices are pixes and edges connect neighboring pixels.

c) The edge weight of an edge in the graph connecting neighboring pixels measures the intensity difference between the pixels (other measures of local pixel differences could also be used).

We can perform the following analysis (this is just an example of this kind of analysis which belongs to a larger family of methods called topological data analysis).

(a) Build a minimum spanning tree and compute the maximum weight edge in the MST. Let us call it W.

(b) Consider the maximal strongly connected components of the image for various thresholds such as $0.5W$, $0.75W$ or $0.9W$. Visualizing the pixels in various strongly connected components will allow us to study the "segments" that make up the images.

Here is some useful code using opencv to load images. Please take a close look.

In [53]:

Copied!





%matplotlib inline
from matplotlib import pyplot as plt
import cv2
# You can read png, jpg and other file types 
img = cv2.imread('test-pic.png') # read an image from a file using opencv (cv2) library
# you can annotate images 
plt.imshow(img) # show the image on the screen 
# You can find out the size of the image
print('Image size (height, width, num layers) is', img.shape)

px = img[145, 67] # img[y,x] is the color of the pixel of x,y
print(f'Pixel at (145,67) is {px}')
print(' pixels are RGB values.')
%matplotlib inline
from matplotlib import pyplot as plt
import cv2
# You can read png, jpg and other file types 
img = cv2.imread('test-pic.png') # read an image from a file using opencv (cv2) library
# you can annotate images 
plt.imshow(img) # show the image on the screen 
# You can find out the size of the image
print('Image size (height, width, num layers) is', img.shape)

px = img[145, 67] # img[y,x] is the color of the pixel of x,y
print(f'Pixel at (145,67) is {px}')
print(' pixels are RGB values.')

Image size (height, width, num layers) is (219, 320, 3)
Pixel at (145,67) is [250  41   2]
 pixels are RGB values.

No description has been provided for this image

In [54]:

Copied!





# load an image and make it into a graph.
import math
import cv2
def pixel_difference(px1, px2):
    def fix_pixels (px):
        return [int(px[0]), int(px[1]), int(px[2]) ]
    px1_float = fix_pixels(px1)
    px2_float = fix_pixels(px2)
    return max( abs(px1_float[0] - px2_float[0]), abs(px1_float[1] - px2_float[1]), abs(px1_float[2] - px2_float[2])) 

def get_index_from_pixel(i, j, height, width):
    assert 0 <= i < width
    assert 0 <= j < height
    return j * width + i

def get_coordinates_from_index(s, height, width):
    assert 0 <= s < height * width
    j = s//width
    i = s % width
    return (i,j)

def connect_neighboring_pixels(i, j, i1, j1, img, g):
    (height, width, _) = img.shape
    s = get_index_from_pixel(i, j, height, width)
    px = img[j,i]
    s1 = get_index_from_pixel(i1, j1, height, width)
    px1 = img[j1,i1]
    w = pixel_difference(px1, px)
    g.add_edge(s, s1, w)
    

def load_image_and_make_graph(imfilename):
    img = cv2.imread(imfilename)
    (height, width, num_layers) = img.shape
    g = UndirectedGraph(height * width)
    for j in range(height):
        for i in range(width):
            s = get_index_from_pixel(i, j, height, width)
            g.set_vertex_data(s, (i,j))
            if i > 0:
                connect_neighboring_pixels(i, j, i-1, j, img, g)
            if i < width -1:
                connect_neighboring_pixels(i, j, i+1, j, img, g)
            if j > 0:
                connect_neighboring_pixels(i, j, i, j-1, img, g)
            if j < height -1:
                connect_neighboring_pixels(i, j, i, j+1, img, g)
    return g
# load an image and make it into a graph.
import math
import cv2
def pixel_difference(px1, px2):
    def fix_pixels (px):
        return [int(px[0]), int(px[1]), int(px[2]) ]
    px1_float = fix_pixels(px1)
    px2_float = fix_pixels(px2)
    return max( abs(px1_float[0] - px2_float[0]), abs(px1_float[1] - px2_float[1]), abs(px1_float[2] - px2_float[2])) 

def get_index_from_pixel(i, j, height, width):
    assert 0 <= i < width
    assert 0 <= j < height
    return j * width + i

def get_coordinates_from_index(s, height, width):
    assert 0 <= s < height * width
    j = s//width
    i = s % width
    return (i,j)

def connect_neighboring_pixels(i, j, i1, j1, img, g):
    (height, width, _) = img.shape
    s = get_index_from_pixel(i, j, height, width)
    px = img[j,i]
    s1 = get_index_from_pixel(i1, j1, height, width)
    px1 = img[j1,i1]
    w = pixel_difference(px1, px)
    g.add_edge(s, s1, w)
    

def load_image_and_make_graph(imfilename):
    img = cv2.imread(imfilename)
    (height, width, num_layers) = img.shape
    g = UndirectedGraph(height * width)
    for j in range(height):
        for i in range(width):
            s = get_index_from_pixel(i, j, height, width)
            g.set_vertex_data(s, (i,j))
            if i > 0:
                connect_neighboring_pixels(i, j, i-1, j, img, g)
            if i < width -1:
                connect_neighboring_pixels(i, j, i+1, j, img, g)
            if j > 0:
                connect_neighboring_pixels(i, j, i, j-1, img, g)
            if j < height -1:
                connect_neighboring_pixels(i, j, i, j+1, img, g)
    return g
                
                
            

In [55]:

Copied!





print('Loading image and building graph.')
g = load_image_and_make_graph('test-pic.png')
print('Running MST algorithm')
(mst_edges, mst_weight) = compute_mst(g)
print(f'Found MST witn {len(mst_edges)} edges and total weight = {mst_weight}')
max_mst_edge_weight= max(mst_edges, key=lambda e: e[2])
print(f'Largest MST edge weight = {max_mst_edge_weight[2]}')
print('Loading image and building graph.')
g = load_image_and_make_graph('test-pic.png')
print('Running MST algorithm')
(mst_edges, mst_weight) = compute_mst(g)
print(f'Found MST witn {len(mst_edges)} edges and total weight = {mst_weight}')
max_mst_edge_weight= max(mst_edges, key=lambda e: e[2])
print(f'Largest MST edge weight = {max_mst_edge_weight[2]}')

Loading image and building graph.
Running MST algorithm
(0, 1, 0)
(0, 320, 0)
(1, 0, 0)
(1, 2, 0)
(1, 321, 0)
(2, 1, 0)
(2, 3, 0)
(2, 322, 0)
(3, 2, 0)
(3, 4, 0)
(3, 323, 0)
(4, 3, 0)
(4, 5, 0)
(4, 324, 0)
(5, 4, 0)
(5, 6, 0)
(5, 325, 0)
(6, 5, 0)
(6, 7, 0)
(6, 326, 0)
(7, 6, 0)
(7, 8, 0)
(7, 327, 0)
(8, 7, 0)
(8, 9, 0)
(8, 328, 0)
(9, 8, 0)
(9, 10, 0)
(9, 329, 0)
(10, 9, 0)
(10, 11, 0)
(10, 330, 0)
(11, 10, 0)
(11, 12, 0)
(11, 331, 0)
(12, 11, 0)
(12, 13, 0)
(12, 332, 0)
(13, 12, 0)
(13, 14, 0)
(13, 333, 0)
(14, 13, 0)
(14, 15, 0)
(14, 334, 0)
(15, 14, 0)
(15, 16, 0)
(15, 335, 0)
(16, 15, 0)
(16, 17, 0)
(16, 336, 0)
(17, 16, 0)
(17, 18, 0)
(17, 337, 0)
(18, 17, 0)
(18, 19, 0)
(18, 338, 0)
(19, 18, 0)
(19, 20, 0)
(19, 339, 0)
(20, 19, 0)
(20, 21, 0)
(20, 340, 0)
(21, 20, 0)
(21, 22, 0)
(21, 341, 0)
(22, 21, 0)
(22, 23, 0)
(22, 342, 0)
(23, 22, 0)
(23, 24, 0)
(23, 343, 0)
(24, 23, 0)
(24, 25, 0)
(24, 344, 0)
(25, 24, 0)
(25, 26, 0)
(25, 345, 0)
(26, 25, 0)
(26, 27, 0)
(26, 346, 0)
(27, 26, 0)
(27, 28, 0)
(27, 347, 0)
(28, 27, 0)
(28, 29, 0)
(28, 348, 0)
(29, 28, 0)
(29, 30, 0)
(29, 349, 0)
(30, 29, 0)
(30, 31, 0)
(30, 350, 0)
(31, 30, 0)
(31, 32, 0)
(31, 351, 0)
(32, 31, 0)
(32, 33, 0)
(32, 352, 0)
(33, 32, 0)
(33, 34, 0)
(33, 353, 0)
(34, 33, 0)
(34, 35, 0)
(34, 354, 0)
(35, 34, 0)
(35, 36, 0)
(35, 355, 0)
(36, 35, 0)
(36, 37, 0)
(36, 356, 0)
(37, 36, 0)
(37, 38, 0)
(37, 357, 0)
(38, 37, 0)
(38, 39, 0)
(38, 358, 0)
(39, 38, 0)
(39, 40, 0)
(39, 359, 0)
(40, 39, 0)
(40, 41, 0)
(40, 360, 0)
(41, 40, 0)
(41, 42, 0)
(41, 361, 0)
(42, 41, 0)
(42, 43, 0)
(42, 362, 0)
(43, 42, 0)
(43, 44, 0)
(43, 363, 0)
(44, 43, 0)
(44, 45, 0)
(44, 364, 0)
(45, 44, 0)
(45, 46, 0)
(45, 365, 0)
(46, 45, 0)
(46, 47, 0)
(46, 366, 0)
(47, 46, 0)
(47, 48, 0)
(47, 367, 0)
(48, 47, 0)
(48, 49, 0)
(48, 368, 0)
(49, 48, 0)
(49, 50, 0)
(49, 369, 0)
(50, 49, 0)
(50, 51, 0)
(50, 370, 0)
(51, 50, 0)
(51, 52, 0)
(51, 371, 0)
(52, 51, 0)
(52, 53, 0)
(52, 372, 0)
(53, 52, 0)
(53, 54, 0)
(53, 373, 0)
(54, 53, 0)
(54, 55, 0)
(54, 374, 0)
(55, 54, 0)
(55, 56, 0)
(55, 375, 0)
(56, 55, 0)
(56, 57, 0)
(56, 376, 0)
(57, 56, 0)
(57, 58, 0)
(57, 377, 0)
(58, 57, 0)
(58, 59, 0)
(58, 378, 0)
(59, 58, 0)
(59, 60, 0)
(59, 379, 0)
(60, 59, 0)
(60, 61, 0)
(60, 380, 0)
(61, 60, 0)
(61, 62, 0)
(61, 381, 0)
(62, 61, 0)
(62, 63, 0)
(62, 382, 0)
(63, 62, 0)
(63, 64, 0)
(63, 383, 0)
(64, 63, 0)
(64, 65, 0)
(64, 384, 0)
(65, 64, 0)
(65, 66, 0)
(65, 385, 0)
(66, 65, 0)
(66, 67, 0)
(66, 386, 0)
(67, 66, 0)
(67, 68, 0)
(67, 387, 0)
(68, 67, 0)
(68, 69, 0)
(68, 388, 0)
(69, 68, 0)
(69, 70, 0)
(69, 389, 0)
(70, 69, 0)
(70, 71, 0)
(70, 390, 0)
(71, 70, 0)
(71, 72, 0)
(71, 391, 0)
(72, 71, 0)
(72, 73, 0)
(72, 392, 0)
(73, 72, 0)
(73, 74, 0)
(73, 393, 0)
(74, 73, 0)
(74, 75, 0)
(74, 394, 0)
(75, 74, 0)
(75, 76, 0)
(75, 395, 0)
(76, 75, 0)
(76, 77, 0)
(76, 396, 0)
(77, 76, 0)
(77, 78, 0)
(77, 397, 0)
(78, 77, 0)
(78, 79, 0)
(78, 398, 0)
(79, 78, 0)
(79, 80, 0)
(79, 399, 0)
(80, 79, 0)
(80, 81, 0)
(80, 400, 0)
(81, 80, 0)
(81, 82, 0)
(81, 401, 0)
(82, 81, 0)
(82, 83, 0)
(82, 402, 0)
(83, 82, 0)
(83, 84, 0)
(83, 403, 0)
(84, 83, 0)
(84, 85, 0)
(84, 404, 0)
(85, 84, 0)
(85, 86, 0)
(85, 405, 0)
(86, 85, 0)
(86, 87, 0)
(86, 406, 0)
(87, 86, 0)
(87, 88, 0)
(87, 407, 0)
(88, 87, 0)
(88, 89, 0)
(88, 408, 0)
(89, 88, 0)
(89, 90, 0)
(89, 409, 0)
(90, 89, 0)
(90, 91, 0)
(90, 410, 0)
(91, 90, 0)
(91, 92, 0)
(91, 411, 0)
(92, 91, 0)
(92, 93, 0)
(92, 412, 0)
(93, 92, 0)
(93, 94, 0)
(93, 413, 0)
(94, 93, 0)
(94, 95, 0)
(94, 414, 0)
(95, 94, 0)
(95, 96, 0)
(95, 415, 0)
(96, 95, 0)
(96, 97, 0)
(96, 416, 0)
(97, 96, 0)
(97, 98, 0)
(97, 417, 0)
(98, 97, 0)
(98, 99, 0)
(98, 418, 0)
(99, 98, 0)
(99, 100, 0)
(99, 419, 0)
(100, 99, 0)
(100, 101, 0)
(100, 420, 0)
(101, 100, 0)
(101, 102, 0)
(101, 421, 0)
(102, 101, 0)
(102, 103, 0)
(102, 422, 0)
(103, 102, 0)
(103, 104, 0)
(103, 423, 0)
(104, 103, 0)
(104, 105, 0)
(104, 424, 0)
(105, 104, 0)
(105, 106, 0)
(105, 425, 0)
(106, 105, 0)
(106, 107, 0)
(106, 426, 0)
(107, 106, 0)
(107, 108, 0)
(107, 427, 0)
(108, 107, 0)
(108, 109, 0)
(108, 428, 0)
(109, 108, 0)
(109, 110, 0)
(109, 429, 0)
(110, 109, 0)
(110, 111, 0)
(110, 430, 0)
(111, 110, 0)
(111, 112, 0)
(111, 431, 0)
(112, 111, 0)
(112, 113, 0)
(112, 432, 0)
(113, 112, 0)
(113, 114, 0)
(113, 433, 0)
(114, 113, 0)
(114, 115, 0)
(114, 434, 0)
(115, 114, 0)
(115, 116, 0)
(115, 435, 0)
(116, 115, 0)
(116, 117, 0)
(116, 436, 0)
(117, 116, 0)
(117, 118, 0)
(117, 437, 0)
(118, 117, 0)
(118, 119, 0)
(118, 438, 0)
(119, 118, 0)
(119, 120, 0)
(119, 439, 0)
(120, 119, 0)
(120, 121, 0)
(120, 440, 0)
(121, 120, 0)
(121, 122, 0)
(121, 441, 0)
(122, 121, 0)
(122, 123, 0)
(122, 442, 0)
(123, 122, 0)
(123, 124, 0)
(123, 443, 0)
(124, 123, 0)
(124, 125, 0)
(124, 444, 0)
(125, 124, 0)
(125, 126, 0)
(125, 445, 0)
(126, 125, 0)
(126, 127, 0)
(126, 446, 0)
(127, 126, 0)
(127, 128, 0)
(127, 447, 0)
(128, 127, 0)
(128, 129, 0)
(128, 448, 0)
(129, 128, 0)
(129, 130, 0)
(129, 449, 0)
(130, 129, 0)
(130, 131, 0)
(130, 450, 0)
(131, 130, 0)
(131, 132, 0)
(131, 451, 0)
(132, 131, 0)
(132, 133, 0)
(132, 452, 0)
(133, 132, 0)
(133, 134, 0)
(133, 453, 0)
(134, 133, 0)
(134, 135, 0)
(134, 454, 0)
(135, 134, 0)
(135, 136, 0)
(135, 455, 0)
(136, 135, 0)
(136, 137, 0)
(136, 456, 0)
(137, 136, 0)
(137, 138, 0)
(137, 457, 0)
(138, 137, 0)
(138, 139, 0)
(138, 458, 0)
(139, 138, 0)
(139, 140, 0)
(139, 459, 0)
(140, 139, 0)
(140, 141, 0)
(140, 460, 0)
(141, 140, 0)
(141, 142, 0)
(141, 461, 0)
(142, 141, 0)
(142, 143, 0)
(142, 462, 0)
(143, 142, 0)
(143, 144, 0)
(143, 463, 0)
(144, 143, 0)
(144, 145, 0)
(144, 464, 0)
(145, 144, 0)
(145, 146, 0)
(145, 465, 0)
(146, 145, 0)
(146, 147, 0)
(146, 466, 0)
(147, 146, 0)
(147, 148, 0)
(147, 467, 0)
(148, 147, 0)
(148, 149, 0)
(148, 468, 0)
(149, 148, 0)
(149, 150, 0)
(149, 469, 0)
(150, 149, 0)
(150, 151, 0)
(150, 470, 0)
(151, 150, 0)
(151, 152, 0)
(151, 471, 0)
(152, 151, 0)
(152, 153, 0)
(152, 472, 0)
(153, 152, 0)
(153, 154, 0)
(153, 473, 0)
(154, 153, 0)
(154, 155, 0)
(154, 474, 0)
(155, 154, 0)
(155, 156, 0)
(155, 475, 0)
(156, 155, 0)
(156, 157, 0)
(156, 476, 0)
(157, 156, 0)
(157, 158, 0)
(157, 477, 0)
(158, 157, 0)
(158, 159, 0)
(158, 478, 0)
(159, 158, 0)
(159, 160, 0)
(159, 479, 0)
(160, 159, 0)
(160, 161, 0)
(160, 480, 0)
(161, 160, 0)
(161, 162, 0)
(161, 481, 0)
(162, 161, 0)
(162, 163, 0)
(162, 482, 0)
(163, 162, 0)
(163, 164, 0)
(163, 483, 0)
(164, 163, 0)
(164, 165, 0)
(164, 484, 0)
(165, 164, 0)
(165, 166, 0)
(165, 485, 0)
(166, 165, 0)
(166, 167, 0)
(166, 486, 0)
(167, 166, 0)
(167, 168, 0)
(167, 487, 0)
(168, 167, 0)
(168, 169, 0)
(168, 488, 0)
(169, 168, 0)
(169, 170, 0)
(169, 489, 0)
(170, 169, 0)
(170, 171, 0)
(170, 490, 0)
(171, 170, 0)
(171, 172, 0)
(171, 491, 0)
(172, 171, 0)
(172, 173, 0)
(172, 492, 0)
(173, 172, 0)
(173, 174, 0)
(173, 493, 0)
(174, 173, 0)
(174, 175, 0)
(174, 494, 0)
(175, 174, 0)
(175, 176, 0)
(175, 495, 0)
(176, 175, 0)
(176, 177, 0)
(176, 496, 0)
(177, 176, 0)
(177, 178, 0)
(177, 497, 0)
(178, 177, 0)
(178, 179, 0)
(178, 498, 0)
(179, 178, 0)
(179, 180, 0)
(179, 499, 0)
(180, 179, 0)
(180, 181, 0)
(180, 500, 0)
(181, 180, 0)
(181, 182, 0)
(181, 501, 0)
(182, 181, 0)
(182, 183, 0)
(182, 502, 0)
(183, 182, 0)
(183, 184, 0)
(183, 503, 0)
(184, 183, 0)
(184, 185, 0)
(184, 504, 0)
(185, 184, 0)
(185, 186, 0)
(185, 505, 0)
(186, 185, 0)
(186, 187, 0)
(186, 506, 0)
(187, 186, 0)
(187, 188, 0)
(187, 507, 0)
(188, 187, 0)
(188, 189, 0)
(188, 508, 0)
(189, 188, 0)
(189, 190, 0)
(189, 509, 0)
(190, 189, 0)
(190, 191, 0)
(190, 510, 0)
(191, 190, 0)
(191, 192, 0)
(191, 511, 0)
(192, 191, 0)
(192, 193, 0)
(192, 512, 0)
(193, 192, 0)
(193, 194, 0)
(193, 513, 0)
(194, 193, 0)
(194, 195, 0)
(194, 514, 0)
(195, 194, 0)
(195, 196, 0)
(195, 515, 0)
(196, 195, 0)
(196, 197, 0)
(196, 516, 0)
(197, 196, 0)
(197, 198, 0)
(197, 517, 0)
(198, 197, 0)
(198, 199, 0)
(198, 518, 0)
(199, 198, 0)
(199, 200, 0)
(199, 519, 0)
(200, 199, 0)
(200, 201, 0)
(200, 520, 0)
(201, 200, 0)
(201, 202, 0)
(201, 521, 0)
(202, 201, 0)
(202, 203, 0)
(202, 522, 0)
(203, 202, 0)
(203, 204, 0)
(203, 523, 0)
(204, 203, 0)
(204, 205, 0)
(204, 524, 0)
(205, 204, 0)
(205, 206, 0)
(205, 525, 0)
(206, 205, 0)
(206, 207, 0)
(206, 526, 0)
(207, 206, 0)
(207, 208, 0)
(207, 527, 0)
(208, 207, 0)
(208, 209, 0)
(208, 528, 0)
(209, 208, 0)
(209, 210, 0)
(209, 529, 0)
(210, 209, 0)
(210, 211, 0)
(210, 530, 0)
(211, 210, 0)
(211, 212, 0)
(211, 531, 0)
(212, 211, 0)
(212, 213, 0)
(212, 532, 0)
(213, 212, 0)
(213, 214, 0)
(213, 533, 0)
(214, 213, 0)
(214, 215, 0)
(214, 534, 0)
(215, 214, 0)
(215, 216, 0)
(215, 535, 0)
(216, 215, 0)
(216, 217, 0)
(216, 536, 0)
(217, 216, 0)
(217, 218, 0)
(217, 537, 0)
(218, 217, 0)
(218, 219, 0)
(218, 538, 0)
(219, 218, 0)
(219, 220, 0)
(219, 539, 0)
(220, 219, 0)
(220, 221, 0)
(220, 540, 0)
(221, 220, 0)
(221, 222, 0)
(221, 541, 0)
(222, 221, 0)
(222, 223, 0)
(222, 542, 0)
(223, 222, 0)
(223, 224, 0)
(223, 543, 0)
(224, 223, 0)
(224, 225, 0)
(224, 544, 0)
(225, 224, 0)
(225, 226, 0)
(225, 545, 0)
(226, 225, 0)
(226, 227, 0)
(226, 546, 0)
(227, 226, 0)
(227, 228, 0)
(227, 547, 0)
(228, 227, 0)
(228, 229, 0)
(228, 548, 0)
(229, 228, 0)
(229, 230, 0)
(229, 549, 0)
(230, 229, 0)
(230, 231, 0)
(230, 550, 0)
(231, 230, 0)
(231, 232, 0)
(231, 551, 0)
(232, 231, 0)
(232, 233, 0)
(232, 552, 0)
(233, 232, 0)
(233, 234, 0)
(233, 553, 0)
(234, 233, 0)
(234, 235, 0)
(234, 554, 0)
(235, 234, 0)
(235, 236, 0)
(235, 555, 0)
(236, 235, 0)
(236, 237, 0)
(236, 556, 0)
(237, 236, 0)
(237, 238, 0)
(237, 557, 0)
(238, 237, 0)
(238, 239, 0)
(238, 558, 0)
(239, 238, 0)
(239, 240, 0)
(239, 559, 0)
(240, 239, 0)
(240, 241, 0)
(240, 560, 0)
(241, 240, 0)
(241, 242, 0)
(241, 561, 0)
(242, 241, 0)
(242, 243, 0)
(242, 562, 0)
(243, 242, 0)
(243, 244, 0)
(243, 563, 0)
(244, 243, 0)
(244, 245, 0)
(244, 564, 0)
(245, 244, 0)
(245, 246, 0)
(245, 565, 0)
(246, 245, 0)
(246, 247, 0)
(246, 566, 0)
(247, 246, 0)
(247, 248, 0)
(247, 567, 0)
(248, 247, 0)
(248, 249, 0)
(248, 568, 0)
(249, 248, 0)
(249, 250, 0)
(249, 569, 0)
(250, 249, 0)
(250, 251, 0)
(250, 570, 0)
(251, 250, 0)
(251, 252, 0)
(251, 571, 0)
(252, 251, 0)
(252, 253, 0)
(252, 572, 0)
(253, 252, 0)
(253, 254, 0)
(253, 573, 0)
(254, 253, 0)
(254, 255, 0)
(254, 574, 0)
(255, 254, 0)
(255, 256, 0)
(255, 575, 0)
(256, 255, 0)
(256, 257, 0)
(256, 576, 0)
(257, 256, 0)
(257, 258, 0)
(257, 577, 0)
(258, 257, 0)
(258, 259, 0)
(258, 578, 0)
(259, 258, 0)
(259, 260, 0)
(259, 579, 0)
(260, 259, 0)
(260, 261, 0)
(260, 580, 0)
(261, 260, 0)
(261, 262, 0)
(261, 581, 0)
(262, 261, 0)
(262, 263, 0)
(262, 582, 0)
(263, 262, 0)
(263, 264, 0)
(263, 583, 0)
(264, 263, 0)
(264, 265, 0)
(264, 584, 0)
(265, 264, 0)
(265, 266, 0)
(265, 585, 0)
(266, 265, 0)
(266, 267, 0)
(266, 586, 0)
(267, 266, 0)
(267, 268, 0)
(267, 587, 0)
(268, 267, 0)
(268, 269, 0)
(268, 588, 0)
(269, 268, 0)
(269, 270, 0)
(269, 589, 0)
(270, 269, 0)
(270, 271, 0)
(270, 590, 0)
(271, 270, 0)
(271, 272, 0)
(271, 591, 0)
(272, 271, 0)
(272, 273, 0)
(272, 592, 0)
(273, 272, 0)
(273, 274, 0)
(273, 593, 0)
(274, 273, 0)
(274, 275, 0)
(274, 594, 0)
(275, 274, 0)
(275, 276, 0)
(275, 595, 0)
(276, 275, 0)
(276, 277, 0)
(276, 596, 0)
(277, 276, 0)
(277, 278, 0)
(277, 597, 0)
(278, 277, 0)
(278, 279, 0)
(278, 598, 0)
(279, 278, 0)
(279, 280, 0)
(279, 599, 0)
(280, 279, 0)
(280, 281, 0)
(280, 600, 0)
(281, 280, 0)
(281, 282, 0)
(281, 601, 0)
(282, 281, 0)
(282, 283, 0)
(282, 602, 0)
(283, 282, 0)
(283, 284, 0)
(283, 603, 0)
(284, 283, 0)
(284, 285, 0)
(284, 604, 0)
(285, 284, 0)
(285, 286, 0)
(285, 605, 0)
(286, 285, 0)
(286, 287, 0)
(286, 606, 0)
(287, 286, 0)
(287, 288, 0)
(287, 607, 0)
(288, 287, 0)
(288, 289, 0)
(288, 608, 0)
(289, 288, 0)
(289, 290, 0)
(289, 609, 0)
(290, 289, 0)
(290, 291, 0)
(290, 610, 0)
(291, 290, 0)
(291, 292, 0)
(291, 611, 0)
(292, 291, 0)
(292, 293, 0)
(292, 612, 0)
(293, 292, 0)
(293, 294, 0)
(293, 613, 0)
(294, 293, 0)
(294, 295, 0)
(294, 614, 0)
(295, 294, 0)
(295, 296, 0)
(295, 615, 0)
(296, 295, 0)
(296, 297, 0)
(296, 616, 0)
(297, 296, 0)
(297, 298, 0)
(297, 617, 0)
(298, 297, 0)
(298, 299, 0)
(298, 618, 0)
(299, 298, 0)
(299, 300, 0)
(299, 619, 0)
(300, 299, 0)
(300, 301, 0)
(300, 620, 0)
(301, 300, 0)
(301, 302, 0)
(301, 621, 0)
(302, 301, 0)
(302, 303, 0)
(302, 622, 0)
(303, 302, 0)
(303, 304, 0)
(303, 623, 0)
(304, 303, 0)
(304, 305, 0)
(304, 624, 0)
(305, 304, 0)
(305, 306, 0)
(305, 625, 0)
(306, 305, 0)
(306, 307, 0)
(306, 626, 0)
(307, 306, 0)
(307, 308, 0)
(307, 627, 0)
(308, 307, 0)
(308, 309, 0)
(308, 628, 0)
(309, 308, 0)
(309, 310, 0)
(309, 629, 0)
(310, 309, 0)
(310, 311, 0)
(310, 630, 0)
(311, 310, 0)
(311, 312, 0)
(311, 631, 0)
(312, 311, 0)
(312, 313, 0)
(312, 632, 0)
(313, 312, 0)
(313, 314, 0)
(313, 633, 0)
(314, 313, 0)
(314, 315, 0)
(314, 634, 0)
(315, 314, 0)
(315, 316, 0)
(315, 635, 0)
(316, 315, 0)
(316, 317, 0)
(316, 636, 0)
(317, 316, 0)
(317, 318, 0)
(317, 637, 0)
(318, 317, 0)
(318, 319, 0)
(318, 638, 0)
(319, 318, 0)
(319, 639, 0)
(320, 321, 0)
(320, 0, 0)
(320, 640, 0)
(321, 320, 0)
(321, 322, 0)
(321, 1, 0)
(321, 641, 0)
(322, 321, 0)
(322, 323, 0)
(322, 2, 0)
(322, 642, 0)
(323, 322, 0)
(323, 324, 0)
(323, 3, 0)
(323, 643, 0)
(324, 323, 0)
(324, 325, 0)
(324, 4, 0)
(324, 644, 0)
(325, 324, 0)
(325, 326, 0)
(325, 5, 0)
(325, 645, 0)
(326, 325, 0)
(326, 327, 0)
(326, 6, 0)
(326, 646, 0)
(327, 326, 0)
(327, 328, 0)
(327, 7, 0)
(327, 647, 0)
(328, 327, 0)
(328, 329, 0)
(328, 8, 0)
(328, 648, 0)
(329, 328, 0)
(329, 330, 0)
(329, 9, 0)
(329, 649, 0)
(330, 329, 0)
(330, 331, 0)
(330, 10, 0)
(330, 650, 0)
(331, 330, 0)
(331, 332, 0)
(331, 11, 0)
(331, 651, 0)
(332, 331, 0)
(332, 333, 0)
(332, 12, 0)
(332, 652, 0)
(333, 332, 0)
(333, 334, 0)
(333, 13, 0)
(333, 653, 0)
(334, 333, 0)
(334, 335, 0)
(334, 14, 0)
(334, 654, 0)
(335, 334, 0)
(335, 336, 0)
(335, 15, 0)
(335, 655, 0)
(336, 335, 0)
(336, 337, 0)
(336, 16, 0)
(336, 656, 0)
(337, 336, 0)
(337, 338, 0)
(337, 17, 0)
(337, 657, 0)
(338, 337, 0)
(338, 339, 0)
(338, 18, 0)
(338, 658, 0)
(339, 338, 0)
(339, 340, 0)
(339, 19, 0)
(339, 659, 0)
(340, 339, 0)
(340, 341, 0)
(340, 20, 0)
(340, 660, 0)
(341, 340, 0)
(341, 342, 0)
(341, 21, 0)
(341, 661, 0)
(342, 341, 0)
(342, 343, 0)
(342, 22, 0)
(342, 662, 0)
(343, 342, 0)
(343, 344, 0)
(343, 23, 0)
(343, 663, 0)
(344, 343, 0)
(344, 345, 0)
(344, 24, 0)
(344, 664, 0)
(345, 344, 0)
(345, 346, 0)
(345, 25, 0)
(345, 665, 0)
(346, 345, 0)
(346, 347, 0)
(346, 26, 0)
(346, 666, 0)
(347, 346, 0)
(347, 348, 0)
(347, 27, 0)
(347, 667, 0)
(348, 347, 0)
(348, 349, 0)
(348, 28, 0)
(348, 668, 0)
(349, 348, 0)
(349, 350, 0)
(349, 29, 0)
(349, 669, 0)
(350, 349, 0)
(350, 351, 0)
(350, 30, 0)
(350, 670, 0)
(351, 350, 0)
(351, 352, 0)
(351, 31, 0)
(351, 671, 0)
(352, 351, 0)
(352, 353, 0)
(352, 32, 0)
(352, 672, 0)
(353, 352, 0)
(353, 354, 0)
(353, 33, 0)
(353, 673, 0)
(354, 353, 0)
(354, 355, 0)
(354, 34, 0)
(354, 674, 0)
(355, 354, 0)
(355, 356, 0)
(355, 35, 0)
(355, 675, 0)
(356, 355, 0)
(356, 357, 0)
(356, 36, 0)
(356, 676, 0)
(357, 356, 0)
(357, 358, 0)
(357, 37, 0)
(357, 677, 0)
(358, 357, 0)
(358, 359, 0)
(358, 38, 0)
(358, 678, 0)
(359, 358, 0)
(359, 360, 0)
(359, 39, 0)
(359, 679, 0)
(360, 359, 0)
(360, 361, 0)
(360, 40, 0)
(360, 680, 0)
(361, 360, 0)
(361, 362, 0)
(361, 41, 0)
(361, 681, 0)
(362, 361, 0)
(362, 363, 0)
(362, 42, 0)
(362, 682, 0)
(363, 362, 0)
(363, 364, 0)
(363, 43, 0)
(363, 683, 0)
(364, 363, 0)
(364, 365, 0)
(364, 44, 0)
(364, 684, 0)
(365, 364, 0)
(365, 366, 0)
(365, 45, 0)
(365, 685, 0)
(366, 365, 0)
(366, 367, 0)
(366, 46, 0)
(366, 686, 0)
(367, 366, 0)
(367, 368, 0)
(367, 47, 0)
(367, 687, 0)
(368, 367, 0)
(368, 369, 0)
(368, 48, 0)
(368, 688, 0)
(369, 368, 0)
(369, 370, 0)
(369, 49, 0)
(369, 689, 0)
(370, 369, 0)
(370, 371, 0)
(370, 50, 0)
(370, 690, 0)
(371, 370, 0)
(371, 372, 0)
(371, 51, 0)
(371, 691, 0)
(372, 371, 0)
(372, 373, 0)
(372, 52, 0)
(372, 692, 0)
(373, 372, 0)
(373, 374, 0)
(373, 53, 0)
(373, 693, 0)
(374, 373, 0)
(374, 375, 0)
(374, 54, 0)
(374, 694, 0)
(375, 374, 0)
(375, 376, 0)
(375, 55, 0)
(375, 695, 0)
(376, 375, 0)
(376, 377, 0)
(376, 56, 0)
(376, 696, 0)
(377, 376, 0)
(377, 378, 0)
(377, 57, 0)
(377, 697, 0)
(378, 377, 0)
(378, 379, 0)
(378, 58, 0)
(378, 698, 0)
(379, 378, 0)
(379, 380, 0)
(379, 59, 0)
(379, 699, 0)
(380, 379, 0)
(380, 381, 0)
(380, 60, 0)
(380, 700, 0)
(381, 380, 0)
(381, 382, 0)
(381, 61, 0)
(381, 701, 0)
(382, 381, 0)
(382, 383, 0)
(382, 62, 0)
(382, 702, 0)
(383, 382, 0)
(383, 384, 0)
(383, 63, 0)
(383, 703, 0)
(384, 383, 0)
(384, 385, 0)
(384, 64, 0)
(384, 704, 0)
(385, 384, 0)
(385, 386, 0)
(385, 65, 0)
(385, 705, 0)
(386, 385, 0)
(386, 387, 0)
(386, 66, 0)
(386, 706, 0)
(387, 386, 0)
(387, 388, 0)
(387, 67, 0)
(387, 707, 0)
(388, 387, 0)
(388, 389, 0)
(388, 68, 0)
(388, 708, 0)
(389, 388, 0)
(389, 390, 0)
(389, 69, 0)
(389, 709, 0)
(390, 389, 0)
(390, 391, 0)
(390, 70, 0)
(390, 710, 0)
(391, 390, 0)
(391, 392, 0)
(391, 71, 0)
(391, 711, 0)
(392, 391, 0)
(392, 393, 0)
(392, 72, 0)
(392, 712, 0)
(393, 392, 0)
(393, 394, 0)
(393, 73, 0)
(393, 713, 0)
(394, 393, 0)
(394, 395, 0)
(394, 74, 0)
(394, 714, 0)
(395, 394, 0)
(395, 396, 0)
(395, 75, 0)
(395, 715, 0)
(396, 395, 0)
(396, 397, 0)
(396, 76, 0)
(396, 716, 0)
(397, 396, 0)
(397, 398, 0)
(397, 77, 0)
(397, 717, 0)
(398, 397, 0)
(398, 399, 0)
(398, 78, 0)
(398, 718, 0)
(399, 398, 0)
(399, 400, 0)
(399, 79, 0)
(399, 719, 0)
(400, 399, 0)
(400, 401, 0)
(400, 80, 0)
(400, 720, 0)
(401, 400, 0)
(401, 402, 0)
(401, 81, 0)
(401, 721, 0)
(402, 401, 0)
(402, 403, 0)
(402, 82, 0)
(402, 722, 0)
(403, 402, 0)
(403, 404, 0)
(403, 83, 0)
(403, 723, 0)
(404, 403, 0)
(404, 405, 0)
(404, 84, 0)
(404, 724, 0)
(405, 404, 0)
(405, 406, 0)
(405, 85, 0)
(405, 725, 0)
(406, 405, 0)
(406, 407, 0)
(406, 86, 0)
(406, 726, 0)
(407, 406, 0)
(407, 408, 0)
(407, 87, 0)
(407, 727, 0)
(408, 407, 0)
(408, 409, 0)
(408, 88, 0)
(408, 728, 0)
(409, 408, 0)
(409, 410, 0)
(409, 89, 0)
(409, 729, 0)
(410, 409, 0)
(410, 411, 0)
(410, 90, 0)
(410, 730, 0)
(411, 410, 0)
(411, 412, 0)
(411, 91, 0)
(411, 731, 0)
(412, 411, 0)
(412, 413, 0)
(412, 92, 0)
(412, 732, 0)
(413, 412, 0)
(413, 414, 0)
(413, 93, 0)
(413, 733, 0)
(414, 413, 0)
(414, 415, 0)
(414, 94, 0)
(414, 734, 0)
(415, 414, 0)
(415, 416, 0)
(415, 95, 0)
(415, 735, 0)
(416, 415, 0)
(416, 417, 0)
(416, 96, 0)
(416, 736, 0)
(417, 416, 0)
(417, 418, 0)
(417, 97, 0)
(417, 737, 0)
(418, 417, 0)
(418, 419, 0)
(418, 98, 0)
(418, 738, 0)
(419, 418, 0)
(419, 420, 0)
(419, 99, 0)
(419, 739, 0)
(420, 419, 0)
(420, 421, 0)
(420, 100, 0)
(420, 740, 0)
(421, 420, 0)
(421, 422, 0)
(421, 101, 0)
(421, 741, 0)
(422, 421, 0)
(422, 423, 0)
(422, 102, 0)
(422, 742, 0)
(423, 422, 0)
(423, 424, 0)
(423, 103, 0)
(423, 743, 0)
(424, 423, 0)
(424, 425, 0)
(424, 104, 0)
(424, 744, 0)
(425, 424, 0)
(425, 426, 0)
(425, 105, 0)
(425, 745, 0)
(426, 425, 0)
(426, 427, 0)
(426, 106, 0)
(426, 746, 0)
(427, 426, 0)
(427, 428, 0)
(427, 107, 0)
(427, 747, 0)
(428, 427, 0)
(428, 429, 0)
(428, 108, 0)
(428, 748, 0)
(429, 428, 0)
(429, 430, 0)
(429, 109, 0)
(429, 749, 0)
(430, 429, 0)
(430, 431, 0)
(430, 110, 0)
(430, 750, 0)
(431, 430, 0)
(431, 432, 0)
(431, 111, 0)
(431, 751, 0)
(432, 431, 0)
(432, 433, 0)
(432, 112, 0)
(432, 752, 0)
(433, 432, 0)
(433, 434, 0)
(433, 113, 0)
(433, 753, 0)
(434, 433, 0)
(434, 435, 0)
(434, 114, 0)
(434, 754, 0)
(435, 434, 0)
(435, 436, 0)
(435, 115, 0)
(435, 755, 0)
(436, 435, 0)
(436, 437, 0)
(436, 116, 0)
(436, 756, 0)
(437, 436, 0)
(437, 438, 0)
(437, 117, 0)
(437, 757, 0)
(438, 437, 0)
(438, 439, 0)
(438, 118, 0)
(438, 758, 0)
(439, 438, 0)
(439, 440, 0)
(439, 119, 0)
(439, 759, 0)
(440, 439, 0)
(440, 441, 0)
(440, 120, 0)
(440, 760, 0)
(441, 440, 0)
(441, 442, 0)
(441, 121, 0)
(441, 761, 0)
(442, 441, 0)
(442, 443, 0)
(442, 122, 0)
(442, 762, 0)
(443, 442, 0)
(443, 444, 0)
(443, 123, 0)
(443, 763, 0)
(444, 443, 0)
(444, 445, 0)
(444, 124, 0)
(444, 764, 0)
(445, 444, 0)
(445, 446, 0)
(445, 125, 0)
(445, 765, 0)
(446, 445, 0)
(446, 447, 0)
(446, 126, 0)
(446, 766, 0)
(447, 446, 0)
(447, 448, 0)
(447, 127, 0)
(447, 767, 0)
(448, 447, 0)
(448, 449, 0)
(448, 128, 0)
(448, 768, 0)
(449, 448, 0)
(449, 450, 0)
(449, 129, 0)
(449, 769, 0)
(450, 449, 0)
(450, 451, 0)
(450, 130, 0)
(450, 770, 0)
(451, 450, 0)
(451, 452, 0)
(451, 131, 0)
(451, 771, 0)
(452, 451, 0)
(452, 453, 0)
(452, 132, 0)
(452, 772, 0)
(453, 452, 0)
(453, 454, 0)
(453, 133, 0)
(453, 773, 0)
(454, 453, 0)
(454, 455, 0)
(454, 134, 0)
(454, 774, 0)
(455, 454, 0)
(455, 456, 0)
(455, 135, 0)
(455, 775, 0)
(456, 455, 0)
(456, 457, 0)
(456, 136, 0)
(456, 776, 0)
(457, 456, 0)
(457, 458, 0)
(457, 137, 0)
(457, 777, 0)
(458, 457, 0)
(458, 459, 0)
(458, 138, 0)
(458, 778, 0)
(459, 458, 0)
(459, 460, 0)
(459, 139, 0)
(459, 779, 0)
(460, 459, 0)
(460, 461, 0)
(460, 140, 0)
(460, 780, 0)
(461, 460, 0)
(461, 462, 0)
(461, 141, 0)
(461, 781, 0)
(462, 461, 0)
(462, 463, 0)
(462, 142, 0)
(462, 782, 0)
(463, 462, 0)
(463, 464, 0)
(463, 143, 0)
(463, 783, 0)
(464, 463, 0)
(464, 465, 0)
(464, 144, 0)
(464, 784, 0)
(465, 464, 0)
(465, 466, 0)
(465, 145, 0)
(465, 785, 0)
(466, 465, 0)
(466, 467, 0)
(466, 146, 0)
(466, 786, 0)
(467, 466, 0)
(467, 468, 0)
(467, 147, 0)
(467, 787, 0)
(468, 467, 0)
(468, 469, 0)
(468, 148, 0)
(468, 788, 0)
(469, 468, 0)
(469, 470, 0)
(469, 149, 0)
(469, 789, 0)
(470, 469, 0)
(470, 471, 0)
(470, 150, 0)
(470, 790, 0)
(471, 470, 0)
(471, 472, 0)
(471, 151, 0)
(471, 791, 0)
(472, 471, 0)
(472, 473, 0)
(472, 152, 0)
(472, 792, 0)
(473, 472, 0)
(473, 474, 0)
(473, 153, 0)
(473, 793, 0)
(474, 473, 0)
(474, 475, 0)
(474, 154, 0)
(474, 794, 0)
(475, 474, 0)
(475, 476, 0)
(475, 155, 0)
(475, 795, 0)
(476, 475, 0)
(476, 477, 0)
(476, 156, 0)
(476, 796, 0)
(477, 476, 0)
(477, 478, 0)
(477, 157, 0)
(477, 797, 0)
(478, 477, 0)
(478, 479, 0)
(478, 158, 0)
(478, 798, 0)
(479, 478, 0)
(479, 480, 0)
(479, 159, 0)
(479, 799, 0)
(480, 479, 0)
(480, 481, 0)
(480, 160, 0)
(480, 800, 0)
(481, 480, 0)
(481, 482, 0)
(481, 161, 0)
(481, 801, 0)
(482, 481, 0)
(482, 483, 0)
(482, 162, 0)
(482, 802, 0)
(483, 482, 0)
(483, 484, 0)
(483, 163, 0)
(483, 803, 0)
(484, 483, 0)
(484, 485, 0)
(484, 164, 0)
(484, 804, 0)
(485, 484, 0)
(485, 486, 0)
(485, 165, 0)
(485, 805, 0)
(486, 485, 0)
(486, 487, 0)
(486, 166, 0)
(486, 806, 0)
(487, 486, 0)
(487, 488, 0)
(487, 167, 0)
(487, 807, 0)
(488, 487, 0)
(488, 489, 0)
(488, 168, 0)
(488, 808, 0)
(489, 488, 0)
(489, 490, 0)
(489, 169, 0)
(489, 809, 0)
(490, 489, 0)
(490, 491, 0)
(490, 170, 0)
(490, 810, 0)
(491, 490, 0)
(491, 492, 0)
(491, 171, 0)
(491, 811, 0)
(492, 491, 0)
(492, 493, 0)
(492, 172, 0)
(492, 812, 0)
(493, 492, 0)
(493, 494, 0)
(493, 173, 0)
(493, 813, 0)
(494, 493, 0)
(494, 495, 0)
(494, 174, 0)
(494, 814, 0)
(495, 494, 0)
(495, 496, 0)
(495, 175, 0)
(495, 815, 0)
(496, 495, 0)
(496, 497, 0)
(496, 176, 0)
(496, 816, 0)
(497, 496, 0)
(497, 498, 0)
(497, 177, 0)
(497, 817, 0)
(498, 497, 0)
(498, 499, 0)
(498, 178, 0)
(498, 818, 0)
(499, 498, 0)
(499, 500, 0)
(499, 179, 0)
(499, 819, 0)
(500, 499, 0)
(500, 501, 0)
(500, 180, 0)
(500, 820, 0)
(501, 500, 0)
(501, 502, 0)
(501, 181, 0)
(501, 821, 0)
(502, 501, 0)
(502, 503, 0)
(502, 182, 0)
(502, 822, 0)
(503, 502, 0)
(503, 504, 0)
(503, 183, 0)
(503, 823, 0)
(504, 503, 0)
(504, 505, 0)
(504, 184, 0)
(504, 824, 0)
(505, 504, 0)
(505, 506, 0)
(505, 185, 0)
(505, 825, 0)
(506, 505, 0)
(506, 507, 0)
(506, 186, 0)
(506, 826, 0)
(507, 506, 0)
(507, 508, 0)
(507, 187, 0)
(507, 827, 0)
(508, 507, 0)
(508, 509, 0)
(508, 188, 0)
(508, 828, 0)
(509, 508, 0)
(509, 510, 0)
(509, 189, 0)
(509, 829, 0)
(510, 509, 0)
(510, 511, 0)
(510, 190, 0)
(510, 830, 0)
(511, 510, 0)
(511, 512, 0)
(511, 191, 0)
(511, 831, 0)
(512, 511, 0)
(512, 513, 0)
(512, 192, 0)
(512, 832, 0)
(513, 512, 0)
(513, 514, 0)
(513, 193, 0)
(513, 833, 0)
(514, 513, 0)
(514, 515, 0)
(514, 194, 0)
(514, 834, 0)
(515, 514, 0)
(515, 516, 0)
(515, 195, 0)
(515, 835, 0)
(516, 515, 0)
(516, 517, 0)
(516, 196, 0)
(516, 836, 0)
(517, 516, 0)
(517, 518, 0)
(517, 197, 0)
(517, 837, 0)
(518, 517, 0)
(518, 519, 0)
(518, 198, 0)
(518, 838, 0)
(519, 518, 0)
(519, 520, 0)
(519, 199, 0)
(519, 839, 0)
(520, 519, 0)
(520, 521, 0)
(520, 200, 0)
(520, 840, 0)
(521, 520, 0)
(521, 522, 0)
(521, 201, 0)
(521, 841, 0)
(522, 521, 0)
(522, 523, 0)
(522, 202, 0)
(522, 842, 0)
(523, 522, 0)
(523, 524, 0)
(523, 203, 0)
(523, 843, 0)
(524, 523, 0)
(524, 525, 0)
(524, 204, 0)
(524, 844, 0)
(525, 524, 0)
(525, 526, 0)
(525, 205, 0)
(525, 845, 0)
(526, 525, 0)
(526, 527, 0)
(526, 206, 0)
(526, 846, 0)
(527, 526, 0)
(527, 528, 0)
(527, 207, 0)
(527, 847, 0)
(528, 527, 0)
(528, 529, 0)
(528, 208, 0)
(528, 848, 0)
(529, 528, 0)
(529, 530, 0)
(529, 209, 0)
(529, 849, 0)
(530, 529, 0)
(530, 531, 0)
(530, 210, 0)
(530, 850, 0)
(531, 530, 0)
(531, 532, 0)
(531, 211, 0)
(531, 851, 0)
(532, 531, 0)
(532, 533, 0)
(532, 212, 0)
(532, 852, 0)
(533, 532, 0)
(533, 534, 0)
(533, 213, 0)
(533, 853, 0)
(534, 533, 0)
(534, 535, 0)
(534, 214, 0)
(534, 854, 0)
(535, 534, 0)
(535, 536, 0)
(535, 215, 0)
(535, 855, 0)
(536, 535, 0)
(536, 537, 0)
(536, 216, 0)
(536, 856, 0)
(537, 536, 0)
(537, 538, 0)
(537, 217, 0)
(537, 857, 0)
(538, 537, 0)
(538, 539, 0)
(538, 218, 0)
(538, 858, 0)
(539, 538, 0)
(539, 540, 0)
(539, 219, 0)
(539, 859, 0)
(540, 539, 0)
(540, 541, 0)
(540, 220, 0)
(540, 860, 0)
(541, 540, 0)
(541, 542, 0)
(541, 221, 0)
(541, 861, 0)
(542, 541, 0)
(542, 543, 0)
(542, 222, 0)
(542, 862, 0)
(543, 542, 0)
(543, 544, 0)
(543, 223, 0)
(543, 863, 0)
(544, 543, 0)
(544, 545, 0)
(544, 224, 0)
(544, 864, 0)
(545, 544, 0)
(545, 546, 0)
(545, 225, 0)
(545, 865, 0)
(546, 545, 0)
(546, 547, 0)
(546, 226, 0)
(546, 866, 0)
(547, 546, 0)
(547, 548, 0)
(547, 227, 0)
(547, 867, 0)
(548, 547, 0)
(548, 549, 0)
(548, 228, 0)
(548, 868, 0)
(549, 548, 0)
(549, 550, 0)
(549, 229, 0)
(549, 869, 0)
(550, 549, 0)
(550, 551, 0)
(550, 230, 0)
(550, 870, 0)
(551, 550, 0)
(551, 552, 0)
(551, 231, 0)
(551, 871, 0)
(552, 551, 0)
(552, 553, 0)
(552, 232, 0)
(552, 872, 0)
(553, 552, 0)
(553, 554, 0)
(553, 233, 0)
(553, 873, 0)
(554, 553, 0)
(554, 555, 0)
(554, 234, 0)
(554, 874, 0)
(555, 554, 0)
(555, 556, 0)
(555, 235, 0)
(555, 875, 0)
(556, 555, 0)
(556, 557, 0)
(556, 236, 0)
(556, 876, 0)
(557, 556, 0)
(557, 558, 0)
(557, 237, 0)
(557, 877, 0)
(558, 557, 0)
(558, 559, 0)
(558, 238, 0)
(558, 878, 0)
(559, 558, 0)
(559, 560, 0)
(559, 239, 0)
(559, 879, 0)
(560, 559, 0)
(560, 561, 0)
(560, 240, 0)
(560, 880, 0)
(561, 560, 0)
(561, 562, 0)
(561, 241, 0)
(561, 881, 0)
(562, 561, 0)
(562, 563, 0)
(562, 242, 0)
(562, 882, 0)
(563, 562, 0)
(563, 564, 0)
(563, 243, 0)
(563, 883, 0)
(564, 563, 0)
(564, 565, 0)
(564, 244, 0)
(564, 884, 0)
(565, 564, 0)
(565, 566, 0)
(565, 245, 0)
(565, 885, 0)
(566, 565, 0)
(566, 567, 0)
(566, 246, 0)
(566, 886, 0)
(567, 566, 0)
(567, 568, 0)
(567, 247, 0)
(567, 887, 0)
(568, 567, 0)
(568, 569, 0)
(568, 248, 0)
(568, 888, 0)
(569, 568, 0)
(569, 570, 0)
(569, 249, 0)
(569, 889, 0)
(570, 569, 0)
(570, 571, 0)
(570, 250, 0)
(570, 890, 0)
(571, 570, 0)
(571, 572, 0)
(571, 251, 0)
(571, 891, 0)
(572, 571, 0)
(572, 573, 0)
(572, 252, 0)
(572, 892, 0)
(573, 572, 0)
(573, 574, 0)
(573, 253, 0)
(573, 893, 0)
(574, 573, 0)
(574, 575, 0)
(574, 254, 0)
(574, 894, 0)
(575, 574, 0)
(575, 576, 0)
(575, 255, 0)
(575, 895, 0)
(576, 575, 0)
(576, 577, 0)
(576, 256, 0)
(576, 896, 0)
(577, 576, 0)
(577, 578, 0)
(577, 257, 0)
(577, 897, 0)
(578, 577, 0)
(578, 579, 0)
(578, 258, 0)
(578, 898, 0)
(579, 578, 0)
(579, 580, 0)
(579, 259, 0)
(579, 899, 0)
(580, 579, 0)
(580, 581, 0)
(580, 260, 0)
(580, 900, 0)
(581, 580, 0)
(581, 582, 0)
(581, 261, 0)
(581, 901, 0)
(582, 581, 0)
(582, 583, 0)
(582, 262, 0)
(582, 902, 0)
(583, 582, 0)
(583, 584, 0)
(583, 263, 0)
(583, 903, 0)
(584, 583, 0)
(584, 585, 0)
(584, 264, 0)
(584, 904, 0)
(585, 584, 0)
(585, 586, 0)
(585, 265, 0)
(585, 905, 0)
(586, 585, 0)
(586, 587, 0)
(586, 266, 0)
(586, 906, 0)
(587, 586, 0)
(587, 588, 0)
(587, 267, 0)
(587, 907, 0)
(588, 587, 0)
(588, 589, 0)
(588, 268, 0)
(588, 908, 0)
(589, 588, 0)
(589, 590, 0)
(589, 269, 0)
(589, 909, 0)
(590, 589, 0)
(590, 591, 0)
(590, 270, 0)
(590, 910, 0)
(591, 590, 0)
(591, 592, 0)
(591, 271, 0)
(591, 911, 0)
(592, 591, 0)
(592, 593, 0)
(592, 272, 0)
(592, 912, 0)
(593, 592, 0)
(593, 594, 0)
(593, 273, 0)
(593, 913, 0)
(594, 593, 0)
(594, 595, 0)
(594, 274, 0)
(594, 914, 0)
(595, 594, 0)
(595, 596, 0)
(595, 275, 0)
(595, 915, 0)
(596, 595, 0)
(596, 597, 0)
(596, 276, 0)
(596, 916, 0)
(597, 596, 0)
(597, 598, 0)
(597, 277, 0)
(597, 917, 0)
(598, 597, 0)
(598, 599, 0)
(598, 278, 0)
(598, 918, 0)
(599, 598, 0)
(599, 600, 0)
(599, 279, 0)
(599, 919, 0)
(600, 599, 0)
(600, 601, 0)
(600, 280, 0)
(600, 920, 0)
(601, 600, 0)
(601, 602, 0)
(601, 281, 0)
(601, 921, 0)
(602, 601, 0)
(602, 603, 0)
(602, 282, 0)
(602, 922, 0)
(603, 602, 0)
(603, 604, 0)
(603, 283, 0)
(603, 923, 0)
(604, 603, 0)
(604, 605, 0)
(604, 284, 0)
(604, 924, 0)
(605, 604, 0)
(605, 606, 0)
(605, 285, 0)
(605, 925, 0)
(606, 605, 0)
(606, 607, 0)
(606, 286, 0)
(606, 926, 0)
(607, 606, 0)
(607, 608, 0)
(607, 287, 0)
(607, 927, 0)
(608, 607, 0)
(608, 609, 0)
(608, 288, 0)
(608, 928, 0)
(609, 608, 0)
(609, 610, 0)
(609, 289, 0)
(609, 929, 0)
(610, 609, 0)
(610, 611, 0)
(610, 290, 0)
(610, 930, 0)
(611, 610, 0)
(611, 612, 0)
(611, 291, 0)
(611, 931, 0)
(612, 611, 0)
(612, 613, 0)
(612, 292, 0)
(612, 932, 0)
(613, 612, 0)
(613, 614, 0)
(613, 293, 0)
(613, 933, 0)
(614, 613, 0)
(614, 615, 0)
(614, 294, 0)
(614, 934, 0)
(615, 614, 0)
(615, 616, 0)
(615, 295, 0)
(615, 935, 0)
(616, 615, 0)
(616, 617, 0)
(616, 296, 0)
(616, 936, 0)
(617, 616, 0)
(617, 618, 0)
(617, 297, 0)
(617, 937, 0)
(618, 617, 0)
(618, 619, 0)
(618, 298, 0)
(618, 938, 0)
(619, 618, 0)
(619, 620, 0)
(619, 299, 0)
(619, 939, 0)
(620, 619, 0)
(620, 621, 0)
(620, 300, 0)
(620, 940, 0)
(621, 620, 0)
(621, 622, 0)
(621, 301, 0)
(621, 941, 0)
(622, 621, 0)
(622, 623, 0)
(622, 302, 0)
(622, 942, 0)
(623, 622, 0)
(623, 624, 0)
(623, 303, 0)
(623, 943, 0)
(624, 623, 0)
(624, 625, 0)
(624, 304, 0)
(624, 944, 0)
(625, 624, 0)
(625, 626, 0)
(625, 305, 0)
(625, 945, 0)
(626, 625, 0)
(626, 627, 0)
(626, 306, 0)
(626, 946, 0)
(627, 626, 0)
(627, 628, 0)
(627, 307, 0)
(627, 947, 0)
(628, 627, 0)
(628, 629, 0)
(628, 308, 0)
(628, 948, 0)
(629, 628, 0)
(629, 630, 0)
(629, 309, 0)
(629, 949, 0)
(630, 629, 0)
(630, 631, 0)
(630, 310, 0)
(630, 950, 0)
(631, 630, 0)
(631, 632, 0)
(631, 311, 0)
(631, 951, 0)
(632, 631, 0)
(632, 633, 0)
(632, 312, 0)
(632, 952, 0)
(633, 632, 0)
(633, 634, 0)
(633, 313, 0)
(633, 953, 0)
(634, 633, 0)
(634, 635, 0)
(634, 314, 0)
(634, 954, 0)
(635, 634, 0)
(635, 636, 0)
(635, 315, 0)
(635, 955, 0)
(636, 635, 0)
(636, 637, 0)
(636, 316, 0)
(636, 956, 0)
(637, 636, 0)
(637, 638, 0)
(637, 317, 0)
(637, 957, 0)
(638, 637, 0)
(638, 639, 0)
(638, 318, 0)
(638, 958, 0)
(639, 638, 0)
(639, 319, 0)
(639, 959, 0)
(640, 641, 0)
(640, 320, 0)
(640, 960, 0)
(641, 640, 0)
(641, 642, 0)
(641, 321, 0)
(641, 961, 0)
(642, 641, 0)
(642, 643, 0)
(642, 322, 0)
(642, 962, 0)
(643, 642, 0)
(643, 644, 0)
(643, 323, 0)
(643, 963, 0)
(644, 643, 0)
(644, 645, 0)
(644, 324, 0)
(644, 964, 0)
(645, 644, 0)
(645, 646, 0)
(645, 325, 0)
(645, 965, 0)
(646, 645, 0)
(646, 647, 0)
(646, 326, 0)
(646, 966, 0)
(647, 646, 0)
(647, 648, 0)
(647, 327, 0)
(647, 967, 0)
(648, 647, 0)
(648, 649, 0)
(648, 328, 0)
(648, 968, 0)
(649, 648, 0)
(649, 650, 0)
(649, 329, 0)
(649, 969, 0)
(650, 649, 0)
(650, 651, 0)
(650, 330, 0)
(650, 970, 0)
(651, 650, 0)
(651, 652, 0)
(651, 331, 0)
(651, 971, 0)
(652, 651, 0)
(652, 653, 0)
(652, 332, 0)
(652, 972, 0)
(653, 652, 0)
(653, 654, 0)
(653, 333, 0)
(653, 973, 0)
(654, 653, 0)
(654, 655, 0)
(654, 334, 0)
(654, 974, 0)
(655, 654, 0)
(655, 656, 0)
(655, 335, 0)
(655, 975, 0)
(656, 655, 0)
(656, 657, 0)
(656, 336, 0)
(656, 976, 0)
(657, 656, 0)
(657, 658, 0)
(657, 337, 0)
(657, 977, 0)
(658, 657, 0)
(658, 659, 0)
(658, 338, 0)
(658, 978, 0)
(659, 658, 0)
(659, 660, 0)
(659, 339, 0)
(659, 979, 0)
(660, 659, 0)
(660, 661, 0)
(660, 340, 0)
(660, 980, 0)
(661, 660, 0)
(661, 662, 0)
(661, 341, 0)
(661, 981, 0)
(662, 661, 0)
(662, 663, 0)
(662, 342, 0)
(662, 982, 0)
(663, 662, 0)
(663, 664, 0)
(663, 343, 0)
(663, 983, 0)
(664, 663, 0)
(664, 665, 0)
(664, 344, 0)
(664, 984, 0)
(665, 664, 0)
(665, 666, 0)
(665, 345, 0)
(665, 985, 0)
(666, 665, 0)
(666, 667, 0)
(666, 346, 0)
(666, 986, 0)
(667, 666, 0)
(667, 668, 0)
(667, 347, 0)
(667, 987, 0)
(668, 667, 0)
(668, 669, 0)
(668, 348, 0)
(668, 988, 0)
(669, 668, 0)
(669, 670, 0)
(669, 349, 0)
(669, 989, 0)
(670, 669, 0)
(670, 671, 0)
(670, 350, 0)
(670, 990, 0)
(671, 670, 0)
(671, 672, 0)
(671, 351, 0)
(671, 991, 0)
(672, 671, 0)
(672, 673, 0)
(672, 352, 0)
(672, 992, 0)
(673, 672, 0)
(673, 674, 0)
(673, 353, 0)
(673, 993, 0)
(674, 673, 0)
(674, 675, 0)
(674, 354, 0)
(674, 994, 0)
(675, 674, 0)
(675, 676, 0)
(675, 355, 0)
(675, 995, 0)
(676, 675, 0)
(676, 677, 0)
(676, 356, 0)
(676, 996, 0)
(677, 676, 0)
(677, 678, 0)
(677, 357, 0)
(677, 997, 0)
(678, 677, 0)
(678, 679, 0)
(678, 358, 0)
(678, 998, 0)
(679, 678, 0)
(679, 680, 0)
(679, 359, 0)
(679, 999, 0)
(680, 679, 0)
(680, 681, 0)
(680, 360, 0)
(680, 1000, 0)
(681, 680, 0)
(681, 682, 0)
(681, 361, 0)
(681, 1001, 0)
(682, 681, 0)
(682, 683, 0)
(682, 362, 0)
(682, 1002, 0)
(683, 682, 0)
(683, 684, 0)
(683, 363, 0)
(683, 1003, 0)
(684, 683, 0)
(684, 685, 0)
(684, 364, 0)
(684, 1004, 0)
(685, 684, 0)
(685, 686, 0)
(685, 365, 0)
(685, 1005, 0)
(686, 685, 0)
(686, 687, 0)
(686, 366, 0)
(686, 1006, 0)
(687, 686, 0)
(687, 688, 0)
(687, 367, 0)
(687, 1007, 0)
(688, 687, 0)
(688, 689, 0)
(688, 368, 0)
(688, 1008, 0)
(689, 688, 0)
(689, 690, 0)
(689, 369, 0)
(689, 1009, 0)
(690, 689, 0)
(690, 691, 0)
(690, 370, 0)
(690, 1010, 0)
(691, 690, 0)
(691, 692, 0)
(691, 371, 0)
(691, 1011, 0)
(692, 691, 0)
(692, 693, 0)
(692, 372, 0)
(692, 1012, 0)
(693, 692, 0)
(693, 694, 0)
(693, 373, 0)
(693, 1013, 0)
(694, 693, 0)
(694, 695, 0)
(694, 374, 0)
(694, 1014, 0)
(695, 694, 0)
(695, 696, 0)
(695, 375, 0)
(695, 1015, 0)
(696, 695, 0)
(696, 697, 0)
(696, 376, 0)
(696, 1016, 0)
(697, 696, 0)
(697, 698, 0)
(697, 377, 0)
(697, 1017, 0)
(698, 697, 0)
(698, 699, 0)
(698, 378, 0)
(698, 1018, 0)
(699, 698, 0)
(699, 700, 0)
(699, 379, 0)
(699, 1019, 0)
(700, 699, 0)
(700, 701, 0)
(700, 380, 0)
(700, 1020, 0)
(701, 700, 0)
(701, 702, 0)
(701, 381, 0)
(701, 1021, 0)
(702, 701, 0)
(702, 703, 0)
(702, 382, 0)
(702, 1022, 0)
(703, 702, 0)
(703, 704, 0)
(703, 383, 0)
(703, 1023, 0)
(704, 703, 0)
(704, 705, 0)
(704, 384, 0)
(704, 1024, 0)
(705, 704, 0)
(705, 706, 0)
(705, 385, 0)
(705, 1025, 0)
(706, 705, 0)
(706, 707, 0)
(706, 386, 0)
(706, 1026, 0)
(707, 706, 0)
(707, 708, 0)
(707, 387, 0)
(707, 1027, 0)
(708, 707, 0)
(708, 709, 0)
(708, 388, 0)
(708, 1028, 0)
(709, 708, 0)
(709, 710, 0)
(709, 389, 0)
(709, 1029, 0)
(710, 709, 0)
(710, 711, 0)
(710, 390, 0)
(710, 1030, 0)
(711, 710, 0)
(711, 712, 0)
(711, 391, 0)
(711, 1031, 0)
(712, 711, 0)
(712, 713, 0)
(712, 392, 0)
(712, 1032, 0)
(713, 712, 0)
(713, 714, 0)
(713, 393, 0)
(713, 1033, 0)
(714, 713, 0)
(714, 715, 0)
(714, 394, 0)
(714, 1034, 0)
(715, 714, 0)
(715, 716, 0)
(715, 395, 0)
(715, 1035, 0)
(716, 715, 0)
(716, 717, 0)
(716, 396, 0)
(716, 1036, 0)
(717, 716, 0)
(717, 718, 0)
(717, 397, 0)
(717, 1037, 0)
(718, 717, 0)
(718, 719, 0)
(718, 398, 0)
(718, 1038, 0)
(719, 718, 0)
(719, 720, 0)
(719, 399, 0)
(719, 1039, 0)
(720, 719, 0)
(720, 721, 0)
(720, 400, 0)
(720, 1040, 0)
(721, 720, 0)
(721, 722, 0)
(721, 401, 0)
(721, 1041, 0)
(722, 721, 0)
(722, 723, 0)
(722, 402, 0)
(722, 1042, 0)
(723, 722, 0)
(723, 724, 0)
(723, 403, 0)
(723, 1043, 0)
(724, 723, 0)
(724, 725, 0)
(724, 404, 0)
(724, 1044, 0)
(725, 724, 0)
(725, 726, 0)
(725, 405, 0)
(725, 1045, 0)
(726, 725, 0)
(726, 727, 0)
(726, 406, 0)
(726, 1046, 0)
(727, 726, 0)
(727, 728, 0)
(727, 407, 0)
(727, 1047, 0)
(728, 727, 0)
(728, 729, 0)
(728, 408, 0)
(728, 1048, 0)
(729, 728, 0)
(729, 730, 0)
(729, 409, 0)
(729, 1049, 0)
(730, 729, 0)
(730, 731, 0)
(730, 410, 0)
(730, 1050, 0)
(731, 730, 0)
(731, 732, 0)
(731, 411, 0)
(731, 1051, 0)
(732, 731, 0)
(732, 733, 0)
(732, 412, 0)
(732, 1052, 0)
(733, 732, 0)
(733, 734, 0)
(733, 413, 0)
(733, 1053, 0)
(734, 733, 0)
(734, 735, 0)
(734, 414, 0)
(734, 1054, 0)
(735, 734, 0)
(735, 736, 0)
(735, 415, 0)
(735, 1055, 0)
(736, 735, 0)
(736, 737, 0)
(736, 416, 0)
(736, 1056, 0)
(737, 736, 0)
(737, 738, 0)
(737, 417, 0)
(737, 1057, 0)
(738, 737, 0)
(738, 739, 0)
(738, 418, 0)
(738, 1058, 0)
(739, 738, 0)
(739, 740, 0)
(739, 419, 0)
(739, 1059, 0)
(740, 739, 0)
(740, 741, 0)
(740, 420, 0)
(740, 1060, 0)
(741, 740, 0)
(741, 742, 0)
(741, 421, 0)
(741, 1061, 0)
(742, 741, 0)
(742, 743, 0)
(742, 422, 0)
(742, 1062, 0)
(743, 742, 0)
(743, 744, 0)
(743, 423, 0)
(743, 1063, 0)
(744, 743, 0)
(744, 745, 0)
(744, 424, 0)
(744, 1064, 0)
(745, 744, 0)
(745, 746, 0)
(745, 425, 0)
(745, 1065, 0)
(746, 745, 0)
(746, 747, 0)
(746, 426, 0)
(746, 1066, 0)
(747, 746, 0)
(747, 748, 0)
(747, 427, 0)
(747, 1067, 0)
(748, 747, 0)
(748, 749, 0)
(748, 428, 0)
(748, 1068, 0)
(749, 748, 0)
(749, 750, 0)
(749, 429, 0)
(749, 1069, 0)
(750, 749, 0)
(750, 751, 0)
(750, 430, 0)
(750, 1070, 0)
(751, 750, 0)
(751, 752, 0)
(751, 431, 0)
(751, 1071, 0)
(752, 751, 0)
(752, 753, 0)
(752, 432, 0)
(752, 1072, 0)
(753, 752, 0)
(753, 754, 0)
(753, 433, 0)
(753, 1073, 0)
(754, 753, 0)
(754, 755, 0)
(754, 434, 0)
(754, 1074, 0)
(755, 754, 0)
(755, 756, 0)
(755, 435, 0)
(755, 1075, 0)
(756, 755, 0)
(756, 757, 0)
(756, 436, 0)
(756, 1076, 0)
(757, 756, 0)
(757, 758, 0)
(757, 437, 0)
(757, 1077, 0)
(758, 757, 0)
(758, 759, 0)
(758, 438, 0)
(758, 1078, 0)
(759, 758, 0)
(759, 760, 0)
(759, 439, 0)
(759, 1079, 0)
(760, 759, 0)
(760, 761, 0)
(760, 440, 0)
(760, 1080, 0)
(761, 760, 0)
(761, 762, 0)
(761, 441, 0)
(761, 1081, 0)
(762, 761, 0)
(762, 763, 0)
(762, 442, 0)
(762, 1082, 0)
(763, 762, 0)
(763, 764, 0)
(763, 443, 0)
(763, 1083, 0)
(764, 763, 0)
(764, 765, 0)
(764, 444, 0)
(764, 1084, 0)
(765, 764, 0)
(765, 766, 0)
(765, 445, 0)
(765, 1085, 0)
(766, 765, 0)
(766, 767, 0)
(766, 446, 0)
(766, 1086, 0)
(767, 766, 0)
(767, 768, 0)
(767, 447, 0)
(767, 1087, 0)
(768, 767, 0)
(768, 769, 0)
(768, 448, 0)
(768, 1088, 0)
(769, 768, 0)
(769, 770, 0)
(769, 449, 0)
(769, 1089, 0)
(770, 769, 0)
(770, 771, 0)
(770, 450, 0)
(770, 1090, 0)
(771, 770, 0)
(771, 772, 0)
(771, 451, 0)
(771, 1091, 0)
(772, 771, 0)
(772, 773, 0)
(772, 452, 0)
(772, 1092, 0)
(773, 772, 0)
(773, 774, 0)
(773, 453, 0)
(773, 1093, 0)
(774, 773, 0)
(774, 775, 0)
(774, 454, 0)
(774, 1094, 0)
(775, 774, 0)
(775, 776, 0)
(775, 455, 0)
(775, 1095, 0)
(776, 775, 0)
(776, 777, 0)
(776, 456, 0)
(776, 1096, 0)
(777, 776, 0)
(777, 778, 0)
(777, 457, 0)
(777, 1097, 0)
(778, 777, 0)
(778, 779, 0)
(778, 458, 0)
(778, 1098, 0)
(779, 778, 0)
(779, 780, 0)
(779, 459, 0)
(779, 1099, 0)
(780, 779, 0)
(780, 781, 0)
(780, 460, 0)
(780, 1100, 0)
(781, 780, 0)
(781, 782, 0)
(781, 461, 0)
(781, 1101, 0)
(782, 781, 0)
(782, 783, 0)
(782, 462, 0)
(782, 1102, 0)
(783, 782, 0)
(783, 784, 0)
(783, 463, 0)
(783, 1103, 0)
(784, 783, 0)
(784, 785, 0)
(784, 464, 0)
(784, 1104, 0)
(785, 784, 0)
(785, 786, 0)
(785, 465, 0)
(785, 1105, 0)
(786, 785, 0)
(786, 787, 0)
(786, 466, 0)
(786, 1106, 0)
(787, 786, 0)
(787, 788, 0)
(787, 467, 0)
(787, 1107, 0)
(788, 787, 0)
(788, 789, 0)
(788, 468, 0)
(788, 1108, 0)
(789, 788, 0)
(789, 790, 0)
(789, 469, 0)
(789, 1109, 0)
(790, 789, 0)
(790, 791, 0)
(790, 470, 0)
(790, 1110, 0)
(791, 790, 0)
(791, 792, 0)
(791, 471, 0)
(791, 1111, 0)
(792, 791, 0)
(792, 793, 0)
(792, 472, 0)
(792, 1112, 0)
(793, 792, 0)
(793, 794, 0)
(793, 473, 0)
(793, 1113, 0)
(794, 793, 0)
(794, 795, 0)
(794, 474, 0)
(794, 1114, 0)
(795, 794, 0)
(795, 796, 0)
(795, 475, 0)
(795, 1115, 0)
(796, 795, 0)
(796, 797, 0)
(796, 476, 0)
(796, 1116, 0)
(797, 796, 0)
(797, 798, 0)
(797, 477, 0)
(797, 1117, 0)
(798, 797, 0)
(798, 799, 0)
(798, 478, 0)
(798, 1118, 0)
(799, 798, 0)
(799, 800, 0)
(799, 479, 0)
(799, 1119, 0)
(800, 799, 0)
(800, 801, 0)
(800, 480, 0)
(800, 1120, 0)
(801, 800, 0)
(801, 802, 0)
(801, 481, 0)
(801, 1121, 0)
(802, 801, 0)
(802, 803, 0)
(802, 482, 0)
(802, 1122, 0)
(803, 802, 0)
(803, 804, 0)
(803, 483, 0)
(803, 1123, 0)
(804, 803, 0)
(804, 805, 0)
(804, 484, 0)
(804, 1124, 0)
(805, 804, 0)
(805, 806, 0)
(805, 485, 0)
(805, 1125, 0)
(806, 805, 0)
(806, 807, 0)
(806, 486, 0)
(806, 1126, 0)
(807, 806, 0)
(807, 808, 0)
(807, 487, 0)
(807, 1127, 0)
(808, 807, 0)
(808, 809, 0)
(808, 488, 0)
(808, 1128, 0)
(809, 808, 0)
(809, 810, 0)
(809, 489, 0)
(809, 1129, 0)
(810, 809, 0)
(810, 811, 0)
(810, 490, 0)
(810, 1130, 0)
(811, 810, 0)
(811, 812, 0)
(811, 491, 0)
(811, 1131, 0)
(812, 811, 0)
(812, 813, 0)
(812, 492, 0)
(812, 1132, 0)
(813, 812, 0)
(813, 814, 0)
(813, 493, 0)
(813, 1133, 0)
(814, 813, 0)
(814, 815, 0)
(814, 494, 0)
(814, 1134, 0)
(815, 814, 0)
(815, 816, 0)
(815, 495, 0)
(815, 1135, 0)
(816, 815, 0)
(816, 817, 0)
(816, 496, 0)
(816, 1136, 0)
(817, 816, 0)
(817, 818, 0)
(817, 497, 0)
(817, 1137, 0)
(818, 817, 0)
(818, 819, 0)
(818, 498, 0)
(818, 1138, 0)
(819, 818, 0)
(819, 820, 0)
(819, 499, 0)
(819, 1139, 0)
(820, 819, 0)
(820, 821, 0)
(820, 500, 0)
(820, 1140, 0)
(821, 820, 0)
(821, 822, 0)
(821, 501, 0)
(821, 1141, 0)
(822, 821, 0)
(822, 823, 0)
(822, 502, 0)
(822, 1142, 0)
(823, 822, 0)
(823, 824, 0)
(823, 503, 0)
(823, 1143, 0)
(824, 823, 0)
(824, 825, 0)
(824, 504, 0)
(824, 1144, 0)
(825, 824, 0)
(825, 826, 0)
(825, 505, 0)
(825, 1145, 0)
(826, 825, 0)
(826, 827, 0)
(826, 506, 0)
(826, 1146, 0)
(827, 826, 0)
(827, 828, 0)
(827, 507, 0)
(827, 1147, 0)
(828, 827, 0)
(828, 829, 0)
(828, 508, 0)
(828, 1148, 0)
(829, 828, 0)
(829, 830, 0)
(829, 509, 0)
(829, 1149, 0)
(830, 829, 0)
(830, 831, 0)
(830, 510, 0)
(830, 1150, 0)
(831, 830, 0)
(831, 832, 0)
(831, 511, 0)
(831, 1151, 0)
(832, 831, 0)
(832, 833, 0)
(832, 512, 0)
(832, 1152, 0)
(833, 832, 0)
(833, 834, 0)
(833, 513, 0)
(833, 1153, 0)
(834, 833, 0)
(834, 835, 0)
(834, 514, 0)
(834, 1154, 0)
(835, 834, 0)
(835, 836, 0)
(835, 515, 0)
(835, 1155, 0)
(836, 835, 0)
(836, 837, 0)
(836, 516, 0)
(836, 1156, 0)
(837, 836, 0)
(837, 838, 0)
(837, 517, 0)
(837, 1157, 0)
(838, 837, 0)
(838, 839, 0)
(838, 518, 0)
(838, 1158, 0)
(839, 838, 0)
(839, 840, 0)
(839, 519, 0)
(839, 1159, 0)
(840, 839, 0)
(840, 841, 0)
(840, 520, 0)
(840, 1160, 0)
(841, 840, 0)
(841, 842, 0)
(841, 521, 0)
(841, 1161, 0)
(842, 841, 0)
(842, 843, 0)
(842, 522, 0)
(842, 1162, 0)
(843, 842, 0)
(843, 844, 0)
(843, 523, 0)
(843, 1163, 0)
(844, 843, 0)
(844, 845, 0)
(844, 524, 0)
(844, 1164, 0)
(845, 844, 0)
(845, 846, 0)
(845, 525, 0)
(845, 1165, 0)
(846, 845, 0)
(846, 847, 0)
(846, 526, 0)
(846, 1166, 0)
(847, 846, 0)
(847, 848, 0)
(847, 527, 0)
(847, 1167, 0)
(848, 847, 0)
(848, 849, 0)
(848, 528, 0)
(848, 1168, 0)
(849, 848, 0)
(849, 850, 0)
(849, 529, 0)
(849, 1169, 0)
(850, 849, 0)
(850, 851, 0)
(850, 530, 0)
(850, 1170, 0)
(851, 850, 0)
(851, 852, 0)
(851, 531, 0)
(851, 1171, 0)
(852, 851, 0)
(852, 853, 0)
(852, 532, 0)
(852, 1172, 0)
(853, 852, 0)
(853, 854, 0)
(853, 533, 0)
(853, 1173, 0)
(854, 853, 0)
(854, 855, 0)
(854, 534, 0)
(854, 1174, 0)
(855, 854, 0)
(855, 856, 0)
(855, 535, 0)
(855, 1175, 0)
(856, 855, 0)
(856, 857, 0)
(856, 536, 0)
(856, 1176, 0)
(857, 856, 0)
(857, 858, 0)
(857, 537, 0)
(857, 1177, 0)
(858, 857, 0)
(858, 859, 0)
(858, 538, 0)
(858, 1178, 0)
(859, 858, 0)
(859, 860, 0)
(859, 539, 0)
(859, 1179, 0)
(860, 859, 0)
(860, 861, 0)
(860, 540, 0)
(860, 1180, 0)
(861, 860, 0)
(861, 862, 0)
(861, 541, 0)
(861, 1181, 0)
(862, 861, 0)
(862, 863, 0)
(862, 542, 0)
(862, 1182, 0)
(863, 862, 0)
(863, 864, 0)
(863, 543, 0)
(863, 1183, 0)
(864, 863, 0)
(864, 865, 0)
(864, 544, 0)
(864, 1184, 0)
(865, 864, 0)
(865, 866, 0)
(865, 545, 0)
(865, 1185, 0)
(866, 865, 0)
(866, 867, 0)
(866, 546, 0)
(866, 1186, 0)
(867, 866, 0)
(867, 868, 0)
(867, 547, 0)
(867, 1187, 0)
(868, 867, 0)
(868, 869, 0)
(868, 548, 0)
(868, 1188, 0)
(869, 868, 0)
(869, 870, 0)
(869, 549, 0)
(869, 1189, 0)
(870, 869, 0)
(870, 871, 0)
(870, 550, 0)
(870, 1190, 0)
(871, 870, 0)
(871, 872, 0)
(871, 551, 0)
(871, 1191, 0)
(872, 871, 0)
(872, 873, 0)
(872, 552, 0)
(872, 1192, 0)
(873, 872, 0)
(873, 874, 0)
(873, 553, 0)
(873, 1193, 0)
(874, 873, 0)
(874, 875, 0)
(874, 554, 0)
(874, 1194, 0)
(875, 874, 0)
(875, 876, 0)
(875, 555, 0)
(875, 1195, 0)
(876, 875, 0)
(876, 877, 0)
(876, 556, 0)
(876, 1196, 0)
(877, 876, 0)
(877, 878, 0)
(877, 557, 0)
(877, 1197, 0)
(878, 877, 0)
(878, 879, 0)
(878, 558, 0)
(878, 1198, 0)
(879, 878, 0)
(879, 880, 0)
(879, 559, 0)
(879, 1199, 0)
(880, 879, 0)
(880, 881, 0)
(880, 560, 0)
(880, 1200, 0)
(881, 880, 0)
(881, 882, 0)
(881, 561, 0)
(881, 1201, 0)
(882, 881, 0)
(882, 883, 0)
(882, 562, 0)
(882, 1202, 0)
(883, 882, 0)
(883, 884, 0)
(883, 563, 0)
(883, 1203, 0)
(884, 883, 0)
(884, 885, 0)
(884, 564, 0)
(884, 1204, 0)
(885, 884, 0)
(885, 886, 0)
(885, 565, 0)
(885, 1205, 0)
(886, 885, 0)
(886, 887, 0)
(886, 566, 0)
(886, 1206, 0)
(887, 886, 0)
(887, 888, 0)
(887, 567, 0)
(887, 1207, 0)
(888, 887, 0)
(888, 889, 0)
(888, 568, 0)
(888, 1208, 0)
(889, 888, 0)
(889, 890, 0)
(889, 569, 0)
(889, 1209, 0)
(890, 889, 0)
(890, 891, 0)
(890, 570, 0)
(890, 1210, 0)
(891, 890, 0)
(891, 892, 0)
(891, 571, 0)
(891, 1211, 0)
(892, 891, 0)
(892, 893, 0)
(892, 572, 0)
(892, 1212, 0)
(893, 892, 0)
(893, 894, 0)
(893, 573, 0)
(893, 1213, 0)
(894, 893, 0)
(894, 895, 0)
(894, 574, 0)
(894, 1214, 0)
(895, 894, 0)
(895, 896, 0)
(895, 575, 0)
(895, 1215, 0)
(896, 895, 0)
(896, 897, 0)
(896, 576, 0)
(896, 1216, 0)
(897, 896, 0)
(897, 898, 0)
(897, 577, 0)
(897, 1217, 0)
(898, 897, 0)
(898, 899, 0)
(898, 578, 0)
(898, 1218, 0)
(899, 898, 0)
(899, 900, 0)
(899, 579, 0)
(899, 1219, 0)
(900, 899, 0)
(900, 901, 0)
(900, 580, 0)
(900, 1220, 0)
(901, 900, 0)
(901, 902, 0)
(901, 581, 0)
(901, 1221, 0)
(902, 901, 0)
(902, 903, 0)
(902, 582, 0)
(902, 1222, 0)
(903, 902, 0)
(903, 904, 0)
(903, 583, 0)
(903, 1223, 0)
(904, 903, 0)
(904, 905, 0)
(904, 584, 0)
(904, 1224, 0)
(905, 904, 0)
(905, 906, 0)
(905, 585, 0)
(905, 1225, 0)
(906, 905, 0)
(906, 907, 0)
(906, 586, 0)
(906, 1226, 0)
(907, 906, 0)
(907, 908, 0)
(907, 587, 0)
(907, 1227, 0)
(908, 907, 0)
(908, 909, 0)
(908, 588, 0)
(908, 1228, 0)
(909, 908, 0)
(909, 910, 0)
(909, 589, 0)
(909, 1229, 0)
(910, 909, 0)
(910, 911, 0)
(910, 590, 0)
(910, 1230, 0)
(911, 910, 0)
(911, 912, 0)
(911, 591, 0)
(911, 1231, 0)
(912, 911, 0)
(912, 913, 0)
(912, 592, 0)
(912, 1232, 0)
(913, 912, 0)
(913, 914, 0)
(913, 593, 0)
(913, 1233, 0)
(914, 913, 0)
(914, 915, 0)
(914, 594, 0)
(914, 1234, 0)
(915, 914, 0)
(915, 916, 0)
(915, 595, 0)
(915, 1235, 0)
(916, 915, 0)
(916, 917, 0)
(916, 596, 0)
(916, 1236, 0)
(917, 916, 0)
(917, 918, 0)
(917, 597, 0)
(917, 1237, 0)
(918, 917, 0)
(918, 919, 0)
(918, 598, 0)
(918, 1238, 0)
(919, 918, 0)
(919, 920, 0)
(919, 599, 0)
(919, 1239, 0)
(920, 919, 0)
(920, 921, 0)
(920, 600, 0)
(920, 1240, 0)
(921, 920, 0)
(921, 922, 0)
(921, 601, 0)
(921, 1241, 0)
(922, 921, 0)
(922, 923, 0)
(922, 602, 0)
(922, 1242, 0)
(923, 922, 0)
(923, 924, 0)
(923, 603, 0)
(923, 1243, 0)
(924, 923, 0)
(924, 925, 0)
(924, 604, 0)
(924, 1244, 0)
(925, 924, 0)
(925, 926, 0)
(925, 605, 0)
(925, 1245, 0)
(926, 925, 0)
(926, 927, 0)
(926, 606, 0)
(926, 1246, 0)
(927, 926, 0)
(927, 928, 0)
(927, 607, 0)
(927, 1247, 0)
(928, 927, 0)
(928, 929, 0)
(928, 608, 0)
(928, 1248, 0)
(929, 928, 0)
(929, 930, 0)
(929, 609, 0)
(929, 1249, 0)
(930, 929, 0)
(930, 931, 0)
(930, 610, 0)
(930, 1250, 0)
(931, 930, 0)
(931, 932, 0)
(931, 611, 0)
(931, 1251, 0)
(932, 931, 0)
(932, 933, 0)
(932, 612, 0)
(932, 1252, 0)
(933, 932, 0)
(933, 934, 0)
(933, 613, 0)
(933, 1253, 0)
(934, 933, 0)
(934, 935, 0)
(934, 614, 0)
(934, 1254, 0)
(935, 934, 0)
(935, 936, 0)
(935, 615, 0)
(935, 1255, 0)
(936, 935, 0)
(936, 937, 0)
(936, 616, 0)
(936, 1256, 0)
(937, 936, 0)
(937, 938, 0)
(937, 617, 0)
(937, 1257, 0)
(938, 937, 0)
(938, 939, 0)
(938, 618, 0)
(938, 1258, 0)
(939, 938, 0)
(939, 940, 0)
(939, 619, 0)
(939, 1259, 0)
(940, 939, 0)
(940, 941, 0)
(940, 620, 0)
(940, 1260, 0)
(941, 940, 0)
(941, 942, 0)
(941, 621, 0)
(941, 1261, 0)
(942, 941, 0)
(942, 943, 0)
(942, 622, 0)
(942, 1262, 0)
(943, 942, 0)
(943, 944, 0)
(943, 623, 0)
(943, 1263, 0)
(944, 943, 0)
(944, 945, 0)
(944, 624, 0)
(944, 1264, 0)
(945, 944, 0)
(945, 946, 0)
(945, 625, 0)
(945, 1265, 0)
(946, 945, 0)
(946, 947, 0)
(946, 626, 0)
(946, 1266, 0)
(947, 946, 0)
(947, 948, 0)
(947, 627, 0)
(947, 1267, 0)
(948, 947, 0)
(948, 949, 0)
(948, 628, 0)
(948, 1268, 0)
(949, 948, 0)
(949, 950, 0)
(949, 629, 0)
(949, 1269, 0)
(950, 949, 0)
(950, 951, 0)
(950, 630, 0)
(950, 1270, 0)
(951, 950, 0)
(951, 952, 0)
(951, 631, 0)
(951, 1271, 0)
(952, 951, 0)
(952, 953, 0)
(952, 632, 0)
(952, 1272, 0)
(953, 952, 0)
(953, 954, 0)
(953, 633, 0)
(953, 1273, 0)
(954, 953, 0)
(954, 955, 0)
(954, 634, 0)
(954, 1274, 0)
(955, 954, 0)
(955, 956, 0)
(955, 635, 0)
(955, 1275, 0)
(956, 955, 0)
(956, 957, 0)
(956, 636, 0)
(956, 1276, 0)
(957, 956, 0)
(957, 958, 0)
(957, 637, 0)
(957, 1277, 0)
(958, 957, 0)
(958, 959, 0)
(958, 638, 0)
(958, 1278, 0)
(959, 958, 0)
(959, 639, 0)
(959, 1279, 0)
(960, 961, 0)
(960, 640, 0)
(960, 1280, 0)
(961, 960, 0)
(961, 962, 0)
(961, 641, 0)
(961, 1281, 0)
(962, 961, 0)
(962, 963, 0)
(962, 642, 0)
(962, 1282, 0)
(963, 962, 0)
(963, 964, 0)
(963, 643, 0)
(963, 1283, 0)
(964, 963, 0)
(964, 965, 0)
(964, 644, 0)
(964, 1284, 0)
(965, 964, 0)
(965, 966, 0)
(965, 645, 0)
(965, 1285, 0)
(966, 965, 0)
(966, 967, 0)
(966, 646, 0)
(966, 1286, 0)
(967, 966, 0)
(967, 968, 0)
(967, 647, 0)
(967, 1287, 0)
(968, 967, 0)
(968, 969, 0)
(968, 648, 0)
(968, 1288, 0)
(969, 968, 0)
(969, 970, 0)
(969, 649, 0)
(969, 1289, 0)
(970, 969, 0)
(970, 971, 0)
(970, 650, 0)
(970, 1290, 0)
(971, 970, 0)
(971, 972, 0)
(971, 651, 0)
(971, 1291, 0)
(972, 971, 0)
(972, 973, 0)
(972, 652, 0)
(972, 1292, 0)
(973, 972, 0)
(973, 974, 0)
(973, 653, 0)
(973, 1293, 0)
(974, 973, 0)
(974, 975, 0)
(974, 654, 0)
(974, 1294, 0)
(975, 974, 0)
(975, 976, 0)
(975, 655, 0)
(975, 1295, 0)
(976, 975, 0)
(976, 977, 0)
(976, 656, 0)
(977, 976, 0)
(977, 978, 0)
(977, 657, 0)
(978, 977, 0)
(978, 979, 0)
(978, 658, 0)
(978, 1298, 0)
(979, 978, 0)
(979, 980, 0)
(979, 659, 0)
(979, 1299, 0)
(980, 979, 0)
(980, 981, 0)
(980, 660, 0)
(980, 1300, 0)
(981, 980, 0)
(981, 982, 0)
(981, 661, 0)
(981, 1301, 0)
(982, 981, 0)
(982, 983, 0)
(982, 662, 0)
(982, 1302, 0)
(983, 982, 0)
(983, 984, 0)
(983, 663, 0)
(983, 1303, 0)
(984, 983, 0)
(984, 985, 0)
(984, 664, 0)
(984, 1304, 0)
(985, 984, 0)
(985, 986, 0)
(985, 665, 0)
(985, 1305, 0)
(986, 985, 0)
(986, 987, 0)
(986, 666, 0)
(986, 1306, 0)
(987, 986, 0)
(987, 988, 0)
(987, 667, 0)
(987, 1307, 0)
(988, 987, 0)
(988, 989, 0)
(988, 668, 0)
(988, 1308, 0)
(989, 988, 0)
(989, 990, 0)
(989, 669, 0)
(989, 1309, 0)
(990, 989, 0)
(990, 991, 0)
(990, 670, 0)
(990, 1310, 0)
(991, 990, 0)
(991, 992, 0)
(991, 671, 0)
(991, 1311, 0)
(992, 991, 0)
(992, 993, 0)
(992, 672, 0)
(992, 1312, 0)
(993, 992, 0)
(993, 994, 0)
(993, 673, 0)
(993, 1313, 0)
(994, 993, 0)
(994, 995, 0)
(994, 674, 0)
(994, 1314, 0)
(995, 994, 0)
(995, 996, 0)
(995, 675, 0)
(995, 1315, 0)
(996, 995, 0)
(996, 997, 0)
(996, 676, 0)
(996, 1316, 0)
(997, 996, 0)
(997, 998, 0)
(997, 677, 0)
(997, 1317, 0)
(998, 997, 0)
(998, 999, 0)
(998, 678, 0)
(998, 1318, 0)
(999, 998, 0)
(999, 1000, 0)
(999, 679, 0)
(999, 1319, 0)
(1000, 999, 0)
(1000, 1001, 0)
(1000, 680, 0)
(1000, 1320, 0)
(1001, 1000, 0)
(1001, 1002, 0)
(1001, 681, 0)
(1001, 1321, 0)
(1002, 1001, 0)
(1002, 1003, 0)
(1002, 682, 0)
(1002, 1322, 0)
(1003, 1002, 0)
(1003, 1004, 0)
(1003, 683, 0)
(1003, 1323, 0)
(1004, 1003, 0)
(1004, 1005, 0)
(1004, 684, 0)
(1004, 1324, 0)
(1005, 1004, 0)
(1005, 1006, 0)
(1005, 685, 0)
(1005, 1325, 0)
(1006, 1005, 0)
(1006, 1007, 0)
(1006, 686, 0)
(1006, 1326, 0)
(1007, 1006, 0)
(1007, 1008, 0)
(1007, 687, 0)
(1007, 1327, 0)
(1008, 1007, 0)
(1008, 1009, 0)
(1008, 688, 0)
(1008, 1328, 0)
(1009, 1008, 0)
(1009, 1010, 0)
(1009, 689, 0)
(1009, 1329, 0)
(1010, 1009, 0)
(1010, 1011, 0)
(1010, 690, 0)
(1010, 1330, 0)
(1011, 1010, 0)
(1011, 1012, 0)
(1011, 691, 0)
(1011, 1331, 0)
(1012, 1011, 0)
(1012, 1013, 0)
(1012, 692, 0)
(1012, 1332, 0)
(1013, 1012, 0)
(1013, 1014, 0)
(1013, 693, 0)
(1013, 1333, 0)
(1014, 1013, 0)
(1014, 1015, 0)
(1014, 694, 0)
(1014, 1334, 0)
(1015, 1014, 0)
(1015, 1016, 0)
(1015, 695, 0)
(1015, 1335, 0)
(1016, 1015, 0)
(1016, 1017, 0)
(1016, 696, 0)
(1016, 1336, 0)
(1017, 1016, 0)
(1017, 1018, 0)
(1017, 697, 0)
(1017, 1337, 0)
(1018, 1017, 0)
(1018, 1019, 0)
(1018, 698, 0)
(1018, 1338, 0)
(1019, 1018, 0)
(1019, 1020, 0)
(1019, 699, 0)
(1019, 1339, 0)
(1020, 1019, 0)
(1020, 1021, 0)
(1020, 700, 0)
(1020, 1340, 0)
(1021, 1020, 0)
(1021, 1022, 0)
(1021, 701, 0)
(1021, 1341, 0)
(1022, 1021, 0)
(1022, 1023, 0)
(1022, 702, 0)
(1022, 1342, 0)
(1023, 1022, 0)
(1023, 1024, 0)
(1023, 703, 0)
(1023, 1343, 0)
(1024, 1023, 0)
(1024, 1025, 0)
(1024, 704, 0)
(1024, 1344, 0)
(1025, 1024, 0)
(1025, 1026, 0)
(1025, 705, 0)
(1025, 1345, 0)
(1026, 1025, 0)
(1026, 1027, 0)
(1026, 706, 0)
(1026, 1346, 0)
(1027, 1026, 0)
(1027, 1028, 0)
(1027, 707, 0)
(1027, 1347, 0)
(1028, 1027, 0)
(1028, 1029, 0)
(1028, 708, 0)
(1028, 1348, 0)
(1029, 1028, 0)
(1029, 1030, 0)
(1029, 709, 0)
(1029, 1349, 0)
(1030, 1029, 0)
(1030, 1031, 0)
(1030, 710, 0)
(1030, 1350, 0)
(1031, 1030, 0)
(1031, 1032, 0)
(1031, 711, 0)
(1031, 1351, 0)
(1032, 1031, 0)
(1032, 1033, 0)
(1032, 712, 0)
(1032, 1352, 0)
(1033, 1032, 0)
(1033, 1034, 0)
(1033, 713, 0)
(1033, 1353, 0)
(1034, 1033, 0)
(1034, 1035, 0)
(1034, 714, 0)
(1034, 1354, 0)
(1035, 1034, 0)
(1035, 1036, 0)
(1035, 715, 0)
(1035, 1355, 0)
(1036, 1035, 0)
(1036, 1037, 0)
(1036, 716, 0)
(1036, 1356, 0)
(1037, 1036, 0)
(1037, 1038, 0)
(1037, 717, 0)
(1037, 1357, 0)
(1038, 1037, 0)
(1038, 1039, 0)
(1038, 718, 0)
(1038, 1358, 0)
(1039, 1038, 0)
(1039, 1040, 0)
(1039, 719, 0)
(1039, 1359, 0)
(1040, 1039, 0)
(1040, 1041, 0)
(1040, 720, 0)
(1040, 1360, 0)
(1041, 1040, 0)
(1041, 1042, 0)
(1041, 721, 0)
(1041, 1361, 0)
(1042, 1041, 0)
(1042, 1043, 0)
(1042, 722, 0)
(1042, 1362, 0)
(1043, 1042, 0)
(1043, 1044, 0)
(1043, 723, 0)
(1043, 1363, 0)
(1044, 1043, 0)
(1044, 1045, 0)
(1044, 724, 0)
(1044, 1364, 0)
(1045, 1044, 0)
(1045, 1046, 0)
(1045, 725, 0)
(1045, 1365, 0)
(1046, 1045, 0)
(1046, 1047, 0)
(1046, 726, 0)
(1046, 1366, 0)
(1047, 1046, 0)
(1047, 1048, 0)
(1047, 727, 0)
(1047, 1367, 0)
(1048, 1047, 0)
(1048, 1049, 0)
(1048, 728, 0)
(1048, 1368, 0)
(1049, 1048, 0)
(1049, 1050, 0)
(1049, 729, 0)
(1049, 1369, 0)
(1050, 1049, 0)
(1050, 1051, 0)
(1050, 730, 0)
(1050, 1370, 0)
(1051, 1050, 0)
(1051, 1052, 0)
(1051, 731, 0)
(1051, 1371, 0)
(1052, 1051, 0)
(1052, 1053, 0)
(1052, 732, 0)
(1052, 1372, 0)
(1053, 1052, 0)
(1053, 1054, 0)
(1053, 733, 0)
(1053, 1373, 0)
(1054, 1053, 0)
(1054, 1055, 0)
(1054, 734, 0)
(1054, 1374, 0)
(1055, 1054, 0)
(1055, 1056, 0)
(1055, 735, 0)
(1055, 1375, 0)
(1056, 1055, 0)
(1056, 1057, 0)
(1056, 736, 0)
(1056, 1376, 0)
(1057, 1056, 0)
(1057, 1058, 0)
(1057, 737, 0)
(1057, 1377, 0)
(1058, 1057, 0)
(1058, 1059, 0)
(1058, 738, 0)
(1058, 1378, 0)
(1059, 1058, 0)
(1059, 1060, 0)
(1059, 739, 0)
(1059, 1379, 0)
(1060, 1059, 0)
(1060, 1061, 0)
(1060, 740, 0)
(1060, 1380, 0)
(1061, 1060, 0)
(1061, 1062, 0)
(1061, 741, 0)
(1061, 1381, 0)
(1062, 1061, 0)
(1062, 1063, 0)
(1062, 742, 0)
(1062, 1382, 0)
(1063, 1062, 0)
(1063, 1064, 0)
(1063, 743, 0)
(1063, 1383, 0)
(1064, 1063, 0)
(1064, 1065, 0)
(1064, 744, 0)
(1064, 1384, 0)
(1065, 1064, 0)
(1065, 1066, 0)
(1065, 745, 0)
(1065, 1385, 0)
(1066, 1065, 0)
(1066, 1067, 0)
(1066, 746, 0)
(1066, 1386, 0)
(1067, 1066, 0)
(1067, 1068, 0)
(1067, 747, 0)
(1067, 1387, 0)
(1068, 1067, 0)
(1068, 1069, 0)
(1068, 748, 0)
(1068, 1388, 0)
(1069, 1068, 0)
(1069, 1070, 0)
(1069, 749, 0)
(1069, 1389, 0)
(1070, 1069, 0)
(1070, 1071, 0)
(1070, 750, 0)
(1070, 1390, 0)
(1071, 1070, 0)
(1071, 1072, 0)
(1071, 751, 0)
(1071, 1391, 0)
(1072, 1071, 0)
(1072, 1073, 0)
(1072, 752, 0)
(1072, 1392, 0)
(1073, 1072, 0)
(1073, 1074, 0)
(1073, 753, 0)
(1073, 1393, 0)
(1074, 1073, 0)
(1074, 1075, 0)
(1074, 754, 0)
(1074, 1394, 0)
(1075, 1074, 0)
(1075, 1076, 0)
(1075, 755, 0)
(1075, 1395, 0)
(1076, 1075, 0)
(1076, 1077, 0)
(1076, 756, 0)
(1076, 1396, 0)
(1077, 1076, 0)
(1077, 1078, 0)
(1077, 757, 0)
(1077, 1397, 0)
(1078, 1077, 0)
(1078, 1079, 0)
(1078, 758, 0)
(1078, 1398, 0)
(1079, 1078, 0)
(1079, 1080, 0)
(1079, 759, 0)
(1079, 1399, 0)
(1080, 1079, 0)
(1080, 1081, 0)
(1080, 760, 0)
(1080, 1400, 0)
(1081, 1080, 0)
(1081, 1082, 0)
(1081, 761, 0)
(1081, 1401, 0)
(1082, 1081, 0)
(1082, 1083, 0)
(1082, 762, 0)
(1082, 1402, 0)
(1083, 1082, 0)
(1083, 1084, 0)
(1083, 763, 0)
(1083, 1403, 0)
(1084, 1083, 0)
(1084, 1085, 0)
(1084, 764, 0)
(1084, 1404, 0)
(1085, 1084, 0)
(1085, 1086, 0)
(1085, 765, 0)
(1085, 1405, 0)
(1086, 1085, 0)
(1086, 1087, 0)
(1086, 766, 0)
(1086, 1406, 0)
(1087, 1086, 0)
(1087, 1088, 0)
(1087, 767, 0)
(1087, 1407, 0)
(1088, 1087, 0)
(1088, 1089, 0)
(1088, 768, 0)
(1088, 1408, 0)
(1089, 1088, 0)
(1089, 1090, 0)
(1089, 769, 0)
(1089, 1409, 0)
(1090, 1089, 0)
(1090, 1091, 0)
(1090, 770, 0)
(1090, 1410, 0)
(1091, 1090, 0)
(1091, 1092, 0)
(1091, 771, 0)
(1091, 1411, 0)
(1092, 1091, 0)
(1092, 1093, 0)
(1092, 772, 0)
(1092, 1412, 0)
(1093, 1092, 0)
(1093, 1094, 0)
(1093, 773, 0)
(1093, 1413, 0)
(1094, 1093, 0)
(1094, 1095, 0)
(1094, 774, 0)
(1094, 1414, 0)
(1095, 1094, 0)
(1095, 1096, 0)
(1095, 775, 0)
(1095, 1415, 0)
(1096, 1095, 0)
(1096, 1097, 0)
(1096, 776, 0)
(1096, 1416, 0)
(1097, 1096, 0)
(1097, 1098, 0)
(1097, 777, 0)
(1097, 1417, 0)
(1098, 1097, 0)
(1098, 1099, 0)
(1098, 778, 0)
(1098, 1418, 0)
(1099, 1098, 0)
(1099, 1100, 0)
(1099, 779, 0)
(1099, 1419, 0)
(1100, 1099, 0)
(1100, 1101, 0)
(1100, 780, 0)
(1100, 1420, 0)
(1101, 1100, 0)
(1101, 1102, 0)
(1101, 781, 0)
(1101, 1421, 0)
(1102, 1101, 0)
(1102, 1103, 0)
(1102, 782, 0)
(1102, 1422, 0)
(1103, 1102, 0)
(1103, 1104, 0)
(1103, 783, 0)
(1103, 1423, 0)
(1104, 1103, 0)
(1104, 1105, 0)
(1104, 784, 0)
(1104, 1424, 0)
(1105, 1104, 0)
(1105, 1106, 0)
(1105, 785, 0)
(1105, 1425, 0)
(1106, 1105, 0)
(1106, 1107, 0)
(1106, 786, 0)
(1106, 1426, 0)
(1107, 1106, 0)
(1107, 1108, 0)
(1107, 787, 0)
(1107, 1427, 0)
(1108, 1107, 0)
(1108, 1109, 0)
(1108, 788, 0)
(1108, 1428, 0)
(1109, 1108, 0)
(1109, 1110, 0)
(1109, 789, 0)
(1109, 1429, 0)
(1110, 1109, 0)
(1110, 1111, 0)
(1110, 790, 0)
(1110, 1430, 0)
(1111, 1110, 0)
(1111, 1112, 0)
(1111, 791, 0)
(1111, 1431, 0)
(1112, 1111, 0)
(1112, 1113, 0)
(1112, 792, 0)
(1112, 1432, 0)
(1113, 1112, 0)
(1113, 1114, 0)
(1113, 793, 0)
(1113, 1433, 0)
(1114, 1113, 0)
(1114, 1115, 0)
(1114, 794, 0)
(1114, 1434, 0)
(1115, 1114, 0)
(1115, 1116, 0)
(1115, 795, 0)
(1115, 1435, 0)
(1116, 1115, 0)
(1116, 1117, 0)
(1116, 796, 0)
(1116, 1436, 0)
(1117, 1116, 0)
(1117, 1118, 0)
(1117, 797, 0)
(1117, 1437, 0)
(1118, 1117, 0)
(1118, 1119, 0)
(1118, 798, 0)
(1118, 1438, 0)
(1119, 1118, 0)
(1119, 1120, 0)
(1119, 799, 0)
(1119, 1439, 0)
(1120, 1119, 0)
(1120, 1121, 0)
(1120, 800, 0)
(1120, 1440, 0)
(1121, 1120, 0)
(1121, 1122, 0)
(1121, 801, 0)
(1121, 1441, 0)
(1122, 1121, 0)
(1122, 1123, 0)
(1122, 802, 0)
(1122, 1442, 0)
(1123, 1122, 0)
(1123, 1124, 0)
(1123, 803, 0)
(1123, 1443, 0)
(1124, 1123, 0)
(1124, 1125, 0)
(1124, 804, 0)
(1124, 1444, 0)
(1125, 1124, 0)
(1125, 1126, 0)
(1125, 805, 0)
(1125, 1445, 0)
(1126, 1125, 0)
(1126, 1127, 0)
(1126, 806, 0)
(1126, 1446, 0)
(1127, 1126, 0)
(1127, 1128, 0)
(1127, 807, 0)
(1127, 1447, 0)
(1128, 1127, 0)
(1128, 1129, 0)
(1128, 808, 0)
(1128, 1448, 0)
(1129, 1128, 0)
(1129, 1130, 0)
(1129, 809, 0)
(1129, 1449, 0)
(1130, 1129, 0)
(1130, 1131, 0)
(1130, 810, 0)
(1130, 1450, 0)
(1131, 1130, 0)
(1131, 1132, 0)
(1131, 811, 0)
(1131, 1451, 0)
(1132, 1131, 0)
(1132, 1133, 0)
(1132, 812, 0)
(1132, 1452, 0)
(1133, 1132, 0)
(1133, 1134, 0)
(1133, 813, 0)
(1133, 1453, 0)
(1134, 1133, 0)
(1134, 1135, 0)
(1134, 814, 0)
(1134, 1454, 0)
(1135, 1134, 0)
(1135, 1136, 0)
(1135, 815, 0)
(1135, 1455, 0)
(1136, 1135, 0)
(1136, 1137, 0)
(1136, 816, 0)
(1136, 1456, 0)
(1137, 1136, 0)
(1137, 1138, 0)
(1137, 817, 0)
(1137, 1457, 0)
(1138, 1137, 0)
(1138, 1139, 0)
(1138, 818, 0)
(1138, 1458, 0)
(1139, 1138, 0)
(1139, 1140, 0)
(1139, 819, 0)
(1139, 1459, 0)
(1140, 1139, 0)
(1140, 1141, 0)
(1140, 820, 0)
(1140, 1460, 0)
(1141, 1140, 0)
(1141, 1142, 0)
(1141, 821, 0)
(1141, 1461, 0)
(1142, 1141, 0)
(1142, 1143, 0)
(1142, 822, 0)
(1142, 1462, 0)
(1143, 1142, 0)
(1143, 1144, 0)
(1143, 823, 0)
(1143, 1463, 0)
(1144, 1143, 0)
(1144, 1145, 0)
(1144, 824, 0)
(1144, 1464, 0)
(1145, 1144, 0)
(1145, 1146, 0)
(1145, 825, 0)
(1145, 1465, 0)
(1146, 1145, 0)
(1146, 1147, 0)
(1146, 826, 0)
(1146, 1466, 0)
(1147, 1146, 0)
(1147, 1148, 0)
(1147, 827, 0)
(1147, 1467, 0)
(1148, 1147, 0)
(1148, 1149, 0)
(1148, 828, 0)
(1148, 1468, 0)
(1149, 1148, 0)
(1149, 1150, 0)
(1149, 829, 0)
(1149, 1469, 0)
(1150, 1149, 0)
(1150, 1151, 0)
(1150, 830, 0)
(1150, 1470, 0)
(1151, 1150, 0)
(1151, 1152, 0)
(1151, 831, 0)
(1151, 1471, 0)
(1152, 1151, 0)
(1152, 1153, 0)
(1152, 832, 0)
(1152, 1472, 0)
(1153, 1152, 0)
(1153, 1154, 0)
(1153, 833, 0)
(1153, 1473, 0)
(1154, 1153, 0)
(1154, 1155, 0)
(1154, 834, 0)
(1154, 1474, 0)
(1155, 1154, 0)
(1155, 1156, 0)
(1155, 835, 0)
(1155, 1475, 0)
(1156, 1155, 0)
(1156, 1157, 0)
(1156, 836, 0)
(1156, 1476, 0)
(1157, 1156, 0)
(1157, 1158, 0)
(1157, 837, 0)
(1157, 1477, 0)
(1158, 1157, 0)
(1158, 1159, 0)
(1158, 838, 0)
(1158, 1478, 0)
(1159, 1158, 0)
(1159, 1160, 0)
(1159, 839, 0)
(1159, 1479, 0)
(1160, 1159, 0)
(1160, 1161, 0)
(1160, 840, 0)
(1160, 1480, 0)
(1161, 1160, 0)
(1161, 1162, 0)
(1161, 841, 0)
(1161, 1481, 0)
(1162, 1161, 0)
(1162, 1163, 0)
(1162, 842, 0)
(1162, 1482, 0)
(1163, 1162, 0)
(1163, 1164, 0)
(1163, 843, 0)
(1163, 1483, 0)
(1164, 1163, 0)
(1164, 1165, 0)
(1164, 844, 0)
(1164, 1484, 0)
(1165, 1164, 0)
(1165, 1166, 0)
(1165, 845, 0)
(1165, 1485, 0)
(1166, 1165, 0)
(1166, 1167, 0)
(1166, 846, 0)
(1166, 1486, 0)
(1167, 1166, 0)
(1167, 1168, 0)
(1167, 847, 0)
(1167, 1487, 0)
(1168, 1167, 0)
(1168, 1169, 0)
(1168, 848, 0)
(1168, 1488, 0)
(1169, 1168, 0)
(1169, 1170, 0)
(1169, 849, 0)
(1169, 1489, 0)
(1170, 1169, 0)
(1170, 1171, 0)
(1170, 850, 0)
(1170, 1490, 0)
(1171, 1170, 0)
(1171, 1172, 0)
(1171, 851, 0)
(1171, 1491, 0)
(1172, 1171, 0)
(1172, 1173, 0)
(1172, 852, 0)
(1172, 1492, 0)
(1173, 1172, 0)
(1173, 1174, 0)
(1173, 853, 0)
(1173, 1493, 0)
(1174, 1173, 0)
(1174, 1175, 0)
(1174, 854, 0)
(1174, 1494, 0)
(1175, 1174, 0)
(1175, 1176, 0)
(1175, 855, 0)
(1175, 1495, 0)
(1176, 1175, 0)
(1176, 1177, 0)
(1176, 856, 0)
(1176, 1496, 0)
(1177, 1176, 0)
(1177, 1178, 0)
(1177, 857, 0)
(1177, 1497, 0)
(1178, 1177, 0)
(1178, 1179, 0)
(1178, 858, 0)
(1178, 1498, 0)
(1179, 1178, 0)
(1179, 1180, 0)
(1179, 859, 0)
(1179, 1499, 0)
(1180, 1179, 0)
(1180, 1181, 0)
(1180, 860, 0)
(1180, 1500, 0)
(1181, 1180, 0)
(1181, 1182, 0)
(1181, 861, 0)
(1181, 1501, 0)
(1182, 1181, 0)
(1182, 1183, 0)
(1182, 862, 0)
(1182, 1502, 0)
(1183, 1182, 0)
(1183, 1184, 0)
(1183, 863, 0)
(1183, 1503, 0)
(1184, 1183, 0)
(1184, 1185, 0)
(1184, 864, 0)
(1184, 1504, 0)
(1185, 1184, 0)
(1185, 1186, 0)
(1185, 865, 0)
(1185, 1505, 0)
(1186, 1185, 0)
(1186, 1187, 0)
(1186, 866, 0)
(1186, 1506, 0)
(1187, 1186, 0)
(1187, 1188, 0)
(1187, 867, 0)
(1187, 1507, 0)
(1188, 1187, 0)
(1188, 1189, 0)
(1188, 868, 0)
(1188, 1508, 0)
(1189, 1188, 0)
(1189, 1190, 0)
(1189, 869, 0)
(1189, 1509, 0)
(1190, 1189, 0)
(1190, 1191, 0)
(1190, 870, 0)
(1190, 1510, 0)
(1191, 1190, 0)
(1191, 1192, 0)
(1191, 871, 0)
(1191, 1511, 0)
(1192, 1191, 0)
(1192, 1193, 0)
(1192, 872, 0)
(1192, 1512, 0)
(1193, 1192, 0)
(1193, 1194, 0)
(1193, 873, 0)
(1193, 1513, 0)
(1194, 1193, 0)
(1194, 1195, 0)
(1194, 874, 0)
(1194, 1514, 0)
(1195, 1194, 0)
(1195, 1196, 0)
(1195, 875, 0)
(1195, 1515, 0)
(1196, 1195, 0)
(1196, 1197, 0)
(1196, 876, 0)
(1196, 1516, 0)
(1197, 1196, 0)
(1197, 1198, 0)
(1197, 877, 0)
(1197, 1517, 0)
(1198, 1197, 0)
(1198, 1199, 0)
(1198, 878, 0)
(1198, 1518, 0)
(1199, 1198, 0)
(1199, 1200, 0)
(1199, 879, 0)
(1199, 1519, 0)
(1200, 1199, 0)
(1200, 1201, 0)
(1200, 880, 0)
(1200, 1520, 0)
(1201, 1200, 0)
(1201, 1202, 0)
(1201, 881, 0)
(1201, 1521, 0)
(1202, 1201, 0)
(1202, 1203, 0)
(1202, 882, 0)
(1202, 1522, 0)
(1203, 1202, 0)
(1203, 1204, 0)
(1203, 883, 0)
(1203, 1523, 0)
(1204, 1203, 0)
(1204, 1205, 0)
(1204, 884, 0)
(1204, 1524, 0)
(1205, 1204, 0)
(1205, 1206, 0)
(1205, 885, 0)
(1205, 1525, 0)
(1206, 1205, 0)
(1206, 1207, 0)
(1206, 886, 0)
(1206, 1526, 0)
(1207, 1206, 0)
(1207, 1208, 0)
(1207, 887, 0)
(1207, 1527, 0)
(1208, 1207, 0)
(1208, 1209, 0)
(1208, 888, 0)
(1208, 1528, 0)
(1209, 1208, 0)
(1209, 1210, 0)
(1209, 889, 0)
(1209, 1529, 0)
(1210, 1209, 0)
(1210, 1211, 0)
(1210, 890, 0)
(1210, 1530, 0)
(1211, 1210, 0)
(1211, 1212, 0)
(1211, 891, 0)
(1211, 1531, 0)
(1212, 1211, 0)
(1212, 1213, 0)
(1212, 892, 0)
(1212, 1532, 0)
(1213, 1212, 0)
(1213, 1214, 0)
(1213, 893, 0)
(1213, 1533, 0)
(1214, 1213, 0)
(1214, 1215, 0)
(1214, 894, 0)
(1214, 1534, 0)
(1215, 1214, 0)
(1215, 1216, 0)
(1215, 895, 0)
(1215, 1535, 0)
(1216, 1215, 0)
(1216, 1217, 0)
(1216, 896, 0)
(1216, 1536, 0)
(1217, 1216, 0)
(1217, 1218, 0)
(1217, 897, 0)
(1217, 1537, 0)
(1218, 1217, 0)
(1218, 1219, 0)
(1218, 898, 0)
(1218, 1538, 0)
(1219, 1218, 0)
(1219, 1220, 0)
(1219, 899, 0)
(1219, 1539, 0)
(1220, 1219, 0)
(1220, 1221, 0)
(1220, 900, 0)
(1220, 1540, 0)
(1221, 1220, 0)
(1221, 1222, 0)
(1221, 901, 0)
(1221, 1541, 0)
(1222, 1221, 0)
(1222, 1223, 0)
(1222, 902, 0)
(1222, 1542, 0)
(1223, 1222, 0)
(1223, 1224, 0)
(1223, 903, 0)
(1223, 1543, 0)
(1224, 1223, 0)
(1224, 1225, 0)
(1224, 904, 0)
(1224, 1544, 0)
(1225, 1224, 0)
(1225, 1226, 0)
(1225, 905, 0)
(1225, 1545, 0)
(1226, 1225, 0)
(1226, 1227, 0)
(1226, 906, 0)
(1226, 1546, 0)
(1227, 1226, 0)
(1227, 1228, 0)
(1227, 907, 0)
(1227, 1547, 0)
(1228, 1227, 0)
(1228, 1229, 0)
(1228, 908, 0)
(1228, 1548, 0)
(1229, 1228, 0)
(1229, 1230, 0)
(1229, 909, 0)
(1229, 1549, 0)
(1230, 1229, 0)
(1230, 1231, 0)
(1230, 910, 0)
(1230, 1550, 0)
(1231, 1230, 0)
(1231, 1232, 0)
(1231, 911, 0)
(1231, 1551, 0)
(1232, 1231, 0)
(1232, 1233, 0)
(1232, 912, 0)
(1232, 1552, 0)
(1233, 1232, 0)
(1233, 1234, 0)
(1233, 913, 0)
(1233, 1553, 0)
(1234, 1233, 0)
(1234, 1235, 0)
(1234, 914, 0)
(1234, 1554, 0)
(1235, 1234, 0)
(1235, 1236, 0)
(1235, 915, 0)
(1235, 1555, 0)
(1236, 1235, 0)
(1236, 1237, 0)
(1236, 916, 0)
(1236, 1556, 0)
(1237, 1236, 0)
(1237, 1238, 0)
(1237, 917, 0)
(1237, 1557, 0)
(1238, 1237, 0)
(1238, 1239, 0)
(1238, 918, 0)
(1238, 1558, 0)
(1239, 1238, 0)
(1239, 1240, 0)
(1239, 919, 0)
(1239, 1559, 0)
(1240, 1239, 0)
(1240, 1241, 0)
(1240, 920, 0)
(1240, 1560, 0)
(1241, 1240, 0)
(1241, 1242, 0)
(1241, 921, 0)
(1241, 1561, 0)
(1242, 1241, 0)
(1242, 1243, 0)
(1242, 922, 0)
(1242, 1562, 0)
(1243, 1242, 0)
(1243, 1244, 0)
(1243, 923, 0)
(1243, 1563, 0)
(1244, 1243, 0)
(1244, 1245, 0)
(1244, 924, 0)
(1244, 1564, 0)
(1245, 1244, 0)
(1245, 1246, 0)
(1245, 925, 0)
(1245, 1565, 0)
(1246, 1245, 0)
(1246, 1247, 0)
(1246, 926, 0)
(1246, 1566, 0)
(1247, 1246, 0)
(1247, 1248, 0)
(1247, 927, 0)
(1247, 1567, 0)
(1248, 1247, 0)
(1248, 1249, 0)
(1248, 928, 0)
(1248, 1568, 0)
(1249, 1248, 0)
(1249, 1250, 0)
(1249, 929, 0)
(1249, 1569, 0)
(1250, 1249, 0)
(1250, 1251, 0)
(1250, 930, 0)
(1250, 1570, 0)
(1251, 1250, 0)
(1251, 1252, 0)
(1251, 931, 0)
(1251, 1571, 0)
(1252, 1251, 0)
(1252, 1253, 0)
(1252, 932, 0)
(1252, 1572, 0)
(1253, 1252, 0)
(1253, 1254, 0)
(1253, 933, 0)
(1253, 1573, 0)
(1254, 1253, 0)
(1254, 1255, 0)
(1254, 934, 0)
(1254, 1574, 0)
(1255, 1254, 0)
(1255, 1256, 0)
(1255, 935, 0)
(1255, 1575, 0)
(1256, 1255, 0)
(1256, 1257, 0)
(1256, 936, 0)
(1256, 1576, 0)
(1257, 1256, 0)
(1257, 1258, 0)
(1257, 937, 0)
(1257, 1577, 0)
(1258, 1257, 0)
(1258, 1259, 0)
(1258, 938, 0)
(1258, 1578, 0)
(1259, 1258, 0)
(1259, 1260, 0)
(1259, 939, 0)
(1259, 1579, 0)
(1260, 1259, 0)
(1260, 1261, 0)
(1260, 940, 0)
(1260, 1580, 0)
(1261, 1260, 0)
(1261, 1262, 0)
(1261, 941, 0)
(1261, 1581, 0)
(1262, 1261, 0)
(1262, 1263, 0)
(1262, 942, 0)
(1262, 1582, 0)
(1263, 1262, 0)
(1263, 1264, 0)
(1263, 943, 0)
(1263, 1583, 0)
(1264, 1263, 0)
(1264, 1265, 0)
(1264, 944, 0)
(1264, 1584, 0)
(1265, 1264, 0)
(1265, 1266, 0)
(1265, 945, 0)
(1265, 1585, 0)
(1266, 1265, 0)
(1266, 1267, 0)
(1266, 946, 0)
(1266, 1586, 0)
(1267, 1266, 0)
(1267, 1268, 0)
(1267, 947, 0)
(1267, 1587, 0)
(1268, 1267, 0)
(1268, 1269, 0)
(1268, 948, 0)
(1268, 1588, 0)
(1269, 1268, 0)
(1269, 1270, 0)
(1269, 949, 0)
(1269, 1589, 0)
(1270, 1269, 0)
(1270, 1271, 0)
(1270, 950, 0)
(1270, 1590, 0)
(1271, 1270, 0)
(1271, 1272, 0)
(1271, 951, 0)
(1271, 1591, 0)
(1272, 1271, 0)
(1272, 1273, 0)
(1272, 952, 0)
(1272, 1592, 0)
(1273, 1272, 0)
(1273, 1274, 0)
(1273, 953, 0)
(1273, 1593, 0)
(1274, 1273, 0)
(1274, 1275, 0)
(1274, 954, 0)
(1274, 1594, 0)
(1275, 1274, 0)
(1275, 1276, 0)
(1275, 955, 0)
(1275, 1595, 0)
(1276, 1275, 0)
(1276, 1277, 0)
(1276, 956, 0)
(1276, 1596, 0)
(1277, 1276, 0)
(1277, 1278, 0)
(1277, 957, 0)
(1277, 1597, 0)
(1278, 1277, 0)
(1278, 1279, 0)
(1278, 958, 0)
(1278, 1598, 0)
(1279, 1278, 0)
(1279, 959, 0)
(1279, 1599, 0)
(1280, 1281, 0)
(1280, 960, 0)
(1280, 1600, 0)
(1281, 1280, 0)
(1281, 1282, 0)
(1281, 961, 0)
(1281, 1601, 0)
(1282, 1281, 0)
(1282, 1283, 0)
(1282, 962, 0)
(1282, 1602, 0)
(1283, 1282, 0)
(1283, 1284, 0)
(1283, 963, 0)
(1283, 1603, 0)
(1284, 1283, 0)
(1284, 1285, 0)
(1284, 964, 0)
(1284, 1604, 0)
(1285, 1284, 0)
(1285, 1286, 0)
(1285, 965, 0)
(1285, 1605, 0)
(1286, 1285, 0)
(1286, 1287, 0)
(1286, 966, 0)
(1286, 1606, 0)
(1287, 1286, 0)
(1287, 1288, 0)
(1287, 967, 0)
(1287, 1607, 0)
(1288, 1287, 0)
(1288, 1289, 0)
(1288, 968, 0)
(1288, 1608, 0)
(1289, 1288, 0)
(1289, 1290, 0)
(1289, 969, 0)
(1289, 1609, 0)
(1290, 1289, 0)
(1290, 1291, 0)
(1290, 970, 0)
(1290, 1610, 0)
(1291, 1290, 0)
(1291, 1292, 0)
(1291, 971, 0)
(1291, 1611, 0)
(1292, 1291, 0)
(1292, 1293, 0)
(1292, 972, 0)
(1292, 1612, 0)
(1293, 1292, 0)
(1293, 1294, 0)
(1293, 973, 0)
(1293, 1613, 0)
(1294, 1293, 0)
(1294, 1295, 0)
(1294, 974, 0)
(1294, 1614, 0)
(1295, 1294, 0)
(1295, 975, 0)
(1296, 1297, 0)
(1297, 1296, 0)
(1298, 1299, 0)
(1298, 978, 0)
(1299, 1298, 0)
(1299, 1300, 0)
(1299, 979, 0)
(1299, 1619, 0)
(1300, 1299, 0)
(1300, 1301, 0)
(1300, 980, 0)
(1300, 1620, 0)
(1301, 1300, 0)
(1301, 1302, 0)
(1301, 981, 0)
(1301, 1621, 0)
(1302, 1301, 0)
(1302, 1303, 0)
(1302, 982, 0)
(1302, 1622, 0)
(1303, 1302, 0)
(1303, 1304, 0)
(1303, 983, 0)
(1303, 1623, 0)
(1304, 1303, 0)
(1304, 1305, 0)
(1304, 984, 0)
(1304, 1624, 0)
(1305, 1304, 0)
(1305, 1306, 0)
(1305, 985, 0)
(1305, 1625, 0)
(1306, 1305, 0)
(1306, 1307, 0)
(1306, 986, 0)
(1306, 1626, 0)
(1307, 1306, 0)
(1307, 1308, 0)
(1307, 987, 0)
(1307, 1627, 0)
(1308, 1307, 0)
(1308, 1309, 0)
(1308, 988, 0)
(1308, 1628, 0)
(1309, 1308, 0)
(1309, 1310, 0)
(1309, 989, 0)
(1309, 1629, 0)
(1310, 1309, 0)
(1310, 1311, 0)
(1310, 990, 0)
(1310, 1630, 0)
(1311, 1310, 0)
(1311, 1312, 0)
(1311, 991, 0)
(1311, 1631, 0)
(1312, 1311, 0)
(1312, 1313, 0)
(1312, 992, 0)
(1312, 1632, 0)
(1313, 1312, 0)
(1313, 1314, 0)
(1313, 993, 0)
(1313, 1633, 0)
(1314, 1313, 0)
(1314, 1315, 0)
(1314, 994, 0)
(1314, 1634, 0)
(1315, 1314, 0)
(1315, 1316, 0)
(1315, 995, 0)
(1315, 1635, 0)
(1316, 1315, 0)
(1316, 1317, 0)
(1316, 996, 0)
(1316, 1636, 0)
(1317, 1316, 0)
(1317, 1318, 0)
(1317, 997, 0)
(1317, 1637, 0)
(1318, 1317, 0)
(1318, 1319, 0)
(1318, 998, 0)
(1318, 1638, 0)
(1319, 1318, 0)
(1319, 1320, 0)
(1319, 999, 0)
(1319, 1639, 0)
(1320, 1319, 0)
(1320, 1321, 0)
(1320, 1000, 0)
(1320, 1640, 0)
(1321, 1320, 0)
(1321, 1322, 0)
(1321, 1001, 0)
(1321, 1641, 0)
(1322, 1321, 0)
(1322, 1323, 0)
(1322, 1002, 0)
(1322, 1642, 0)
(1323, 1322, 0)
(1323, 1324, 0)
(1323, 1003, 0)
(1323, 1643, 0)
(1324, 1323, 0)
(1324, 1325, 0)
(1324, 1004, 0)
(1324, 1644, 0)
(1325, 1324, 0)
(1325, 1326, 0)
(1325, 1005, 0)
(1325, 1645, 0)
(1326, 1325, 0)
(1326, 1327, 0)
(1326, 1006, 0)
(1326, 1646, 0)
(1327, 1326, 0)
(1327, 1328, 0)
(1327, 1007, 0)
(1327, 1647, 0)
(1328, 1327, 0)
(1328, 1329, 0)
(1328, 1008, 0)
(1328, 1648, 0)
(1329, 1328, 0)
(1329, 1330, 0)
(1329, 1009, 0)
(1329, 1649, 0)
(1330, 1329, 0)
(1330, 1331, 0)
(1330, 1010, 0)
(1330, 1650, 0)
(1331, 1330, 0)
(1331, 1332, 0)
(1331, 1011, 0)
(1331, 1651, 0)
(1332, 1331, 0)
(1332, 1333, 0)
(1332, 1012, 0)
(1332, 1652, 0)
(1333, 1332, 0)
(1333, 1334, 0)
(1333, 1013, 0)
(1333, 1653, 0)
(1334, 1333, 0)
(1334, 1335, 0)
(1334, 1014, 0)
(1334, 1654, 0)
(1335, 1334, 0)
(1335, 1336, 0)
(1335, 1015, 0)
(1335, 1655, 0)
(1336, 1335, 0)
(1336, 1337, 0)
(1336, 1016, 0)
(1336, 1656, 0)
(1337, 1336, 0)
(1337, 1338, 0)
(1337, 1017, 0)
(1337, 1657, 0)
(1338, 1337, 0)
(1338, 1339, 0)
(1338, 1018, 0)
(1338, 1658, 0)
(1339, 1338, 0)
(1339, 1340, 0)
(1339, 1019, 0)
(1339, 1659, 0)
(1340, 1339, 0)
(1340, 1341, 0)
(1340, 1020, 0)
(1340, 1660, 0)
(1341, 1340, 0)
(1341, 1342, 0)
(1341, 1021, 0)
(1341, 1661, 0)
(1342, 1341, 0)
(1342, 1343, 0)
(1342, 1022, 0)
(1342, 1662, 0)
(1343, 1342, 0)
(1343, 1344, 0)
(1343, 1023, 0)
(1343, 1663, 0)
(1344, 1343, 0)
(1344, 1345, 0)
(1344, 1024, 0)
(1344, 1664, 0)
(1345, 1344, 0)
(1345, 1346, 0)
(1345, 1025, 0)
(1345, 1665, 0)
(1346, 1345, 0)
(1346, 1347, 0)
(1346, 1026, 0)
(1346, 1666, 0)
(1347, 1346, 0)
(1347, 1348, 0)
(1347, 1027, 0)
(1347, 1667, 0)
(1348, 1347, 0)
(1348, 1349, 0)
(1348, 1028, 0)
(1348, 1668, 0)
(1349, 1348, 0)
(1349, 1350, 0)
(1349, 1029, 0)
(1349, 1669, 0)
(1350, 1349, 0)
(1350, 1351, 0)
(1350, 1030, 0)
(1350, 1670, 0)
(1351, 1350, 0)
(1351, 1352, 0)
(1351, 1031, 0)
(1351, 1671, 0)
(1352, 1351, 0)
(1352, 1353, 0)
(1352, 1032, 0)
(1352, 1672, 0)
(1353, 1352, 0)
(1353, 1354, 0)
(1353, 1033, 0)
(1353, 1673, 0)
(1354, 1353, 0)
(1354, 1355, 0)
(1354, 1034, 0)
(1354, 1674, 0)
(1355, 1354, 0)
(1355, 1356, 0)
(1355, 1035, 0)
(1355, 1675, 0)
(1356, 1355, 0)
(1356, 1357, 0)
(1356, 1036, 0)
(1356, 1676, 0)
(1357, 1356, 0)
(1357, 1358, 0)
(1357, 1037, 0)
(1357, 1677, 0)
(1358, 1357, 0)
(1358, 1359, 0)
(1358, 1038, 0)
(1358, 1678, 0)
(1359, 1358, 0)
(1359, 1360, 0)
(1359, 1039, 0)
(1359, 1679, 0)
(1360, 1359, 0)
(1360, 1361, 0)
(1360, 1040, 0)
(1360, 1680, 0)
(1361, 1360, 0)
(1361, 1362, 0)
(1361, 1041, 0)
(1361, 1681, 0)
(1362, 1361, 0)
(1362, 1363, 0)
(1362, 1042, 0)
(1362, 1682, 0)
(1363, 1362, 0)
(1363, 1364, 0)
(1363, 1043, 0)
(1363, 1683, 0)
(1364, 1363, 0)
(1364, 1365, 0)
(1364, 1044, 0)
(1364, 1684, 0)
(1365, 1364, 0)
(1365, 1366, 0)
(1365, 1045, 0)
(1365, 1685, 0)
(1366, 1365, 0)
(1366, 1367, 0)
(1366, 1046, 0)
(1366, 1686, 0)
(1367, 1366, 0)
(1367, 1368, 0)
(1367, 1047, 0)
(1367, 1687, 0)
(1368, 1367, 0)
(1368, 1369, 0)
(1368, 1048, 0)
(1368, 1688, 0)
(1369, 1368, 0)
(1369, 1370, 0)
(1369, 1049, 0)
(1369, 1689, 0)
(1370, 1369, 0)
(1370, 1371, 0)
(1370, 1050, 0)
(1370, 1690, 0)
(1371, 1370, 0)
(1371, 1372, 0)
(1371, 1051, 0)
(1371, 1691, 0)
(1372, 1371, 0)
(1372, 1373, 0)
(1372, 1052, 0)
(1372, 1692, 0)
(1373, 1372, 0)
(1373, 1374, 0)
(1373, 1053, 0)
(1373, 1693, 0)
(1374, 1373, 0)
(1374, 1375, 0)
(1374, 1054, 0)
(1374, 1694, 0)
(1375, 1374, 0)
(1375, 1376, 0)
(1375, 1055, 0)
(1375, 1695, 0)
(1376, 1375, 0)
(1376, 1377, 0)
(1376, 1056, 0)
(1376, 1696, 0)
(1377, 1376, 0)
(1377, 1378, 0)
(1377, 1057, 0)
(1377, 1697, 0)
(1378, 1377, 0)
(1378, 1379, 0)
(1378, 1058, 0)
(1378, 1698, 0)
(1379, 1378, 0)
(1379, 1380, 0)
(1379, 1059, 0)
(1379, 1699, 0)
(1380, 1379, 0)
(1380, 1381, 0)
(1380, 1060, 0)
(1380, 1700, 0)
(1381, 1380, 0)
(1381, 1382, 0)
(1381, 1061, 0)
(1381, 1701, 0)
(1382, 1381, 0)
(1382, 1383, 0)
(1382, 1062, 0)
(1382, 1702, 0)
(1383, 1382, 0)
(1383, 1384, 0)
(1383, 1063, 0)
(1383, 1703, 0)
(1384, 1383, 0)
(1384, 1385, 0)
(1384, 1064, 0)
(1384, 1704, 0)
(1385, 1384, 0)
(1385, 1386, 0)
(1385, 1065, 0)
(1385, 1705, 0)
(1386, 1385, 0)
(1386, 1387, 0)
(1386, 1066, 0)
(1386, 1706, 0)
(1387, 1386, 0)
(1387, 1388, 0)
(1387, 1067, 0)
(1387, 1707, 0)
(1388, 1387, 0)
(1388, 1389, 0)
(1388, 1068, 0)
(1388, 1708, 0)
(1389, 1388, 0)
(1389, 1390, 0)
(1389, 1069, 0)
(1389, 1709, 0)
(1390, 1389, 0)
(1390, 1391, 0)
(1390, 1070, 0)
(1390, 1710, 0)
(1391, 1390, 0)
(1391, 1392, 0)
(1391, 1071, 0)
(1391, 1711, 0)
(1392, 1391, 0)
(1392, 1393, 0)
(1392, 1072, 0)
(1392, 1712, 0)
(1393, 1392, 0)
(1393, 1394, 0)
(1393, 1073, 0)
(1393, 1713, 0)
(1394, 1393, 0)
(1394, 1395, 0)
(1394, 1074, 0)
(1394, 1714, 0)
(1395, 1394, 0)
(1395, 1396, 0)
(1395, 1075, 0)
(1395, 1715, 0)
(1396, 1395, 0)
(1396, 1397, 0)
(1396, 1076, 0)
(1396, 1716, 0)
(1397, 1396, 0)
(1397, 1398, 0)
(1397, 1077, 0)
(1397, 1717, 0)
(1398, 1397, 0)
(1398, 1399, 0)
(1398, 1078, 0)
(1398, 1718, 0)
(1399, 1398, 0)
(1399, 1400, 0)
(1399, 1079, 0)
(1399, 1719, 0)
(1400, 1399, 0)
(1400, 1401, 0)
(1400, 1080, 0)
(1400, 1720, 0)
(1401, 1400, 0)
(1401, 1402, 0)
(1401, 1081, 0)
(1401, 1721, 0)
(1402, 1401, 0)
(1402, 1403, 0)
(1402, 1082, 0)
(1402, 1722, 0)
(1403, 1402, 0)
(1403, 1404, 0)
(1403, 1083, 0)
(1403, 1723, 0)
(1404, 1403, 0)
(1404, 1405, 0)
(1404, 1084, 0)
(1404, 1724, 0)
(1405, 1404, 0)
(1405, 1406, 0)
(1405, 1085, 0)
(1405, 1725, 0)
(1406, 1405, 0)
(1406, 1407, 0)
(1406, 1086, 0)
(1406, 1726, 0)
(1407, 1406, 0)
(1407, 1408, 0)
(1407, 1087, 0)
(1407, 1727, 0)
(1408, 1407, 0)
(1408, 1409, 0)
(1408, 1088, 0)
(1408, 1728, 0)
(1409, 1408, 0)
(1409, 1410, 0)
(1409, 1089, 0)
(1409, 1729, 0)
(1410, 1409, 0)
(1410, 1411, 0)
(1410, 1090, 0)
(1410, 1730, 0)
(1411, 1410, 0)
(1411, 1412, 0)
(1411, 1091, 0)
(1411, 1731, 0)
(1412, 1411, 0)
(1412, 1413, 0)
(1412, 1092, 0)
(1412, 1732, 0)
(1413, 1412, 0)
(1413, 1414, 0)
(1413, 1093, 0)
(1413, 1733, 0)
(1414, 1413, 0)
(1414, 1415, 0)
(1414, 1094, 0)
(1414, 1734, 0)
(1415, 1414, 0)
(1415, 1416, 0)
(1415, 1095, 0)
(1415, 1735, 0)
(1416, 1415, 0)
(1416, 1417, 0)
(1416, 1096, 0)
(1416, 1736, 0)
(1417, 1416, 0)
(1417, 1418, 0)
(1417, 1097, 0)
(1417, 1737, 0)
(1418, 1417, 0)
(1418, 1419, 0)
(1418, 1098, 0)
(1418, 1738, 0)
(1419, 1418, 0)
(1419, 1420, 0)
(1419, 1099, 0)
(1419, 1739, 0)
(1420, 1419, 0)
(1420, 1421, 0)
(1420, 1100, 0)
(1420, 1740, 0)
(1421, 1420, 0)
(1421, 1422, 0)
(1421, 1101, 0)
(1421, 1741, 0)
(1422, 1421, 0)
(1422, 1423, 0)
(1422, 1102, 0)
(1422, 1742, 0)
(1423, 1422, 0)
(1423, 1424, 0)
(1423, 1103, 0)
(1423, 1743, 0)
(1424, 1423, 0)
(1424, 1425, 0)
(1424, 1104, 0)
(1424, 1744, 0)
(1425, 1424, 0)
(1425, 1426, 0)
(1425, 1105, 0)
(1425, 1745, 0)
(1426, 1425, 0)
(1426, 1427, 0)
(1426, 1106, 0)
(1426, 1746, 0)
(1427, 1426, 0)
(1427, 1428, 0)
(1427, 1107, 0)
(1427, 1747, 0)
(1428, 1427, 0)
(1428, 1429, 0)
(1428, 1108, 0)
(1428, 1748, 0)
(1429, 1428, 0)
(1429, 1430, 0)
(1429, 1109, 0)
(1429, 1749, 0)
(1430, 1429, 0)
(1430, 1431, 0)
(1430, 1110, 0)
(1430, 1750, 0)
(1431, 1430, 0)
(1431, 1432, 0)
(1431, 1111, 0)
(1431, 1751, 0)
(1432, 1431, 0)
(1432, 1433, 0)
(1432, 1112, 0)
(1432, 1752, 0)
(1433, 1432, 0)
(1433, 1434, 0)
(1433, 1113, 0)
(1433, 1753, 0)
(1434, 1433, 0)
(1434, 1435, 0)
(1434, 1114, 0)
(1434, 1754, 0)
(1435, 1434, 0)
(1435, 1436, 0)
(1435, 1115, 0)
(1435, 1755, 0)
(1436, 1435, 0)
(1436, 1437, 0)
(1436, 1116, 0)
(1436, 1756, 0)
(1437, 1436, 0)
(1437, 1438, 0)
(1437, 1117, 0)
(1437, 1757, 0)
(1438, 1437, 0)
(1438, 1439, 0)
(1438, 1118, 0)
(1438, 1758, 0)
(1439, 1438, 0)
(1439, 1440, 0)
(1439, 1119, 0)
(1439, 1759, 0)
(1440, 1439, 0)
(1440, 1441, 0)
(1440, 1120, 0)
(1440, 1760, 0)
(1441, 1440, 0)
(1441, 1442, 0)
(1441, 1121, 0)
(1441, 1761, 0)
(1442, 1441, 0)
(1442, 1443, 0)
(1442, 1122, 0)
(1442, 1762, 0)
(1443, 1442, 0)
(1443, 1444, 0)
(1443, 1123, 0)
(1443, 1763, 0)
(1444, 1443, 0)
(1444, 1445, 0)
(1444, 1124, 0)
(1444, 1764, 0)
(1445, 1444, 0)
(1445, 1446, 0)
(1445, 1125, 0)
(1445, 1765, 0)
(1446, 1445, 0)
(1446, 1447, 0)
(1446, 1126, 0)
(1446, 1766, 0)
(1447, 1446, 0)
(1447, 1448, 0)
(1447, 1127, 0)
(1447, 1767, 0)
(1448, 1447, 0)
(1448, 1449, 0)
(1448, 1128, 0)
(1448, 1768, 0)
(1449, 1448, 0)
(1449, 1450, 0)
(1449, 1129, 0)
(1449, 1769, 0)
(1450, 1449, 0)
(1450, 1451, 0)
(1450, 1130, 0)
(1450, 1770, 0)
(1451, 1450, 0)
(1451, 1452, 0)
(1451, 1131, 0)
(1451, 1771, 0)
(1452, 1451, 0)
(1452, 1453, 0)
(1452, 1132, 0)
(1452, 1772, 0)
(1453, 1452, 0)
(1453, 1454, 0)
(1453, 1133, 0)
(1453, 1773, 0)
(1454, 1453, 0)
(1454, 1455, 0)
(1454, 1134, 0)
(1454, 1774, 0)
(1455, 1454, 0)
(1455, 1456, 0)
(1455, 1135, 0)
(1455, 1775, 0)
(1456, 1455, 0)
(1456, 1457, 0)
(1456, 1136, 0)
(1456, 1776, 0)
(1457, 1456, 0)
(1457, 1458, 0)
(1457, 1137, 0)
(1457, 1777, 0)
(1458, 1457, 0)
(1458, 1459, 0)
(1458, 1138, 0)
(1458, 1778, 0)
(1459, 1458, 0)
(1459, 1460, 0)
(1459, 1139, 0)
(1459, 1779, 0)
(1460, 1459, 0)
(1460, 1461, 0)
(1460, 1140, 0)
(1460, 1780, 0)
(1461, 1460, 0)
(1461, 1462, 0)
(1461, 1141, 0)
(1461, 1781, 0)
(1462, 1461, 0)
(1462, 1463, 0)
(1462, 1142, 0)
(1462, 1782, 0)
(1463, 1462, 0)
(1463, 1464, 0)
(1463, 1143, 0)
(1463, 1783, 0)
(1464, 1463, 0)
(1464, 1465, 0)
(1464, 1144, 0)
(1464, 1784, 0)
(1465, 1464, 0)
(1465, 1466, 0)
(1465, 1145, 0)
(1465, 1785, 0)
(1466, 1465, 0)
(1466, 1467, 0)
(1466, 1146, 0)
(1466, 1786, 0)
(1467, 1466, 0)
(1467, 1468, 0)
(1467, 1147, 0)
(1467, 1787, 0)
(1468, 1467, 0)
(1468, 1469, 0)
(1468, 1148, 0)
(1468, 1788, 0)
(1469, 1468, 0)
(1469, 1470, 0)
(1469, 1149, 0)
(1469, 1789, 0)
(1470, 1469, 0)
(1470, 1471, 0)
(1470, 1150, 0)
(1470, 1790, 0)
(1471, 1470, 0)
(1471, 1472, 0)
(1471, 1151, 0)
(1471, 1791, 0)
(1472, 1471, 0)
(1472, 1473, 0)
(1472, 1152, 0)
(1472, 1792, 0)
(1473, 1472, 0)
(1473, 1474, 0)
(1473, 1153, 0)
(1473, 1793, 0)
(1474, 1473, 0)
(1474, 1475, 0)
(1474, 1154, 0)
(1474, 1794, 0)
(1475, 1474, 0)
(1475, 1476, 0)
(1475, 1155, 0)
(1475, 1795, 0)
(1476, 1475, 0)
(1476, 1477, 0)
(1476, 1156, 0)
(1476, 1796, 0)
(1477, 1476, 0)
(1477, 1478, 0)
(1477, 1157, 0)
(1477, 1797, 0)
(1478, 1477, 0)
(1478, 1479, 0)
(1478, 1158, 0)
(1478, 1798, 0)
(1479, 1478, 0)
(1479, 1480, 0)
(1479, 1159, 0)
(1479, 1799, 0)
(1480, 1479, 0)
(1480, 1481, 0)
(1480, 1160, 0)
(1480, 1800, 0)
(1481, 1480, 0)
(1481, 1482, 0)
(1481, 1161, 0)
(1481, 1801, 0)
(1482, 1481, 0)
(1482, 1483, 0)
(1482, 1162, 0)
(1482, 1802, 0)
(1483, 1482, 0)
(1483, 1484, 0)
(1483, 1163, 0)
(1483, 1803, 0)
(1484, 1483, 0)
(1484, 1485, 0)
(1484, 1164, 0)
(1484, 1804, 0)
(1485, 1484, 0)
(1485, 1486, 0)
(1485, 1165, 0)
(1485, 1805, 0)
(1486, 1485, 0)
(1486, 1487, 0)
(1486, 1166, 0)
(1486, 1806, 0)
(1487, 1486, 0)
(1487, 1488, 0)
(1487, 1167, 0)
(1487, 1807, 0)
(1488, 1487, 0)
(1488, 1489, 0)
(1488, 1168, 0)
(1488, 1808, 0)
(1489, 1488, 0)
(1489, 1490, 0)
(1489, 1169, 0)
(1489, 1809, 0)
(1490, 1489, 0)
(1490, 1491, 0)
(1490, 1170, 0)
(1490, 1810, 0)
(1491, 1490, 0)
(1491, 1492, 0)
(1491, 1171, 0)
(1491, 1811, 0)
(1492, 1491, 0)
(1492, 1493, 0)
(1492, 1172, 0)
(1492, 1812, 0)
(1493, 1492, 0)
(1493, 1494, 0)
(1493, 1173, 0)
(1493, 1813, 0)
(1494, 1493, 0)
(1494, 1495, 0)
(1494, 1174, 0)
(1494, 1814, 0)
(1495, 1494, 0)
(1495, 1496, 0)
(1495, 1175, 0)
(1495, 1815, 0)
(1496, 1495, 0)
(1496, 1497, 0)
(1496, 1176, 0)
(1496, 1816, 0)
(1497, 1496, 0)
(1497, 1498, 0)
(1497, 1177, 0)
(1497, 1817, 0)
(1498, 1497, 0)
(1498, 1499, 0)
(1498, 1178, 0)
(1498, 1818, 0)
(1499, 1498, 0)
(1499, 1500, 0)
(1499, 1179, 0)
(1499, 1819, 0)
(1500, 1499, 0)
(1500, 1501, 0)
(1500, 1180, 0)
(1500, 1820, 0)
(1501, 1500, 0)
(1501, 1502, 0)
(1501, 1181, 0)
(1501, 1821, 0)
(1502, 1501, 0)
(1502, 1503, 0)
(1502, 1182, 0)
(1502, 1822, 0)
(1503, 1502, 0)
(1503, 1504, 0)
(1503, 1183, 0)
(1503, 1823, 0)
(1504, 1503, 0)
(1504, 1505, 0)
(1504, 1184, 0)
(1504, 1824, 0)
(1505, 1504, 0)
(1505, 1506, 0)
(1505, 1185, 0)
(1505, 1825, 0)
(1506, 1505, 0)
(1506, 1507, 0)
(1506, 1186, 0)
(1506, 1826, 0)
(1507, 1506, 0)
(1507, 1508, 0)
(1507, 1187, 0)
(1507, 1827, 0)
(1508, 1507, 0)
(1508, 1509, 0)
(1508, 1188, 0)
(1508, 1828, 0)
(1509, 1508, 0)
(1509, 1510, 0)
(1509, 1189, 0)
(1509, 1829, 0)
(1510, 1509, 0)
(1510, 1511, 0)
(1510, 1190, 0)
(1510, 1830, 0)
(1511, 1510, 0)
(1511, 1512, 0)
(1511, 1191, 0)
(1511, 1831, 0)
(1512, 1511, 0)
(1512, 1513, 0)
(1512, 1192, 0)
(1512, 1832, 0)
(1513, 1512, 0)
(1513, 1514, 0)
(1513, 1193, 0)
(1513, 1833, 0)
(1514, 1513, 0)
(1514, 1515, 0)
(1514, 1194, 0)
(1514, 1834, 0)
(1515, 1514, 0)
(1515, 1516, 0)
(1515, 1195, 0)
(1515, 1835, 0)
(1516, 1515, 0)
(1516, 1517, 0)
(1516, 1196, 0)
(1516, 1836, 0)
(1517, 1516, 0)
(1517, 1518, 0)
(1517, 1197, 0)
(1517, 1837, 0)
(1518, 1517, 0)
(1518, 1519, 0)
(1518, 1198, 0)
(1518, 1838, 0)
(1519, 1518, 0)
(1519, 1520, 0)
(1519, 1199, 0)
(1519, 1839, 0)
(1520, 1519, 0)
(1520, 1521, 0)
(1520, 1200, 0)
(1520, 1840, 0)
(1521, 1520, 0)
(1521, 1522, 0)
(1521, 1201, 0)
(1521, 1841, 0)
(1522, 1521, 0)
(1522, 1523, 0)
(1522, 1202, 0)
(1522, 1842, 0)
(1523, 1522, 0)
(1523, 1524, 0)
(1523, 1203, 0)
(1523, 1843, 0)
(1524, 1523, 0)
(1524, 1525, 0)
(1524, 1204, 0)
(1524, 1844, 0)
(1525, 1524, 0)
(1525, 1526, 0)
(1525, 1205, 0)
(1525, 1845, 0)
(1526, 1525, 0)
(1526, 1527, 0)
(1526, 1206, 0)
(1526, 1846, 0)
(1527, 1526, 0)
(1527, 1528, 0)
(1527, 1207, 0)
(1527, 1847, 0)
(1528, 1527, 0)
(1528, 1529, 0)
(1528, 1208, 0)
(1528, 1848, 0)
(1529, 1528, 0)
(1529, 1530, 0)
(1529, 1209, 0)
(1529, 1849, 0)
(1530, 1529, 0)
(1530, 1531, 0)
(1530, 1210, 0)
(1530, 1850, 0)
(1531, 1530, 0)
(1531, 1532, 0)
(1531, 1211, 0)
(1531, 1851, 0)
(1532, 1531, 0)
(1532, 1533, 0)
(1532, 1212, 0)
(1532, 1852, 0)
(1533, 1532, 0)
(1533, 1534, 0)
(1533, 1213, 0)
(1533, 1853, 0)
(1534, 1533, 0)
(1534, 1535, 0)
(1534, 1214, 0)
(1534, 1854, 0)
(1535, 1534, 0)
(1535, 1536, 0)
(1535, 1215, 0)
(1535, 1855, 0)
(1536, 1535, 0)
(1536, 1537, 0)
(1536, 1216, 0)
(1536, 1856, 0)
(1537, 1536, 0)
(1537, 1538, 0)
(1537, 1217, 0)
(1537, 1857, 0)
(1538, 1537, 0)
(1538, 1539, 0)
(1538, 1218, 0)
(1538, 1858, 0)
(1539, 1538, 0)
(1539, 1540, 0)
(1539, 1219, 0)
(1539, 1859, 0)
(1540, 1539, 0)
(1540, 1541, 0)
(1540, 1220, 0)
(1540, 1860, 0)
(1541, 1540, 0)
(1541, 1542, 0)
(1541, 1221, 0)
(1541, 1861, 0)
(1542, 1541, 0)
(1542, 1543, 0)
(1542, 1222, 0)
(1542, 1862, 0)
(1543, 1542, 0)
(1543, 1544, 0)
(1543, 1223, 0)
(1543, 1863, 0)
(1544, 1543, 0)
(1544, 1545, 0)
(1544, 1224, 0)
(1544, 1864, 0)
(1545, 1544, 0)
(1545, 1546, 0)
(1545, 1225, 0)
(1545, 1865, 0)
(1546, 1545, 0)
(1546, 1547, 0)
(1546, 1226, 0)
(1546, 1866, 0)
(1547, 1546, 0)
(1547, 1548, 0)
(1547, 1227, 0)
(1547, 1867, 0)
(1548, 1547, 0)
(1548, 1549, 0)
(1548, 1228, 0)
(1548, 1868, 0)
(1549, 1548, 0)
(1549, 1550, 0)
(1549, 1229, 0)
(1549, 1869, 0)
(1550, 1549, 0)
(1550, 1551, 0)
(1550, 1230, 0)
(1550, 1870, 0)
(1551, 1550, 0)
(1551, 1552, 0)
(1551, 1231, 0)
(1551, 1871, 0)
(1552, 1551, 0)
(1552, 1553, 0)
(1552, 1232, 0)
(1552, 1872, 0)
(1553, 1552, 0)
(1553, 1554, 0)
(1553, 1233, 0)
(1553, 1873, 0)
(1554, 1553, 0)
(1554, 1555, 0)
(1554, 1234, 0)
(1554, 1874, 0)
(1555, 1554, 0)
(1555, 1556, 0)
(1555, 1235, 0)
(1555, 1875, 0)
(1556, 1555, 0)
(1556, 1557, 0)
(1556, 1236, 0)
(1556, 1876, 0)
(1557, 1556, 0)
(1557, 1558, 0)
(1557, 1237, 0)
(1557, 1877, 0)
(1558, 1557, 0)
(1558, 1559, 0)
(1558, 1238, 0)
(1558, 1878, 0)
(1559, 1558, 0)
(1559, 1560, 0)
(1559, 1239, 0)
(1559, 1879, 0)
(1560, 1559, 0)
(1560, 1561, 0)
(1560, 1240, 0)
(1560, 1880, 0)
(1561, 1560, 0)
(1561, 1562, 0)
(1561, 1241, 0)
(1561, 1881, 0)
(1562, 1561, 0)
(1562, 1563, 0)
(1562, 1242, 0)
(1562, 1882, 0)
(1563, 1562, 0)
(1563, 1564, 0)
(1563, 1243, 0)
(1563, 1883, 0)
(1564, 1563, 0)
(1564, 1565, 0)
(1564, 1244, 0)
(1564, 1884, 0)
(1565, 1564, 0)
(1565, 1566, 0)
(1565, 1245, 0)
(1565, 1885, 0)
(1566, 1565, 0)
(1566, 1567, 0)
(1566, 1246, 0)
(1566, 1886, 0)
(1567, 1566, 0)
(1567, 1568, 0)
(1567, 1247, 0)
(1567, 1887, 0)
(1568, 1567, 0)
(1568, 1569, 0)
(1568, 1248, 0)
(1568, 1888, 0)
(1569, 1568, 0)
(1569, 1570, 0)
(1569, 1249, 0)
(1569, 1889, 0)
(1570, 1569, 0)
(1570, 1571, 0)
(1570, 1250, 0)
(1570, 1890, 0)
(1571, 1570, 0)
(1571, 1572, 0)
(1571, 1251, 0)
(1571, 1891, 0)
(1572, 1571, 0)
(1572, 1573, 0)
(1572, 1252, 0)
(1572, 1892, 0)
(1573, 1572, 0)
(1573, 1574, 0)
(1573, 1253, 0)
(1573, 1893, 0)
(1574, 1573, 0)
(1574, 1575, 0)
(1574, 1254, 0)
(1574, 1894, 0)
(1575, 1574, 0)
(1575, 1576, 0)
(1575, 1255, 0)
(1575, 1895, 0)
(1576, 1575, 0)
(1576, 1577, 0)
(1576, 1256, 0)
(1576, 1896, 0)
(1577, 1576, 0)
(1577, 1578, 0)
(1577, 1257, 0)
(1577, 1897, 0)
(1578, 1577, 0)
(1578, 1579, 0)
(1578, 1258, 0)
(1578, 1898, 0)
(1579, 1578, 0)
(1579, 1580, 0)
(1579, 1259, 0)
(1579, 1899, 0)
(1580, 1579, 0)
(1580, 1581, 0)
(1580, 1260, 0)
(1580, 1900, 0)
(1581, 1580, 0)
(1581, 1582, 0)
(1581, 1261, 0)
(1581, 1901, 0)
(1582, 1581, 0)
(1582, 1583, 0)
(1582, 1262, 0)
(1582, 1902, 0)
(1583, 1582, 0)
(1583, 1584, 0)
(1583, 1263, 0)
(1583, 1903, 0)
(1584, 1583, 0)
(1584, 1585, 0)
(1584, 1264, 0)
(1584, 1904, 0)
(1585, 1584, 0)
(1585, 1586, 0)
(1585, 1265, 0)
(1585, 1905, 0)
(1586, 1585, 0)
(1586, 1587, 0)
(1586, 1266, 0)
(1586, 1906, 0)
(1587, 1586, 0)
(1587, 1588, 0)
(1587, 1267, 0)
(1587, 1907, 0)
(1588, 1587, 0)
(1588, 1589, 0)
(1588, 1268, 0)
(1588, 1908, 0)
(1589, 1588, 0)
(1589, 1590, 0)
(1589, 1269, 0)
(1589, 1909, 0)
(1590, 1589, 0)
(1590, 1591, 0)
(1590, 1270, 0)
(1590, 1910, 0)
(1591, 1590, 0)
(1591, 1592, 0)
(1591, 1271, 0)
(1591, 1911, 0)
(1592, 1591, 0)
(1592, 1593, 0)
(1592, 1272, 0)
(1592, 1912, 0)
(1593, 1592, 0)
(1593, 1594, 0)
(1593, 1273, 0)
(1593, 1913, 0)
(1594, 1593, 0)
(1594, 1595, 0)
(1594, 1274, 0)
(1594, 1914, 0)
(1595, 1594, 0)
(1595, 1596, 0)
(1595, 1275, 0)
(1595, 1915, 0)
(1596, 1595, 0)
(1596, 1597, 0)
(1596, 1276, 0)
(1596, 1916, 0)
(1597, 1596, 0)
(1597, 1598, 0)
(1597, 1277, 0)
(1597, 1917, 0)
(1598, 1597, 0)
(1598, 1599, 0)
(1598, 1278, 0)
(1598, 1918, 0)
(1599, 1598, 0)
(1599, 1279, 0)
(1599, 1919, 0)
(1600, 1601, 0)
(1600, 1280, 0)
(1600, 1920, 0)
(1601, 1600, 0)
(1601, 1602, 0)
(1601, 1281, 0)
(1601, 1921, 0)
(1602, 1601, 0)
(1602, 1603, 0)
(1602, 1282, 0)
(1602, 1922, 0)
(1603, 1602, 0)
(1603, 1604, 0)
(1603, 1283, 0)
(1603, 1923, 0)
(1604, 1603, 0)
(1604, 1605, 0)
(1604, 1284, 0)
(1604, 1924, 0)
(1605, 1604, 0)
(1605, 1606, 0)
(1605, 1285, 0)
(1605, 1925, 0)
(1606, 1605, 0)
(1606, 1607, 0)
(1606, 1286, 0)
(1606, 1926, 0)
(1607, 1606, 0)
(1607, 1608, 0)
(1607, 1287, 0)
(1607, 1927, 0)
(1608, 1607, 0)
(1608, 1609, 0)
(1608, 1288, 0)
(1608, 1928, 0)
(1609, 1608, 0)
(1609, 1610, 0)
(1609, 1289, 0)
(1609, 1929, 0)
(1610, 1609, 0)
(1610, 1611, 0)
(1610, 1290, 0)
(1610, 1930, 0)
(1611, 1610, 0)
(1611, 1612, 0)
(1611, 1291, 0)
(1611, 1931, 0)
(1612, 1611, 0)
(1612, 1613, 0)
(1612, 1292, 0)
(1612, 1932, 0)
(1613, 1612, 0)
(1613, 1614, 0)
(1613, 1293, 0)
(1613, 1933, 0)
(1614, 1613, 0)
(1614, 1294, 0)
(1616, 1617, 0)
(1617, 1616, 0)
(1619, 1620, 0)
(1619, 1299, 0)
(1619, 1939, 0)
(1620, 1619, 0)
(1620, 1621, 0)
(1620, 1300, 0)
(1620, 1940, 0)
(1621, 1620, 0)
(1621, 1622, 0)
(1621, 1301, 0)
(1621, 1941, 0)
(1622, 1621, 0)
(1622, 1623, 0)
(1622, 1302, 0)
(1622, 1942, 0)
(1623, 1622, 0)
(1623, 1624, 0)
(1623, 1303, 0)
(1623, 1943, 0)
(1624, 1623, 0)
(1624, 1625, 0)
(1624, 1304, 0)
(1625, 1624, 0)
(1625, 1626, 0)
(1625, 1305, 0)
(1626, 1625, 0)
(1626, 1627, 0)
(1626, 1306, 0)
(1627, 1626, 0)
(1627, 1628, 0)
(1627, 1307, 0)
(1628, 1627, 0)
(1628, 1629, 0)
(1628, 1308, 0)
(1629, 1628, 0)
(1629, 1630, 0)
(1629, 1309, 0)
(1630, 1629, 0)
(1630, 1631, 0)
(1630, 1310, 0)
(1631, 1630, 0)
(1631, 1632, 0)
(1631, 1311, 0)
(1632, 1631, 0)
(1632, 1633, 0)
(1632, 1312, 0)
(1633, 1632, 0)
(1633, 1634, 0)
(1633, 1313, 0)
(1634, 1633, 0)
(1634, 1635, 0)
(1634, 1314, 0)
(1635, 1634, 0)
(1635, 1636, 0)
(1635, 1315, 0)
(1636, 1635, 0)
(1636, 1637, 0)
(1636, 1316, 0)
(1637, 1636, 0)
(1637, 1638, 0)
(1637, 1317, 0)
(1638, 1637, 0)
(1638, 1639, 0)
(1638, 1318, 0)
(1639, 1638, 0)
(1639, 1640, 0)
(1639, 1319, 0)
(1640, 1639, 0)
(1640, 1641, 0)
(1640, 1320, 0)
(1641, 1640, 0)
(1641, 1642, 0)
(1641, 1321, 0)
(1642, 1641, 0)
(1642, 1643, 0)
(1642, 1322, 0)
(1643, 1642, 0)
(1643, 1644, 0)
(1643, 1323, 0)
(1644, 1643, 0)
(1644, 1645, 0)
(1644, 1324, 0)
(1645, 1644, 0)
(1645, 1646, 0)
(1645, 1325, 0)
(1646, 1645, 0)
(1646, 1647, 0)
(1646, 1326, 0)
(1647, 1646, 0)
(1647, 1648, 0)
(1647, 1327, 0)
(1648, 1647, 0)
(1648, 1649, 0)
(1648, 1328, 0)
(1649, 1648, 0)
(1649, 1650, 0)
(1649, 1329, 0)
(1650, 1649, 0)
(1650, 1651, 0)
(1650, 1330, 0)
(1651, 1650, 0)
(1651, 1652, 0)
(1651, 1331, 0)
(1652, 1651, 0)
(1652, 1653, 0)
(1652, 1332, 0)
(1653, 1652, 0)
(1653, 1654, 0)
(1653, 1333, 0)
(1654, 1653, 0)
(1654, 1655, 0)
(1654, 1334, 0)
(1655, 1654, 0)
(1655, 1656, 0)
(1655, 1335, 0)
(1656, 1655, 0)
(1656, 1657, 0)
(1656, 1336, 0)
(1657, 1656, 0)
(1657, 1658, 0)
(1657, 1337, 0)
(1658, 1657, 0)
(1658, 1659, 0)
(1658, 1338, 0)
(1659, 1658, 0)
(1659, 1660, 0)
(1659, 1339, 0)
(1660, 1659, 0)
(1660, 1661, 0)
(1660, 1340, 0)
(1661, 1660, 0)
(1661, 1662, 0)
(1661, 1341, 0)
(1662, 1661, 0)
(1662, 1663, 0)
(1662, 1342, 0)
(1663, 1662, 0)
(1663, 1664, 0)
(1663, 1343, 0)
(1664, 1663, 0)
(1664, 1665, 0)
(1664, 1344, 0)
(1665, 1664, 0)
(1665, 1666, 0)
(1665, 1345, 0)
(1666, 1665, 0)
(1666, 1667, 0)
(1666, 1346, 0)
(1667, 1666, 0)
(1667, 1668, 0)
(1667, 1347, 0)
(1668, 1667, 0)
(1668, 1669, 0)
(1668, 1348, 0)
(1669, 1668, 0)
(1669, 1670, 0)
(1669, 1349, 0)
(1670, 1669, 0)
(1670, 1671, 0)
(1670, 1350, 0)
(1671, 1670, 0)
(1671, 1672, 0)
(1671, 1351, 0)
(1672, 1671, 0)
(1672, 1673, 0)
(1672, 1352, 0)
(1673, 1672, 0)
(1673, 1674, 0)
(1673, 1353, 0)
(1674, 1673, 0)
(1674, 1675, 0)
(1674, 1354, 0)
(1675, 1674, 0)
(1675, 1676, 0)
(1675, 1355, 0)
(1676, 1675, 0)
(1676, 1677, 0)
(1676, 1356, 0)
(1677, 1676, 0)
(1677, 1678, 0)
(1677, 1357, 0)
(1678, 1677, 0)
(1678, 1679, 0)
(1678, 1358, 0)
(1679, 1678, 0)
(1679, 1680, 0)
(1679, 1359, 0)
(1680, 1679, 0)
(1680, 1681, 0)
(1680, 1360, 0)
(1681, 1680, 0)
(1681, 1682, 0)
(1681, 1361, 0)
(1682, 1681, 0)
(1682, 1683, 0)
(1682, 1362, 0)
(1683, 1682, 0)
(1683, 1684, 0)
(1683, 1363, 0)
(1684, 1683, 0)
(1684, 1685, 0)
(1684, 1364, 0)
(1685, 1684, 0)
(1685, 1686, 0)
(1685, 1365, 0)
(1686, 1685, 0)
(1686, 1687, 0)
(1686, 1366, 0)
(1687, 1686, 0)
(1687, 1688, 0)
(1687, 1367, 0)
(1688, 1687, 0)
(1688, 1689, 0)
(1688, 1368, 0)
(1689, 1688, 0)
(1689, 1690, 0)
(1689, 1369, 0)
(1690, 1689, 0)
(1690, 1691, 0)
(1690, 1370, 0)
(1691, 1690, 0)
(1691, 1692, 0)
(1691, 1371, 0)
(1692, 1691, 0)
(1692, 1693, 0)
(1692, 1372, 0)
(1693, 1692, 0)
(1693, 1694, 0)
(1693, 1373, 0)
(1694, 1693, 0)
(1694, 1695, 0)
(1694, 1374, 0)
(1695, 1694, 0)
(1695, 1696, 0)
(1695, 1375, 0)
(1696, 1695, 0)
(1696, 1697, 0)
(1696, 1376, 0)
(1697, 1696, 0)
(1697, 1698, 0)
(1697, 1377, 0)
(1698, 1697, 0)
(1698, 1699, 0)
(1698, 1378, 0)
(1699, 1698, 0)
(1699, 1700, 0)
(1699, 1379, 0)
(1700, 1699, 0)
(1700, 1701, 0)
(1700, 1380, 0)
(1701, 1700, 0)
(1701, 1702, 0)
(1701, 1381, 0)
(1702, 1701, 0)
(1702, 1703, 0)
(1702, 1382, 0)
(1703, 1702, 0)
(1703, 1704, 0)
(1703, 1383, 0)
(1704, 1703, 0)
(1704, 1705, 0)
(1704, 1384, 0)
(1705, 1704, 0)
(1705, 1706, 0)
(1705, 1385, 0)
(1706, 1705, 0)
(1706, 1707, 0)
(1706, 1386, 0)
(1707, 1706, 0)
(1707, 1708, 0)
(1707, 1387, 0)
(1708, 1707, 0)
(1708, 1709, 0)
(1708, 1388, 0)
(1709, 1708, 0)
(1709, 1710, 0)
(1709, 1389, 0)
(1710, 1709, 0)
(1710, 1711, 0)
(1710, 1390, 0)
(1711, 1710, 0)
(1711, 1712, 0)
(1711, 1391, 0)
(1712, 1711, 0)
(1712, 1713, 0)
(1712, 1392, 0)
(1713, 1712, 0)
(1713, 1714, 0)
(1713, 1393, 0)
(1714, 1713, 0)
(1714, 1715, 0)
(1714, 1394, 0)
(1715, 1714, 0)
(1715, 1716, 0)
(1715, 1395, 0)
(1716, 1715, 0)
(1716, 1717, 0)
(1716, 1396, 0)
(1717, 1716, 0)
(1717, 1718, 0)
(1717, 1397, 0)
(1718, 1717, 0)
(1718, 1719, 0)
(1718, 1398, 0)
(1719, 1718, 0)
(1719, 1720, 0)
(1719, 1399, 0)
(1720, 1719, 0)
(1720, 1721, 0)
(1720, 1400, 0)
(1721, 1720, 0)
(1721, 1722, 0)
(1721, 1401, 0)
(1722, 1721, 0)
(1722, 1723, 0)
(1722, 1402, 0)
(1723, 1722, 0)
(1723, 1724, 0)
(1723, 1403, 0)
(1724, 1723, 0)
(1724, 1725, 0)
(1724, 1404, 0)
(1725, 1724, 0)
(1725, 1726, 0)
(1725, 1405, 0)
(1726, 1725, 0)
(1726, 1727, 0)
(1726, 1406, 0)
(1727, 1726, 0)
(1727, 1728, 0)
(1727, 1407, 0)
(1728, 1727, 0)
(1728, 1729, 0)
(1728, 1408, 0)
(1729, 1728, 0)
(1729, 1730, 0)
(1729, 1409, 0)
(1730, 1729, 0)
(1730, 1731, 0)
(1730, 1410, 0)
(1731, 1730, 0)
(1731, 1732, 0)
(1731, 1411, 0)
(1732, 1731, 0)
(1732, 1733, 0)
(1732, 1412, 0)
(1733, 1732, 0)
(1733, 1734, 0)
(1733, 1413, 0)
(1734, 1733, 0)
(1734, 1735, 0)
(1734, 1414, 0)
(1735, 1734, 0)
(1735, 1736, 0)
(1735, 1415, 0)
(1736, 1735, 0)
(1736, 1737, 0)
(1736, 1416, 0)
(1737, 1736, 0)
(1737, 1738, 0)
(1737, 1417, 0)
(1738, 1737, 0)
(1738, 1739, 0)
(1738, 1418, 0)
(1739, 1738, 0)
(1739, 1740, 0)
(1739, 1419, 0)
(1740, 1739, 0)
(1740, 1741, 0)
(1740, 1420, 0)
(1741, 1740, 0)
(1741, 1742, 0)
(1741, 1421, 0)
(1742, 1741, 0)
(1742, 1743, 0)
(1742, 1422, 0)
(1743, 1742, 0)
(1743, 1744, 0)
(1743, 1423, 0)
(1744, 1743, 0)
(1744, 1745, 0)
(1744, 1424, 0)
(1745, 1744, 0)
(1745, 1746, 0)
(1745, 1425, 0)
(1746, 1745, 0)
(1746, 1747, 0)
(1746, 1426, 0)
(1747, 1746, 0)
(1747, 1748, 0)
(1747, 1427, 0)
(1748, 1747, 0)
(1748, 1749, 0)
(1748, 1428, 0)
(1749, 1748, 0)
(1749, 1750, 0)
(1749, 1429, 0)
(1750, 1749, 0)
(1750, 1751, 0)
(1750, 1430, 0)
(1751, 1750, 0)
(1751, 1752, 0)
(1751, 1431, 0)
(1752, 1751, 0)
(1752, 1753, 0)
(1752, 1432, 0)
(1753, 1752, 0)
(1753, 1754, 0)
(1753, 1433, 0)
(1754, 1753, 0)
(1754, 1755, 0)
(1754, 1434, 0)
(1755, 1754, 0)
(1755, 1756, 0)
(1755, 1435, 0)
(1756, 1755, 0)
(1756, 1757, 0)
(1756, 1436, 0)
(1757, 1756, 0)
(1757, 1758, 0)
(1757, 1437, 0)
(1758, 1757, 0)
(1758, 1759, 0)
(1758, 1438, 0)
(1759, 1758, 0)
(1759, 1760, 0)
(1759, 1439, 0)
(1760, 1759, 0)
(1760, 1761, 0)
(1760, 1440, 0)
(1761, 1760, 0)
(1761, 1762, 0)
(1761, 1441, 0)
(1762, 1761, 0)
(1762, 1763, 0)
(1762, 1442, 0)
(1763, 1762, 0)
(1763, 1764, 0)
(1763, 1443, 0)
(1764, 1763, 0)
(1764, 1765, 0)
(1764, 1444, 0)
(1765, 1764, 0)
(1765, 1766, 0)
(1765, 1445, 0)
(1766, 1765, 0)
(1766, 1767, 0)
(1766, 1446, 0)
(1767, 1766, 0)
(1767, 1768, 0)
(1767, 1447, 0)
(1768, 1767, 0)
(1768, 1769, 0)
(1768, 1448, 0)
(1769, 1768, 0)
(1769, 1770, 0)
(1769, 1449, 0)
(1770, 1769, 0)
(1770, 1771, 0)
(1770, 1450, 0)
(1771, 1770, 0)
(1771, 1772, 0)
(1771, 1451, 0)
(1772, 1771, 0)
(1772, 1773, 0)
(1772, 1452, 0)
(1773, 1772, 0)
(1773, 1774, 0)
(1773, 1453, 0)
(1774, 1773, 0)
(1774, 1775, 0)
(1774, 1454, 0)
(1775, 1774, 0)
(1775, 1776, 0)
(1775, 1455, 0)
(1776, 1775, 0)
(1776, 1777, 0)
(1776, 1456, 0)
(1777, 1776, 0)
(1777, 1778, 0)
(1777, 1457, 0)
(1778, 1777, 0)
(1778, 1779, 0)
(1778, 1458, 0)
(1779, 1778, 0)
(1779, 1780, 0)
(1779, 1459, 0)
(1780, 1779, 0)
(1780, 1781, 0)
(1780, 1460, 0)
(1781, 1780, 0)
(1781, 1782, 0)
(1781, 1461, 0)
(1782, 1781, 0)
(1782, 1783, 0)
(1782, 1462, 0)
(1783, 1782, 0)
(1783, 1784, 0)
(1783, 1463, 0)
(1784, 1783, 0)
(1784, 1785, 0)
(1784, 1464, 0)
(1785, 1784, 0)
(1785, 1786, 0)
(1785, 1465, 0)
(1786, 1785, 0)
(1786, 1787, 0)
(1786, 1466, 0)
(1787, 1786, 0)
(1787, 1788, 0)
(1787, 1467, 0)
(1788, 1787, 0)
(1788, 1789, 0)
(1788, 1468, 0)
(1789, 1788, 0)
(1789, 1790, 0)
(1789, 1469, 0)
(1790, 1789, 0)
(1790, 1791, 0)
(1790, 1470, 0)
(1791, 1790, 0)
(1791, 1792, 0)
(1791, 1471, 0)
(1792, 1791, 0)
(1792, 1793, 0)
(1792, 1472, 0)
(1793, 1792, 0)
(1793, 1794, 0)
(1793, 1473, 0)
(1794, 1793, 0)
(1794, 1795, 0)
(1794, 1474, 0)
(1795, 1794, 0)
(1795, 1796, 0)
(1795, 1475, 0)
(1796, 1795, 0)
(1796, 1797, 0)
(1796, 1476, 0)
(1797, 1796, 0)
(1797, 1798, 0)
(1797, 1477, 0)
(1798, 1797, 0)
(1798, 1799, 0)
(1798, 1478, 0)
(1799, 1798, 0)
(1799, 1800, 0)
(1799, 1479, 0)
(1800, 1799, 0)
(1800, 1801, 0)
(1800, 1480, 0)
(1801, 1800, 0)
(1801, 1802, 0)
(1801, 1481, 0)
(1802, 1801, 0)
(1802, 1803, 0)
(1802, 1482, 0)
(1803, 1802, 0)
(1803, 1804, 0)
(1803, 1483, 0)
(1804, 1803, 0)
(1804, 1805, 0)
(1804, 1484, 0)
(1805, 1804, 0)
(1805, 1806, 0)
(1805, 1485, 0)
(1806, 1805, 0)
(1806, 1807, 0)
(1806, 1486, 0)
(1807, 1806, 0)
(1807, 1808, 0)
(1807, 1487, 0)
(1808, 1807, 0)
(1808, 1809, 0)
(1808, 1488, 0)
(1809, 1808, 0)
(1809, 1810, 0)
(1809, 1489, 0)
(1810, 1809, 0)
(1810, 1811, 0)
(1810, 1490, 0)
(1811, 1810, 0)
(1811, 1812, 0)
(1811, 1491, 0)
(1812, 1811, 0)
(1812, 1813, 0)
(1812, 1492, 0)
(1813, 1812, 0)
(1813, 1814, 0)
(1813, 1493, 0)
(1814, 1813, 0)
(1814, 1815, 0)
(1814, 1494, 0)
(1815, 1814, 0)
(1815, 1816, 0)
(1815, 1495, 0)
(1816, 1815, 0)
(1816, 1817, 0)
(1816, 1496, 0)
(1817, 1816, 0)
(1817, 1818, 0)
(1817, 1497, 0)
(1818, 1817, 0)
(1818, 1819, 0)
(1818, 1498, 0)
(1819, 1818, 0)
(1819, 1820, 0)
(1819, 1499, 0)
(1820, 1819, 0)
(1820, 1821, 0)
(1820, 1500, 0)
(1821, 1820, 0)
(1821, 1822, 0)
(1821, 1501, 0)
(1822, 1821, 0)
(1822, 1823, 0)
(1822, 1502, 0)
(1823, 1822, 0)
(1823, 1824, 0)
(1823, 1503, 0)
(1824, 1823, 0)
(1824, 1825, 0)
(1824, 1504, 0)
(1825, 1824, 0)
(1825, 1826, 0)
(1825, 1505, 0)
(1826, 1825, 0)
(1826, 1827, 0)
(1826, 1506, 0)
(1827, 1826, 0)
(1827, 1828, 0)
(1827, 1507, 0)
(1828, 1827, 0)
(1828, 1829, 0)
(1828, 1508, 0)
(1829, 1828, 0)
(1829, 1830, 0)
(1829, 1509, 0)
(1830, 1829, 0)
(1830, 1831, 0)
(1830, 1510, 0)
(1831, 1830, 0)
(1831, 1832, 0)
(1831, 1511, 0)
(1832, 1831, 0)
(1832, 1833, 0)
(1832, 1512, 0)
(1833, 1832, 0)
(1833, 1834, 0)
(1833, 1513, 0)
(1834, 1833, 0)
(1834, 1835, 0)
(1834, 1514, 0)
(1835, 1834, 0)
(1835, 1836, 0)
(1835, 1515, 0)
(1836, 1835, 0)
(1836, 1837, 0)
(1836, 1516, 0)
(1837, 1836, 0)
(1837, 1838, 0)
(1837, 1517, 0)
(1838, 1837, 0)
(1838, 1839, 0)
(1838, 1518, 0)
(1839, 1838, 0)
(1839, 1840, 0)
(1839, 1519, 0)
(1840, 1839, 0)
(1840, 1841, 0)
(1840, 1520, 0)
(1841, 1840, 0)
(1841, 1842, 0)
(1841, 1521, 0)
(1842, 1841, 0)
(1842, 1843, 0)
(1842, 1522, 0)
(1843, 1842, 0)
(1843, 1844, 0)
(1843, 1523, 0)
(1844, 1843, 0)
(1844, 1845, 0)
(1844, 1524, 0)
(1845, 1844, 0)
(1845, 1846, 0)
(1845, 1525, 0)
(1846, 1845, 0)
(1846, 1847, 0)
(1846, 1526, 0)
(1847, 1846, 0)
(1847, 1848, 0)
(1847, 1527, 0)
(1848, 1847, 0)
(1848, 1849, 0)
(1848, 1528, 0)
(1849, 1848, 0)
(1849, 1850, 0)
(1849, 1529, 0)
(1850, 1849, 0)
(1850, 1851, 0)
(1850, 1530, 0)
(1851, 1850, 0)
(1851, 1852, 0)
(1851, 1531, 0)
(1852, 1851, 0)
(1852, 1853, 0)
(1852, 1532, 0)
(1853, 1852, 0)
(1853, 1854, 0)
(1853, 1533, 0)
(1854, 1853, 0)
(1854, 1855, 0)
(1854, 1534, 0)
(1855, 1854, 0)
(1855, 1856, 0)
(1855, 1535, 0)
(1856, 1855, 0)
(1856, 1857, 0)
(1856, 1536, 0)
(1857, 1856, 0)
(1857, 1858, 0)
(1857, 1537, 0)
(1858, 1857, 0)
(1858, 1859, 0)
(1858, 1538, 0)
(1859, 1858, 0)
(1859, 1860, 0)
(1859, 1539, 0)
(1860, 1859, 0)
(1860, 1861, 0)
(1860, 1540, 0)
(1861, 1860, 0)
(1861, 1862, 0)
(1861, 1541, 0)
(1862, 1861, 0)
(1862, 1863, 0)
(1862, 1542, 0)
(1863, 1862, 0)
(1863, 1864, 0)
(1863, 1543, 0)
(1864, 1863, 0)
(1864, 1865, 0)
(1864, 1544, 0)
(1865, 1864, 0)
(1865, 1866, 0)
(1865, 1545, 0)
(1866, 1865, 0)
(1866, 1867, 0)
(1866, 1546, 0)
(1867, 1866, 0)
(1867, 1868, 0)
(1867, 1547, 0)
(1868, 1867, 0)
(1868, 1869, 0)
(1868, 1548, 0)
(1869, 1868, 0)
(1869, 1870, 0)
(1869, 1549, 0)
(1870, 1869, 0)
(1870, 1871, 0)
(1870, 1550, 0)
(1871, 1870, 0)
(1871, 1872, 0)
(1871, 1551, 0)
(1872, 1871, 0)
(1872, 1873, 0)
(1872, 1552, 0)
(1873, 1872, 0)
(1873, 1874, 0)
(1873, 1553, 0)
(1874, 1873, 0)
(1874, 1875, 0)
(1874, 1554, 0)
(1875, 1874, 0)
(1875, 1876, 0)
(1875, 1555, 0)
(1876, 1875, 0)
(1876, 1877, 0)
(1876, 1556, 0)
(1877, 1876, 0)
(1877, 1878, 0)
(1877, 1557, 0)
(1878, 1877, 0)
(1878, 1879, 0)
(1878, 1558, 0)
(1879, 1878, 0)
(1879, 1880, 0)
(1879, 1559, 0)
(1880, 1879, 0)
(1880, 1881, 0)
(1880, 1560, 0)
(1881, 1880, 0)
(1881, 1882, 0)
(1881, 1561, 0)
(1882, 1881, 0)
(1882, 1883, 0)
(1882, 1562, 0)
(1883, 1882, 0)
(1883, 1884, 0)
(1883, 1563, 0)
(1884, 1883, 0)
(1884, 1885, 0)
(1884, 1564, 0)
(1885, 1884, 0)
(1885, 1886, 0)
(1885, 1565, 0)
(1886, 1885, 0)
(1886, 1887, 0)
(1886, 1566, 0)
(1887, 1886, 0)
(1887, 1888, 0)
(1887, 1567, 0)
(1888, 1887, 0)
(1888, 1889, 0)
(1888, 1568, 0)
(1889, 1888, 0)
(1889, 1890, 0)
(1889, 1569, 0)
(1890, 1889, 0)
(1890, 1891, 0)
(1890, 1570, 0)
(1891, 1890, 0)
(1891, 1892, 0)
(1891, 1571, 0)
(1892, 1891, 0)
(1892, 1893, 0)
(1892, 1572, 0)
(1893, 1892, 0)
(1893, 1894, 0)
(1893, 1573, 0)
(1894, 1893, 0)
(1894, 1895, 0)
(1894, 1574, 0)
(1895, 1894, 0)
(1895, 1896, 0)
(1895, 1575, 0)
(1896, 1895, 0)
(1896, 1897, 0)
(1896, 1576, 0)
(1897, 1896, 0)
(1897, 1898, 0)
(1897, 1577, 0)
(1898, 1897, 0)
(1898, 1899, 0)
(1898, 1578, 0)
(1899, 1898, 0)
(1899, 1900, 0)
(1899, 1579, 0)
(1900, 1899, 0)
(1900, 1901, 0)
(1900, 1580, 0)
(1901, 1900, 0)
(1901, 1902, 0)
(1901, 1581, 0)
(1902, 1901, 0)
(1902, 1903, 0)
(1902, 1582, 0)
(1903, 1902, 0)
(1903, 1904, 0)
(1903, 1583, 0)
(1904, 1903, 0)
(1904, 1905, 0)
(1904, 1584, 0)
(1905, 1904, 0)
(1905, 1906, 0)
(1905, 1585, 0)
(1906, 1905, 0)
(1906, 1907, 0)
(1906, 1586, 0)
(1907, 1906, 0)
(1907, 1908, 0)
(1907, 1587, 0)
(1908, 1907, 0)
(1908, 1909, 0)
(1908, 1588, 0)
(1909, 1908, 0)
(1909, 1910, 0)
(1909, 1589, 0)
(1910, 1909, 0)
(1910, 1911, 0)
(1910, 1590, 0)
(1911, 1910, 0)
(1911, 1912, 0)
(1911, 1591, 0)
(1911, 2231, 0)
(1912, 1911, 0)
(1912, 1913, 0)
(1912, 1592, 0)
(1912, 2232, 0)
(1913, 1912, 0)
(1913, 1914, 0)
(1913, 1593, 0)
(1913, 2233, 0)
(1914, 1913, 0)
(1914, 1915, 0)
(1914, 1594, 0)
(1914, 2234, 0)
(1915, 1914, 0)
(1915, 1916, 0)
(1915, 1595, 0)
(1915, 2235, 0)
(1916, 1915, 0)
(1916, 1917, 0)
(1916, 1596, 0)
(1916, 2236, 0)
(1917, 1916, 0)
(1917, 1918, 0)
(1917, 1597, 0)
(1917, 2237, 0)
(1918, 1917, 0)
(1918, 1919, 0)
(1918, 1598, 0)
(1918, 2238, 0)
(1919, 1918, 0)
(1919, 1599, 0)
(1919, 2239, 0)
(1920, 1921, 0)
(1920, 1600, 0)
(1920, 2240, 0)
(1921, 1920, 0)
(1921, 1922, 0)
(1921, 1601, 0)
(1921, 2241, 0)
(1922, 1921, 0)
(1922, 1923, 0)
(1922, 1602, 0)
(1922, 2242, 0)
(1923, 1922, 0)
(1923, 1924, 0)
(1923, 1603, 0)
(1923, 2243, 0)
(1924, 1923, 0)
(1924, 1925, 0)
(1924, 1604, 0)
(1924, 2244, 0)
(1925, 1924, 0)
(1925, 1926, 0)
(1925, 1605, 0)
(1925, 2245, 0)
(1926, 1925, 0)
(1926, 1927, 0)
(1926, 1606, 0)
(1926, 2246, 0)
(1927, 1926, 0)
(1927, 1928, 0)
(1927, 1607, 0)
(1927, 2247, 0)
(1928, 1927, 0)
(1928, 1929, 0)
(1928, 1608, 0)
(1928, 2248, 0)
(1929, 1928, 0)
(1929, 1930, 0)
(1929, 1609, 0)
(1929, 2249, 0)
(1930, 1929, 0)
(1930, 1931, 0)
(1930, 1610, 0)
(1930, 2250, 0)
(1931, 1930, 0)
(1931, 1932, 0)
(1931, 1611, 0)
(1931, 2251, 0)
(1932, 1931, 0)
(1932, 1933, 0)
(1932, 1612, 0)
(1932, 2252, 0)
(1933, 1932, 0)
(1933, 1613, 0)
(1938, 1939, 0)
(1939, 1938, 0)
(1939, 1940, 0)
(1939, 1619, 0)
(1939, 2259, 0)
(1940, 1939, 0)
(1940, 1941, 0)
(1940, 1620, 0)
(1941, 1940, 0)
(1941, 1942, 0)
(1941, 1621, 0)
(1941, 2261, 0)
(1942, 1941, 0)
(1942, 1943, 0)
(1942, 1622, 0)
(1943, 1942, 0)
(1943, 1623, 0)
(1944, 1945, 0)
(1945, 1944, 0)
(1945, 1946, 0)
(1946, 1945, 0)
(1946, 1947, 0)
(1947, 1946, 0)
(1947, 1948, 0)
(1948, 1947, 0)
(1948, 1949, 0)
(1949, 1948, 0)
(1949, 1950, 0)
(1950, 1949, 0)
(1950, 1951, 0)
(1951, 1950, 0)
(1951, 1952, 0)
(1952, 1951, 0)
(1952, 1953, 0)
(1953, 1952, 0)
(1953, 1954, 0)
(1954, 1953, 0)
(1954, 1955, 0)
(1955, 1954, 0)
(1955, 1956, 0)
(1956, 1955, 0)
(1956, 1957, 0)
(1957, 1956, 0)
(1957, 1958, 0)
(1958, 1957, 0)
(1958, 1959, 0)
(1959, 1958, 0)
(1959, 1960, 0)
(1960, 1959, 0)
(1960, 1961, 0)
(1961, 1960, 0)
(1961, 1962, 0)
(1962, 1961, 0)
(1962, 1963, 0)
(1963, 1962, 0)
(1963, 1964, 0)
(1964, 1963, 0)
(1964, 1965, 0)
(1965, 1964, 0)
(1965, 1966, 0)
(1966, 1965, 0)
(1966, 1967, 0)
(1967, 1966, 0)
(1967, 1968, 0)
(1968, 1967, 0)
(1968, 1969, 0)
(1969, 1968, 0)
(1969, 1970, 0)
(1970, 1969, 0)
(1970, 1971, 0)
(1971, 1970, 0)
(1971, 1972, 0)
(1972, 1971, 0)
(1972, 1973, 0)
(1973, 1972, 0)
(1973, 1974, 0)
(1974, 1973, 0)
(1974, 1975, 0)
(1975, 1974, 0)
(1975, 1976, 0)
(1976, 1975, 0)
(1976, 1977, 0)
(1977, 1976, 0)
(1977, 1978, 0)
(1978, 1977, 0)
(1978, 1979, 0)
(1979, 1978, 0)
(1979, 1980, 0)
(1980, 1979, 0)
(1980, 1981, 0)
(1981, 1980, 0)
(1981, 1982, 0)
(1982, 1981, 0)
(1982, 1983, 0)
(1983, 1982, 0)
(1983, 1984, 0)
(1984, 1983, 0)
(1984, 1985, 0)
(1985, 1984, 0)
(1985, 1986, 0)
(1986, 1985, 0)
(1986, 1987, 0)
(1987, 1986, 0)
(1987, 1988, 0)
(1988, 1987, 0)
(1988, 1989, 0)
(1989, 1988, 0)
(1989, 1990, 0)
(1990, 1989, 0)
(1990, 1991, 0)
(1991, 1990, 0)
(1991, 1992, 0)
(1992, 1991, 0)
(1992, 1993, 0)
(1993, 1992, 0)
(1993, 1994, 0)
(1994, 1993, 0)
(1994, 1995, 0)
(1995, 1994, 0)
(1995, 1996, 0)
(1996, 1995, 0)
(1996, 1997, 0)
(1997, 1996, 0)
(1997, 1998, 0)
(1998, 1997, 0)
(1998, 1999, 0)
(1999, 1998, 0)
(1999, 2000, 0)
(2000, 1999, 0)
(2000, 2001, 0)
(2001, 2000, 0)
(2001, 2002, 0)
(2002, 2001, 0)
(2002, 2003, 0)
(2003, 2002, 0)
(2003, 2004, 0)
(2004, 2003, 0)
(2004, 2005, 0)
(2005, 2004, 0)
(2005, 2006, 0)
(2006, 2005, 0)
(2006, 2007, 0)
(2007, 2006, 0)
(2007, 2008, 0)
(2008, 2007, 0)
(2008, 2009, 0)
(2009, 2008, 0)
(2009, 2010, 0)
(2010, 2009, 0)
(2010, 2011, 0)
(2011, 2010, 0)
(2011, 2012, 0)
(2012, 2011, 0)
(2012, 2013, 0)
(2013, 2012, 0)
(2013, 2014, 0)
(2014, 2013, 0)
(2014, 2015, 0)
(2015, 2014, 0)
(2015, 2016, 0)
(2016, 2015, 0)
(2016, 2017, 0)
(2017, 2016, 0)
(2017, 2018, 0)
(2018, 2017, 0)
(2018, 2019, 0)
(2019, 2018, 0)
(2019, 2020, 0)
(2020, 2019, 0)
(2020, 2021, 0)
(2021, 2020, 0)
(2021, 2022, 0)
(2022, 2021, 0)
(2022, 2023, 0)
(2023, 2022, 0)
(2023, 2024, 0)
(2024, 2023, 0)
(2024, 2025, 0)
(2025, 2024, 0)
(2025, 2026, 0)
(2026, 2025, 0)
(2026, 2027, 0)
(2027, 2026, 0)
(2027, 2028, 0)
(2028, 2027, 0)
(2028, 2029, 0)
(2029, 2028, 0)
(2029, 2030, 0)
(2030, 2029, 0)
(2030, 2031, 0)
(2031, 2030, 0)
(2031, 2032, 0)
(2032, 2031, 0)
(2032, 2033, 0)
(2033, 2032, 0)
(2033, 2034, 0)
(2034, 2033, 0)
(2034, 2035, 0)
(2035, 2034, 0)
(2035, 2036, 0)
(2036, 2035, 0)
(2036, 2037, 0)
(2037, 2036, 0)
(2037, 2038, 0)
(2038, 2037, 0)
(2038, 2039, 0)
(2039, 2038, 0)
(2039, 2040, 0)
(2040, 2039, 0)
(2040, 2041, 0)
(2041, 2040, 0)
(2041, 2042, 0)
(2042, 2041, 0)
(2042, 2043, 0)
(2043, 2042, 0)
(2043, 2044, 0)
(2044, 2043, 0)
(2044, 2045, 0)
(2045, 2044, 0)
(2045, 2046, 0)
(2046, 2045, 0)
(2046, 2047, 0)
(2047, 2046, 0)
(2047, 2048, 0)
(2048, 2047, 0)
(2048, 2049, 0)
(2049, 2048, 0)
(2049, 2050, 0)
(2050, 2049, 0)
(2050, 2051, 0)
(2051, 2050, 0)
(2051, 2052, 0)
(2052, 2051, 0)
(2052, 2053, 0)
(2053, 2052, 0)
(2053, 2054, 0)
(2054, 2053, 0)
(2054, 2055, 0)
(2055, 2054, 0)
(2055, 2056, 0)
(2056, 2055, 0)
(2056, 2057, 0)
(2057, 2056, 0)
(2057, 2058, 0)
(2058, 2057, 0)
(2058, 2059, 0)
(2059, 2058, 0)
(2059, 2060, 0)
(2060, 2059, 0)
(2060, 2061, 0)
(2061, 2060, 0)
(2061, 2062, 0)
(2062, 2061, 0)
(2062, 2063, 0)
(2063, 2062, 0)
(2063, 2064, 0)
(2064, 2063, 0)
(2064, 2065, 0)
(2065, 2064, 0)
(2065, 2066, 0)
(2066, 2065, 0)
(2066, 2067, 0)
(2067, 2066, 0)
(2067, 2068, 0)
(2068, 2067, 0)
(2068, 2069, 0)
(2069, 2068, 0)
(2069, 2070, 0)
(2070, 2069, 0)
(2070, 2071, 0)
(2071, 2070, 0)
(2071, 2072, 0)
(2072, 2071, 0)
(2072, 2073, 0)
(2073, 2072, 0)
(2073, 2074, 0)
(2074, 2073, 0)
(2074, 2075, 0)
(2075, 2074, 0)
(2075, 2076, 0)
(2076, 2075, 0)
(2076, 2077, 0)
(2077, 2076, 0)
(2077, 2078, 0)
(2078, 2077, 0)
(2078, 2079, 0)
(2079, 2078, 0)
(2079, 2080, 0)
(2080, 2079, 0)
(2080, 2081, 0)
(2081, 2080, 0)
(2081, 2082, 0)
(2082, 2081, 0)
(2082, 2083, 0)
(2083, 2082, 0)
(2083, 2084, 0)
(2084, 2083, 0)
(2084, 2085, 0)
(2085, 2084, 0)
(2085, 2086, 0)
(2086, 2085, 0)
(2086, 2087, 0)
(2087, 2086, 0)
(2087, 2088, 0)
(2088, 2087, 0)
(2088, 2089, 0)
(2089, 2088, 0)
(2089, 2090, 0)
(2090, 2089, 0)
(2090, 2091, 0)
(2091, 2090, 0)
(2091, 2092, 0)
(2092, 2091, 0)
(2092, 2093, 0)
(2093, 2092, 0)
(2093, 2094, 0)
(2094, 2093, 0)
(2094, 2095, 0)
(2095, 2094, 0)
(2095, 2096, 0)
(2096, 2095, 0)
(2096, 2097, 0)
(2097, 2096, 0)
(2097, 2098, 0)
(2098, 2097, 0)
(2098, 2099, 0)
(2099, 2098, 0)
(2099, 2100, 0)
(2100, 2099, 0)
(2100, 2101, 0)
(2101, 2100, 0)
(2101, 2102, 0)
(2102, 2101, 0)
(2102, 2103, 0)
(2103, 2102, 0)
(2103, 2104, 0)
(2104, 2103, 0)
(2104, 2105, 0)
(2105, 2104, 0)
(2105, 2106, 0)
(2106, 2105, 0)
(2106, 2107, 0)
(2107, 2106, 0)
(2107, 2108, 0)
(2108, 2107, 0)
(2108, 2109, 0)
(2109, 2108, 0)
(2109, 2110, 0)
(2110, 2109, 0)
(2110, 2111, 0)
(2111, 2110, 0)
(2111, 2112, 0)
(2112, 2111, 0)
(2112, 2113, 0)
(2113, 2112, 0)
(2113, 2114, 0)
(2114, 2113, 0)
(2114, 2115, 0)
(2115, 2114, 0)
(2115, 2116, 0)
(2116, 2115, 0)
(2116, 2117, 0)
(2117, 2116, 0)
(2117, 2118, 0)
(2118, 2117, 0)
(2118, 2119, 0)
(2119, 2118, 0)
(2119, 2120, 0)
(2120, 2119, 0)
(2120, 2121, 0)
(2121, 2120, 0)
(2121, 2122, 0)
(2122, 2121, 0)
(2122, 2123, 0)
(2123, 2122, 0)
(2123, 2124, 0)
(2124, 2123, 0)
(2124, 2125, 0)
(2125, 2124, 0)
(2125, 2126, 0)
(2126, 2125, 0)
(2126, 2127, 0)
(2127, 2126, 0)
(2127, 2128, 0)
(2128, 2127, 0)
(2128, 2129, 0)
(2129, 2128, 0)
(2129, 2130, 0)
(2130, 2129, 0)
(2130, 2131, 0)
(2131, 2130, 0)
(2131, 2132, 0)
(2132, 2131, 0)
(2132, 2133, 0)
(2133, 2132, 0)
(2133, 2134, 0)
(2134, 2133, 0)
(2134, 2135, 0)
(2135, 2134, 0)
(2135, 2136, 0)
(2136, 2135, 0)
(2136, 2137, 0)
(2137, 2136, 0)
(2137, 2138, 0)
(2138, 2137, 0)
(2138, 2139, 0)
(2139, 2138, 0)
(2139, 2140, 0)
(2140, 2139, 0)
(2140, 2141, 0)
(2141, 2140, 0)
(2141, 2142, 0)
(2142, 2141, 0)
(2142, 2143, 0)
(2143, 2142, 0)
(2143, 2144, 0)
(2144, 2143, 0)
(2144, 2145, 0)
(2145, 2144, 0)
(2145, 2146, 0)
(2146, 2145, 0)
(2146, 2147, 0)
(2147, 2146, 0)
(2147, 2148, 0)
(2148, 2147, 0)
(2148, 2149, 0)
(2149, 2148, 0)
(2149, 2150, 0)
(2150, 2149, 0)
(2150, 2151, 0)
(2151, 2150, 0)
(2151, 2152, 0)
(2152, 2151, 0)
(2152, 2153, 0)
(2153, 2152, 0)
(2153, 2154, 0)
(2154, 2153, 0)
(2154, 2155, 0)
(2155, 2154, 0)
(2155, 2156, 0)
(2156, 2155, 0)
(2156, 2157, 0)
(2157, 2156, 0)
(2157, 2158, 0)
(2158, 2157, 0)
(2158, 2159, 0)
(2159, 2158, 0)
(2159, 2160, 0)
(2160, 2159, 0)
(2160, 2161, 0)
(2161, 2160, 0)
(2161, 2162, 0)
(2162, 2161, 0)
(2162, 2163, 0)
(2163, 2162, 0)
(2163, 2164, 0)
(2164, 2163, 0)
(2164, 2165, 0)
(2165, 2164, 0)
(2165, 2166, 0)
(2166, 2165, 0)
(2166, 2167, 0)
(2167, 2166, 0)
(2167, 2168, 0)
(2168, 2167, 0)
(2168, 2169, 0)
(2169, 2168, 0)
(2169, 2170, 0)
(2170, 2169, 0)
(2170, 2171, 0)
(2171, 2170, 0)
(2171, 2172, 0)
(2172, 2171, 0)
(2172, 2173, 0)
(2173, 2172, 0)
(2173, 2174, 0)
(2174, 2173, 0)
(2174, 2175, 0)
(2175, 2174, 0)
(2175, 2176, 0)
(2176, 2175, 0)
(2176, 2177, 0)
(2177, 2176, 0)
(2177, 2178, 0)
(2178, 2177, 0)
(2178, 2179, 0)
(2179, 2178, 0)
(2179, 2180, 0)
(2180, 2179, 0)
(2180, 2181, 0)
(2181, 2180, 0)
(2181, 2182, 0)
(2182, 2181, 0)
(2182, 2183, 0)
(2183, 2182, 0)
(2183, 2184, 0)
(2184, 2183, 0)
(2184, 2185, 0)
(2185, 2184, 0)
(2185, 2186, 0)
(2186, 2185, 0)
(2186, 2187, 0)
(2187, 2186, 0)
(2187, 2188, 0)
(2188, 2187, 0)
(2188, 2189, 0)
(2189, 2188, 0)
(2189, 2190, 0)
(2190, 2189, 0)
(2190, 2191, 0)
(2191, 2190, 0)
(2191, 2192, 0)
(2192, 2191, 0)
(2192, 2193, 0)
(2193, 2192, 0)
(2193, 2194, 0)
(2194, 2193, 0)
(2194, 2195, 0)
(2195, 2194, 0)
(2195, 2196, 0)
(2196, 2195, 0)
(2196, 2197, 0)
(2197, 2196, 0)
(2197, 2198, 0)
(2198, 2197, 0)
(2198, 2199, 0)
(2199, 2198, 0)
(2199, 2200, 0)
(2200, 2199, 0)
(2200, 2201, 0)
(2201, 2200, 0)
(2201, 2202, 0)
(2202, 2201, 0)
(2202, 2203, 0)
(2203, 2202, 0)
(2203, 2204, 0)
(2204, 2203, 0)
(2204, 2205, 0)
(2205, 2204, 0)
(2205, 2206, 0)
(2206, 2205, 0)
(2206, 2207, 0)
(2207, 2206, 0)
(2207, 2208, 0)
(2208, 2207, 0)
(2208, 2209, 0)
(2209, 2208, 0)
(2209, 2210, 0)
(2210, 2209, 0)
(2210, 2211, 0)
(2211, 2210, 0)
(2211, 2212, 0)
(2212, 2211, 0)
(2212, 2213, 0)
(2213, 2212, 0)
(2213, 2214, 0)
(2214, 2213, 0)
(2214, 2215, 0)
(2215, 2214, 0)
(2215, 2216, 0)
(2216, 2215, 0)
(2216, 2217, 0)
(2217, 2216, 0)
(2217, 2218, 0)
(2218, 2217, 0)
(2218, 2219, 0)
(2219, 2218, 0)
(2219, 2220, 0)
(2220, 2219, 0)
(2220, 2221, 0)
(2221, 2220, 0)
(2221, 2222, 0)
(2222, 2221, 0)
(2222, 2223, 0)
(2223, 2222, 0)
(2223, 2224, 0)
(2224, 2223, 0)
(2224, 2225, 0)
(2225, 2224, 0)
(2225, 2226, 0)
(2226, 2225, 0)
(2226, 2227, 0)
(2227, 2226, 0)
(2227, 2228, 0)
(2228, 2227, 0)
(2228, 2229, 0)
(2229, 2228, 0)
(2229, 2230, 0)
(2230, 2229, 0)
(2231, 2232, 0)
(2231, 1911, 0)
(2231, 2551, 0)
(2232, 2231, 0)
(2232, 2233, 0)
(2232, 1912, 0)
(2232, 2552, 0)
(2233, 2232, 0)
(2233, 2234, 0)
(2233, 1913, 0)
(2233, 2553, 0)
(2234, 2233, 0)
(2234, 2235, 0)
(2234, 1914, 0)
(2234, 2554, 0)
(2235, 2234, 0)
(2235, 2236, 0)
(2235, 1915, 0)
(2235, 2555, 0)
(2236, 2235, 0)
(2236, 2237, 0)
(2236, 1916, 0)
(2236, 2556, 0)
(2237, 2236, 0)
(2237, 2238, 0)
(2237, 1917, 0)
(2237, 2557, 0)
(2238, 2237, 0)
(2238, 2239, 0)
(2238, 1918, 0)
(2238, 2558, 0)
(2239, 2238, 0)
(2239, 1919, 0)
(2239, 2559, 0)
(2240, 2241, 0)
(2240, 1920, 0)
(2240, 2560, 0)
(2241, 2240, 0)
(2241, 2242, 0)
(2241, 1921, 0)
(2241, 2561, 0)
(2242, 2241, 0)
(2242, 2243, 0)
(2242, 1922, 0)
(2242, 2562, 0)
(2243, 2242, 0)
(2243, 2244, 0)
(2243, 1923, 0)
(2243, 2563, 0)
(2244, 2243, 0)
(2244, 2245, 0)
(2244, 1924, 0)
(2244, 2564, 0)
(2245, 2244, 0)
(2245, 2246, 0)
(2245, 1925, 0)
(2245, 2565, 0)
(2246, 2245, 0)
(2246, 2247, 0)
(2246, 1926, 0)
(2246, 2566, 0)
(2247, 2246, 0)
(2247, 2248, 0)
(2247, 1927, 0)
(2247, 2567, 0)
(2248, 2247, 0)
(2248, 2249, 0)
(2248, 1928, 0)
(2248, 2568, 0)
(2249, 2248, 0)
(2249, 2250, 0)
(2249, 1929, 0)
(2249, 2569, 0)
(2250, 2249, 0)
(2250, 2251, 0)
(2250, 1930, 0)
(2250, 2570, 0)
(2251, 2250, 0)
(2251, 2252, 0)
(2251, 1931, 0)
(2251, 2571, 0)
(2252, 2251, 0)
(2252, 1932, 0)
(2252, 2572, 0)
(2253, 2573, 0)
(2254, 2574, 0)
(2259, 1939, 0)
(2261, 1941, 0)
(2264, 2265, 0)
(2265, 2264, 0)
(2265, 2266, 0)
(2266, 2265, 0)
(2266, 2267, 0)
(2267, 2266, 0)
(2267, 2268, 0)
(2268, 2267, 0)
(2268, 2269, 0)
(2269, 2268, 0)
(2269, 2270, 0)
(2270, 2269, 0)
(2270, 2271, 0)
(2271, 2270, 0)
(2271, 2272, 0)
(2272, 2271, 0)
(2272, 2273, 0)
(2273, 2272, 0)
(2273, 2274, 0)
(2274, 2273, 0)
(2274, 2275, 0)
(2275, 2274, 0)
(2275, 2276, 0)
(2276, 2275, 0)
(2276, 2277, 0)
(2277, 2276, 0)
(2277, 2278, 0)
(2278, 2277, 0)
(2278, 2279, 0)
(2279, 2278, 0)
(2279, 2280, 0)
(2280, 2279, 0)
(2280, 2281, 0)
(2281, 2280, 0)
(2281, 2282, 0)
(2282, 2281, 0)
(2282, 2283, 0)
(2283, 2282, 0)
(2283, 2284, 0)
(2284, 2283, 0)
(2284, 2285, 0)
(2285, 2284, 0)
(2285, 2286, 0)
(2286, 2285, 0)
(2286, 2287, 0)
(2287, 2286, 0)
(2287, 2288, 0)
(2288, 2287, 0)
(2288, 2289, 0)
(2289, 2288, 0)
(2289, 2290, 0)
(2290, 2289, 0)
(2290, 2291, 0)
(2291, 2290, 0)
(2291, 2292, 0)
(2292, 2291, 0)
(2292, 2293, 0)
(2293, 2292, 0)
(2293, 2294, 0)
(2294, 2293, 0)
(2294, 2295, 0)
(2295, 2294, 0)
(2295, 2296, 0)
(2296, 2295, 0)
(2296, 2297, 0)
(2297, 2296, 0)
(2297, 2298, 0)
(2298, 2297, 0)
(2298, 2299, 0)
(2299, 2298, 0)
(2299, 2300, 0)
(2300, 2299, 0)
(2300, 2301, 0)
(2301, 2300, 0)
(2301, 2302, 0)
(2302, 2301, 0)
(2302, 2303, 0)
(2303, 2302, 0)
(2303, 2304, 0)
(2304, 2303, 0)
(2304, 2305, 0)
(2305, 2304, 0)
(2305, 2306, 0)
(2306, 2305, 0)
(2306, 2307, 0)
(2307, 2306, 0)
(2307, 2308, 0)
(2308, 2307, 0)
(2308, 2309, 0)
(2309, 2308, 0)
(2309, 2310, 0)
(2310, 2309, 0)
(2310, 2311, 0)
(2311, 2310, 0)
(2311, 2312, 0)
(2312, 2311, 0)
(2312, 2313, 0)
(2313, 2312, 0)
(2313, 2314, 0)
(2314, 2313, 0)
(2314, 2315, 0)
(2315, 2314, 0)
(2315, 2316, 0)

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-55-54285e1d75d7> in <module>
      2 g = load_image_and_make_graph('test-pic.png')
      3 print('Running MST algorithm')
----> 4 (mst_edges, mst_weight) = compute_mst(g)
      5 print(f'Found MST witn {len(mst_edges)} edges and total weight = {mst_weight}')
      6 max_mst_edge_weight= max(mst_edges, key=lambda e: e[2])

<ipython-input-50-98b2603c7a9c> in compute_mst(g)
     13     for edge in g.edges:
     14         print(edge)
---> 15         if (d.find(edge[0]) != d.find(edge[1])) and (len(d.dictionary_of_sets())>1):
     16             mst_edges.append(edge)
     17             mst_weight += edge[2]

<ipython-input-15-8b560d32a195> in dictionary_of_sets(self)
     15         for i in range(self.n):
     16             if self.is_representative(i):
---> 17                 d[i] = set([i])
     18         for j in range(self.n):
     19             if self.parents[j] != None:

KeyboardInterrupt:

In [56]:

Copied!





import numpy as np


    
def visualize_components(orig_image, g, components_dict):
    (w,h,channels) = orig_image.shape
    new_image = np.zeros((w, h, channels), np.uint8)
    count = 0
    delta = 10
    for (key, vertSet) in components_dict.items():
        if len(vertSet) >= 10: 
            (i,j) = g.get_vertex_data(key)
            rgb_px = orig_image[j,i]
            rgb_color = (int(rgb_px[0]), int(rgb_px[1]), int(rgb_px[2]))
            count = count+1          
            for s in vertSet:
                (i,j) = g.get_vertex_data(s)
                cv2.circle(new_image,(i,j), 1, rgb_color, -1) 
    return new_image
import numpy as np


    
def visualize_components(orig_image, g, components_dict):
    (w,h,channels) = orig_image.shape
    new_image = np.zeros((w, h, channels), np.uint8)
    count = 0
    delta = 10
    for (key, vertSet) in components_dict.items():
        if len(vertSet) >= 10: 
            (i,j) = g.get_vertex_data(key)
            rgb_px = orig_image[j,i]
            rgb_color = (int(rgb_px[0]), int(rgb_px[1]), int(rgb_px[2]))
            count = count+1          
            for s in vertSet:
                (i,j) = g.get_vertex_data(s)
                cv2.circle(new_image,(i,j), 1, rgb_color, -1) 
    return new_image

In [57]:

Copied!





W0 = 0.01* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen
W0 = 0.01* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen 

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-57-edce9cfdd605> in <module>
----> 1 W0 = 0.01* max_mst_edge_weight[2]
      2 res = compute_scc(g, W0)
      3 print(f'Found {len(res)} components')
      4 print('Showing components with at least 10 vertices')
      5 new_img= visualize_components(img, g, res)

NameError: name 'max_mst_edge_weight' is not defined

In [ ]:

Copied!





W0 = 0.02* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen
W0 = 0.02* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen 

In [ ]:

Copied!





W0 = 0.03* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
new_img= visualize_components(img, g, res)
print('Showing components with at least 10 vertices')
plt.imshow(new_img) # show the image on the screen
W0 = 0.03* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
new_img= visualize_components(img, g, res)
print('Showing components with at least 10 vertices')
plt.imshow(new_img) # show the image on the screen 

In [ ]:

Copied!





W0 = 0.04* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen
W0 = 0.04* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen 

In [ ]:

Copied!





W0 = 0.05* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen
W0 = 0.05* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen 

In [ ]:

Copied!





W0 = 0.07* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen
W0 = 0.07* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen 

In [ ]:

Copied!





W0 = 0.1* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen
W0 = 0.1* max_mst_edge_weight[2]
res = compute_scc(g, W0)
print(f'Found {len(res)} components')
print('Showing components with at least 10 vertices')
new_img= visualize_components(img, g, res)
plt.imshow(new_img) # show the image on the screen 

Problem 1¶

Problem 2¶

2A: Use union-find data-structures to compute strongly connected components.¶

2B Compute Minimum Spanning Tree¶

2C: Edge Threshold to Disconnect a Graph¶

Topological Data Analysis on Images (Not part of the Assignment -- just in case you are curious).¶

That's all Folks!¶