YASS -- Yet Another Scheduler Simulator

Objectives:

  • Take a set of jobs (htc or hpc), and simulate their execution on a fixed set of compute jobs.
  • For scheduling, use First-Come-Frist-Serve (FCFS) algorithm with backfilling (no fair-sharing and gang-scheduling; similar to SLURM's scheduling with sched/backfill configuration).
  • Record enough information through the execution, to evaluate different preemption policies with respect to the amount of wasted cycles.

Tunable parameters:

  • Mode: hpc, htc, or peregrine.
  • Number of nodes in the cluster (set when Cluster object is created).
  • Number of nodes that will be preempted (set when Cluster object is created; default: 50% of cluster nodes).
  • Experiment duration -- run execution until all jobs complete or this time limited is exceeded (passed as a parameter in Evaluation.run()).

Imports and contol variables

In [4]:
%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import sys, os, random
import seaborn as sns
from collections import OrderedDict
import random
import operator
from copy import deepcopy

# Define the mode of operation:
# htc - run single-node jobs
# hpc - run multi-node jobs
# peregrine - run jobs from Peregrine system
MODE = "peregrine"

# Number of times jobs from the selected workload are repeated (and shuffled in the final list)
JOB_REPEAT_COUNT = 1

# Standard figure size
FSIZE = (10,4)

# Perform error checking 
if not MODE in set(["hpc", "htc", "peregrine"]):
    print "Error: specified incorrect mode of operation"
    sys.exit(1)

Run simulation (this might take a long time)

  • During simulation, progress is reported in the form: "simulated_time_in_seconds..." at moments when one of the jobs finishes.
  • Results of the simulation are saved to: wasted_cycles.csv, preemptions.csv, and job_execution.csv.
In [27]:
jobs_dir = "jobs_" + MODE + "/"

# Iterate through each jobs, index - Order
#for index, row in jobs.iterrows():
#    print index, row["Runtime"], row["NodeCount"]

class Workload(object):
    def __init__(self, jobs_dir):
        self.jobs_dir = jobs_dir
        self.jobs = pd.read_csv(jobs_dir + "summary.csv")
        
        if MODE == "htc":
            #print self.jobs.head()
            #print self.jobs.tail()
            pass
        
        if MODE == "hpc":
            # For comparison only use the specified number of jobs
            # self.jobs = self.jobs.iloc[:200]
            pass
        
        if MODE == "peregrine":
            total_job_count = len(self.jobs)
            self.jobs = self.jobs.loc[(self.jobs["NodeCount"] <= 20) & (self.jobs["Runtime"] <= 24*3600.0) & \
                                      (self.jobs["Runtime"] >= 0.01)]
            print "Selected Peregrine jobs: %d out of %d" % (len(self.jobs), total_job_count)
        
        if JOB_REPEAT_COUNT > 1:
            print "Original job count: ", len(self.jobs)
            # Add shuffled copies of jobs to make the workload longer
            all_jobs = pd.DataFrame()
            for i in range(JOB_REPEAT_COUNT):
                new_jobs = self.jobs.iloc[np.random.permutation(len(self.jobs))]
                all_jobs = all_jobs.append(new_jobs)
            all_jobs.reset_index(drop=True, inplace=True)
            all_jobs['Order'] = all_jobs.index
            self.jobs = all_jobs
            print "New job count: ", len(self.jobs)
        
        # Print job stats
        print self.jobs.describe()
        total_node_hours = 0.0
        for idx, j in self.jobs.iterrows():
            total_node_hours += j["NodeCount"] * j ["Runtime"] / 3600.0
        print "Total node-hours in the selected workload: %f" % total_node_hours
        
        self.jobs = self.jobs.set_index("Order")
        self.jobs["NodeCount"] = self.jobs["NodeCount"].astype(int)
        self.jobs["State"] = "P"
        self.jobs["Started"] = ""
        self.jobs["Completed"] = ""

class Cluster(object):
    
    def __init__(self, node_count, preempt_count=None):
        """
        self.nodes -- dict where keys are node names and values are elapsed time for the running job or -1 for idle
                        (if not -1, always growing to corresponding job total runtims)
        self.running_jobs -- dict where keys are jobs IDs and the values are dicts:
            "Runtime": xxx - total runtime for this job (fixed for each job)
            "Elapsed": xxx - time it has been running so far (growing up to "Runtime")
            "NodeCount": xxx - number of nodes used by this jobs
            "Nodes": [xxx,yyy,zzz] - list of names of the nodes used by this job
        """
        self.node_count = node_count
        self.nodes = OrderedDict([ ("node-%d" % id, -1) for id in range(self.node_count) ])
        self.idle_node_set = set([ "node-%d" % id for id in range(self.node_count)]) 
        self.running_jobs = OrderedDict()
        if not preempt_count:
            self.preempt_count = int(self.node_count / 2.0)
        
    def place_job(self, job_id, job_runtime, job_node_count):
        """
        Simulate scheduling and executing a job
        If a job with given attributes can be executed: update node structures and return true
        Otherwise, return false
        """
        if len(self.idle_node_set) == 0:
            return False
        candidates = list(self.idle_node_set)
        if len(candidates) < job_node_count:
            return False
        else:
            # print "Node count", job_node_count
            selected_nodes = candidates[:int(job_node_count)]
            # print "Job %d started on nodes: %s" % (job_id, str(selected_nodes))
            for node in selected_nodes:
                self.nodes[node] = 0.0  
                self.idle_node_set.remove(node)
                self.running_jobs[job_id] = {"Runtime": job_runtime, "Elapsed": 0.0, \
                                             "NodeCount": job_node_count, "Nodes": selected_nodes}
            return True
    
    def fast_forward(self, starting_time, show_progress=True):
        """
        Simulate running all jobs until the first one finishes.
        Returns time to the moment when the next job will finish and the list of IDs of the finished job,
        subtract that time from runtimes for 
        all jobs and nodes, and free up the nodes for the finished jobs
        """
        # Find min remaining time across all jobs
        time_step = min([job["Runtime"] - job["Elapsed"] for id, job in self.running_jobs.items()])
        # print "Moving forward by %d seconds from state of running jobs %s" % (time_step, self.running_jobs) 
        # print "Moving forward by %d seconds" % (time_step) 
        if time_step < 0:
            print "Error: moving back in time!"
            sys.exit(1)
        
        # within time_step interval no job will finish; simulate policy evaluation with currently running jobs
        PolicyEval.evaluate(self.preempt_count, self.nodes, self.running_jobs, starting_time, time_step)
        
        finished_jobs = []
        for id, job in self.running_jobs.items():
            job["Elapsed"] += time_step
            if abs(job["Runtime"] - job["Elapsed"]) < 0.001:
                # Consider finished 
                for node in job["Nodes"]:
                    self.nodes[node] = -1
                    self.idle_node_set.add(node)
                del self.running_jobs[id]
                # print "Job %d completed on nodes: %s" % (id, str(job["Nodes"]))
                finished_jobs.append(id)
            else:
                for node in job["Nodes"]:
                    self.nodes[node] += time_step
        
        if show_progress:
            sys.stdout.write("%d..." % starting_time)
            sys.stdout.flush()
        return time_step, finished_jobs  

class PolicyEval(object):
    # Class/static dataframe
    wasted_cycles = pd.DataFrame()
    preemptions = pd.DataFrame()
    grace_periods = [60,120,1200,1800]
    eval_counter = 0
    
    @staticmethod
    def evaluate(preemt_count, nodes, running_jobs, starting_time, duration, time_delta=30):

        # Evaluate every second
        for dt in range(0, int(duration), time_delta):

            # Simulate the state of nodes and jobs at curr_time + dt 
            
            # Nodes: if idle, leave idle; otherwise, fast forward by dt
            future_nodes =  OrderedDict([ (node, -1)  if elap == -1 else (node, elap + dt) \
                                                  for node, elap in nodes.items()]) 
            # Jobs: fast forward all jobs by dt
            future_running_jobs = deepcopy(running_jobs)
            for id, job in future_running_jobs.items():
                job["Elapsed"] += dt
            
            RANDOM_vec, RANDOM_nodes = PolicyEval.RANDOM(preemt_count, future_nodes, future_running_jobs)
            RANDOM_vec.update({"Policy": "RANDOM", "Time": starting_time + dt})
            
            # Simple, original version: estimate LIFO and FIFO separately
            #LIFO_vec, LIFO_nodes = PolicyEval.LIFO(preemt_count, future_nodes, future_running_jobs)
            #LIFO_vec.update({"Policy": "LIFO", "Time": starting_time + dt})
            #FIFO_vec, FIFO_nodes = PolicyEval.FIFO(preemt_count, future_nodes, future_running_jobs)
            #FIFO_vec.update({"Policy": "FIFO", "Time": starting_time + dt})
            # Optimized version: estimate LIFO and FIFO together and save some cycles by avoiding repeated sorts
            LIFO_vec, LIFO_nodes, FIFO_vec, FIFO_nodes = PolicyEval.LIFO_and_FIFO(preemt_count, future_nodes, future_running_jobs)
            LIFO_vec.update({"Policy": "LIFO", "Time": starting_time + dt})
            FIFO_vec.update({"Policy": "FIFO", "Time": starting_time + dt})
            
            PAP_vec, PAP_nodes = PolicyEval.PAP(preemt_count, future_nodes, future_running_jobs)
            PAP_vec.update({"Policy": "PAP", "Time": starting_time + dt})
            
            PolicyEval.preemptions = PolicyEval.preemptions.append(pd.DataFrame([RANDOM_vec, LIFO_vec, FIFO_vec, PAP_vec])) 
                
            for gp in PolicyEval.grace_periods:
                RANDOM_wc = PolicyEval.get_wasted_cycles(future_running_jobs, RANDOM_nodes, gp) 
                LIFO_wc = PolicyEval.get_wasted_cycles(future_running_jobs, LIFO_nodes, gp) 
                FIFO_wc = PolicyEval.get_wasted_cycles(future_running_jobs, FIFO_nodes, gp) 
                PAP_wc = PolicyEval.get_wasted_cycles(future_running_jobs, PAP_nodes, gp) 
        
                PolicyEval.wasted_cycles = PolicyEval.wasted_cycles.append(pd.DataFrame([ {"Policy": "RANDOM", "GracePeriod": gp ,"Time": starting_time + dt, "WastedCycles": RANDOM_wc},
                                                                                         {"Policy": "LIFO", "GracePeriod": gp, "Time": starting_time + dt, "WastedCycles": LIFO_wc},
                                                                                         {"Policy": "FIFO", "GracePeriod": gp, "Time": starting_time + dt, "WastedCycles": FIFO_wc},
                                                                                         {"Policy": "PAP", "GracePeriod": gp, "Time": starting_time + dt, "WastedCycles": PAP_wc} ])) 
        PolicyEval.eval_counter += 1
        # Periodically save eval results 
        if PolicyEval.eval_counter % 100 == 0 and PolicyEval.eval_counter > 0:
            PolicyEval.save()
            
        
    @staticmethod
    def RANDOM(preemt_count, nodes, running_jobs):
        """ 
        Given running jobs and node states, decide on what nodes to kill according to the RANDOM policy.
        Random policy igores the runtimes.
        
        Returned:
        - p_vec -- preemption_vector (dict) where keys are nodes and values are preemption values in [0,1]
        - p_nodes -- preempted_nodes, list with preemt_count nodes that should be preempted
        """
        
        p_vec = OrderedDict([(node,random.uniform(0, 1)) for node in nodes.keys()])
        
        # Proper version: sort by value, get keys, and only select the necessary number
        # p_nodes = [pair[0] for pair in sorted(p_vec.items(), key=operator.itemgetter(1))][:preemt_count] 
        
        # Optimized version: ignore assigned values, return random sample
        p_nodes = random.sample(p_vec.keys(), preemt_count)
        return p_vec, p_nodes   
    
    @staticmethod
    def LIFO(preemt_count, nodes, running_jobs):
        """ 
        Given a row from monitor data, decide on what nodes to kill according to the LIFO policy.
        LIFO, last-in-first-out policy, creates preemption vectors based on current job runtimes:
        the longer a job has been running, the higher the value of the node it is running on is.
        
        Deletion is simulated by ranking the available nodes according to this policy,
        and selecting the specified number of nodes at the beginning of the list (sorted in the value-ascending order).
        Preemption vectors takes form of a dict: {<node>:<value>}
        List of deleted nodes is returned.
        
        Returned:
        - p_vec -- preemption_vector (dict) where keys are nodes and values are preemption values in [0,1]
        - p_nodes -- preempted_nodes, list with preemt_count nodes that should be preempted
        """
        tmp = deepcopy(nodes)        
        for node in tmp.keys():
            if tmp[node] == -1:
                tmp[node] = 0
        # Sort by value
        tmp = sorted(tmp.items(), key=operator.itemgetter(1))
        # Scale -- divide by the largest value (if not zero)
        max_elapsed = tmp[-1][1]
        if abs(max_elapsed) > 0.0001:
            p_vec = OrderedDict([ (node,elap/max_elapsed) for node,elap in tmp])
        else:
            p_vec = OrderedDict(tmp)
        
        p_nodes = p_vec.keys()[:preemt_count] 
        return p_vec, p_nodes 
    
    @staticmethod
    def FIFO(preemt_count, nodes, running_jobs):
        """ 
        Given a row from monitor data, decide on what nodes to kill according to the FIFO policy.
        FIFO, first-in-first-out policy, creates preemption vectors based on current job runtimes:
        the longer a job has been running, the lower the value of the node it is running on is.
        
        Deletion is simulated by ranking the available nodes according to this policy,
        and selecting the specified number of nodes at the beginning of the list (sorted in the value-descending order).
        Preemption vectors takes form of a dict: {<node>:<value>}
        List of deleted nodes is returned.
        
        Returned:
        - p_vec -- preemption_vector (dict) where keys are nodes and values are preemption values in [0,1]
        - p_nodes -- preempted_nodes, list with preemt_count nodes that should be preempted
        """
        tmp = deepcopy(nodes)
        for node in tmp.keys():
            if tmp[node] == -1:
                tmp[node] = 0
        # Sort by value
        tmp = sorted(tmp.items(), key=operator.itemgetter(1))
        # Scale -- divide by the largest value (if not zero)
        max_elapsed = tmp[-1][1]
        if abs(max_elapsed) > 0.0001:
            p_vec = OrderedDict([ (node,1.0-elap/max_elapsed) for node,elap in tmp ])
        else:
            # all values are zeros
            p_vec = OrderedDict([ (node,1.0) for node,elap in tmp ])
        
        # last preemt_count elements in the list
        p_nodes = p_vec.keys()[-preemt_count:] 
        return p_vec, p_nodes
    
    @staticmethod
    def LIFO_and_FIFO(preemt_count, nodes, running_jobs):
        """
        Optimized version that combines two previous functions
        """
        # This part is the same for both LIFO and FIFO
        tmp = dict([ (node,0.0) if elap == -1 else (node,elap) for node, elap in nodes.items() ]) 
        # Sort by value
        tmp = sorted(tmp.items(), key=operator.itemgetter(1))
        # Scale -- divide by the largest value (if not zero)
        max_elapsed = tmp[-1][1]
        
        # Policy-specific operations
        if abs(max_elapsed) > 0.0001:
            LIFO_vec = OrderedDict([ (node,elap/max_elapsed) for node,elap in tmp])
            FIFO_vec = OrderedDict([ (node,1.0-elap/max_elapsed) for node,elap in tmp])
        else:
            LIFO_vec = dict(tmp)
            FIFO_vec = {node:1.0 for node,elap in tmp}
        
        LIFO_nodes = LIFO_vec.keys()[:preemt_count] 
        FIFO_nodes = FIFO_vec.keys()[-preemt_count:] 
        return LIFO_vec, LIFO_nodes, FIFO_vec, FIFO_nodes 
    
    @staticmethod
    def PAP(preemt_count, nodes, running_jobs):
        """ 
        Given a row from monitor data, decide on what nodes to kill according to the PAP policy.
        PAP, Parallel-Aware Preemption policy, creates preemption vectors based on current job runtimes --
        the longer a job has been running, the lower the value of the node it is running on is --
        and the number of nodes used by each job.
        
        Deletion is simulated by ranking the available nodes according to this policy,
        and selecting the specified number of nodes at the beginning of the list (sorted in the value-descending order).
        Preemption vectors takes form of a dict: {<node>:<value>}
        List of deleted nodes is returned.
        
        Returned:
        - p_vec -- preemption_vector (dict) where keys are nodes and values are preemption values in [0,1]
        - p_nodes -- preempted_nodes, list with preemt_count nodes that should be preempted
        """
        # Include idle nodes 
        tmp = {node:0.0 for node, elap in nodes.items() if elap == -1}
        # Include loaded nodes
        for id, job in running_jobs.items():
            total_elapsed = job["NodeCount"] * job["Elapsed"]
            for node in job["Nodes"]:
                tmp[node] = total_elapsed
        
        tmp = sorted(tmp.items(), key=operator.itemgetter(1))
        # Scale -- divide by the largest value (if not zero)
        max_elapsed = tmp[-1][1]
        if abs(max_elapsed) > 0.0001:
            p_vec = OrderedDict([ (node,elap/max_elapsed) for node,elap in tmp])
        else:
            p_vec = OrderedDict(tmp)
        
        p_nodes = p_vec.keys()[:preemt_count] 
        return p_vec, p_nodes 
     
    @staticmethod    
    def get_wasted_cycles(running_jobs, preemted_nodes, grace_period):
        total = 0
        p_set = set(preemted_nodes)
        for id, job in running_jobs.items():
            # If find this intersection, the entire job will be preempted
            if len(set(job["Nodes"]) & p_set):
                if grace_period < job['Runtime'] - job['Elapsed']:
                    # currently running job won't finish before the end of grace period
                    total += job["NodeCount"] * (job["Elapsed"] + grace_period)
        return total
    
    @staticmethod
    def save():
        PolicyEval.wasted_cycles.to_csv("wasted_cycles.csv")
        PolicyEval.preemptions.to_csv("preemptions.csv")

class Execution(object):
    
    def __init__(self, cluster, workload):
        self.cluster = cluster
        self.workload = workload
        self.timer = 0
        self.timer_when_no_pending_jobs = 0
        self.is_timer_when_no_pending_jobs_set = False
        
    def run(self, terminate_at_timer=None):
        while True: 
            #print "Time: %f" % self.timer
            if terminate_at_timer and self.timer >= terminate_at_timer:
                print "Stopping because specified time exceeded"
                break
            
            pending_jobs = self.workload.jobs[self.workload.jobs["State"]=="P"]
            if (len(pending_jobs) == 0) and (not self.is_timer_when_no_pending_jobs_set):
                self.timer_when_no_pending_jobs = self.timer
                self.is_timer_when_no_pending_jobs_set = True
                
            # print "Number of pending jobs: %d" % len(pending_jobs) 
            
            if len(self.workload.jobs[self.workload.jobs["State"] != "C"]) == 0:
                print "All jobs completed. Finish execution"
                break
                
            placed_any = False
            # Scheduling phase
            for id, job in pending_jobs.iterrows():
                placed = self.cluster.place_job(id, job["Runtime"], job["NodeCount"])       
                if placed:
                    placed_any = True
                    self.workload.jobs.set_value(id, 'State', "R")
                    self.workload.jobs.set_value(id, 'Started', self.timer)
                if len(self.cluster.idle_node_set) == 0:
                    # Can't schedule any more jobs
                    break
            
            # Time-stepping phase
            if self.cluster.running_jobs:
                time_step, finished_jobs = self.cluster.fast_forward(starting_time=self.timer) 
                self.timer += time_step
                for id in finished_jobs:
                    self.workload.jobs.set_value(id, 'State', "C")
                    self.workload.jobs.set_value(id, 'Completed', self.timer)
        
        # End of execution
        PolicyEval.save()
                    
w = Workload(jobs_dir)
c = Cluster(20)
x = Execution(c, w)
x.run()
w.jobs.to_csv('job_execution.csv')

print "Final value of timer: %f seconds (%f hours)" % (x.timer, x.timer/3600.0)
print "Time when number of pending job is zero: %f seconds (%f hours)" % (x.timer_when_no_pending_jobs, x.timer_when_no_pending_jobs/3600.0)
Selected Peregrine jobs: 7275 out of 7275
        Unnamed: 0        Order    NodeCount       Runtime  exit_code  \
count  7275.000000  7275.000000  7275.000000   7275.000000     7275.0   
mean   5015.200962  5015.200962     1.419656   7119.068591        0.0   
std    2883.351141  2883.351141     1.193868  12797.274658        0.0   
min       0.000000     0.000000     1.000000     33.000000        0.0   
25%    2525.000000  2525.000000     1.000000    439.500000        0.0   
50%    5022.000000  5022.000000     1.000000   1921.000000        0.0   
75%    7509.500000  7509.500000     1.000000   6840.500000        0.0   
max    9994.000000  9994.000000    16.000000  85945.000000        0.0   

       wallclock_used_seconds  wallclock_req_seconds  \
count             7275.000000            7275.000000   
mean              7119.068591           69039.202474   
std              12797.274658           90473.311734   
min                 33.000000              30.000000   
25%                439.500000           14400.000000   
50%               1921.000000           57600.000000   
75%               6840.500000           57600.000000   
max              85945.000000          864000.000000   

       wallclock_to_runtime_ratio  
count                 7275.000000  
mean                   164.564370  
std                    961.663054  
min                      0.015291  
25%                      5.174273  
50%                     19.057702  
75%                     66.666667  
max                  21600.000000  
Total node-hours in the selected workload: 26838.580000
0...36...38...77...93...148...157...225...301...350...421...442...474...482...553...606...784...1049...1503...1648...1663...2064...2191...2317...2372...2401...2608...2823...2936...4039...4083...4310...4351...4559...4571...4826...4838...5026...5930...6382...6866...7034...7258...7430...7730...7869...8081...8434...8438...8465...9361...9398...9406...9466...10047...10110...10255...10323...10511...10613...10720...10892...11544...11915...12624...13695...13705...13719...13978...14482...14660...14716...14756...14845...15020...15205...16441...16515...16869...16938...17113...17162...17354...17458...17503...17759...17777...17829...18148...18268...18425...18565...19025...19730...19862...19907...19946...20038...20255...20507...20926...21111...21763...22375...22634...22759...22820...23091...23271...23288...23601...24249...24387...24919...24993...25723...26868...26990...27283...27403...27464...28200...28990...29100...29833...31161...31236...31461...31629...31797...32097...32725...33948...34042...34230...34260...34555...34650...34675...34714...34761...34902...35004...35036...35142...35460...35494...36048...36102...36513...36738...36877...37081...37108...37151...37469...37585...38500...39011...40147...40255...40263...40314...40421...40568...40823...40879...41220...41587...41796...41951...42513...42716...43010...43207...44152...44214...44597...44710...45008...45289...45314...45603...45719...45958...48455...49379...49476...50293...51141...52014...52212...52414...52884...53309...53602...54867...55817...56566...56833...56865...57296...57476...57521...57538...57625...57698...57805...58123...58402...58723...58791...59677...60226...60802...61384...61550...62420...62587...63527...64048...64913...65044...65279...65412...65687...66433...67182...67349...68675...69379...69456...70067...70341...70451...70578...70751...71517...71549...71678...73215...73275...73316...73721...73820...73825...73962...74691...75001...75082...75099...75286...75850...76256...76635...76995...77163...77233...77565...77683...78373...78713...78810...79807...79833...79868...79902...81403...81579...81584...81808...82945...82989...83043...83155...83378...83405...83855...83913...84262...84613...84793...84978...86029...86260...86483...87130...87286...88385...88854...89006...89462...89750...89959...90333...90511...90615...90964...91034...91440...91583...91623...91704...91799...91865...91911...92137...92152...93251...94043...94206...94255...94536...94785...95051...95101...95527...95615...95665...95771...96155...96350...96515...97981...98125...98805...99048...99343...99364...99520...99723...100118...100270...100635...100657...100874...100909...100921...100970...101044...101380...101568...101649...102477...103082...103136...103189...103868...104391...105043...105201...106140...107508...108554...108727...108773...108997...109633...110690...110743...110901...111030...111095...111202...114303...114454...117793...118055...118137...118772...118828...119419...119651...119742...120039...120223...120389...120744...120777...120862...120903...121093...121124...121245...121471...121604...121659...121685...121791...121936...122197...122518...123364...124780...127808...127816...128070...128148...128424...130403...130572...131178...131377...131526...133007...133349...133586...134478...135064...136344...136632...136724...136977...137595...137692...138096...138245...139124...139164...139703...139856...140799...141366...141397...141932...142195...142568...142949...142970...143235...143304...143775...144181...144381...145285...145417...145440...145671...145726...145736...146534...148507...149678...150208...150417...150690...150961...151065...151636...151754...151763...152135...153033...153564...153686...153826...154174...154192...154236...154861...155090...155145...155507...155538...155609...155690...155843...155918...155953...155963...156284...156294...156357...157339...158516...158672...158684...158837...160537...160630...161697...161745...162296...162307...162678...163390...163608...164462...164959...165001...165045...165350...165567...165636...165722...165923...165947...165960...166325...166517...166625...166923...167260...167300...167665...167720...169877...170060...170327...170794...170998...171068...172051...172366...172788...173716...173834...174350...174701...175263...175327...175484...176173...176385...176504...176513...177069...177452...177641...178114...178852...178937...179472...179772...180053...180186...180891...181689...181774...181793...182012...182363...182858...183175...183290...183441...183773...183911...184271...184599...184810...184978...185151...185250...185419...185515...186079...186274...186554...186740...186838...187473...189286...189594...189991...190434...191226...191325...191759...191883...192004...192073...192971...193205...193411...193598...193910...193955...194752...196260...197917...198012...199407...199423...199553...199653...200164...200517...201219...201501...201789...201907...202049...202117...202242...203030...203261...203441...203698...203890...203941...204074...204497...205571...205623...205780...206131...206153...206290...206420...206481...208090...208502...209145...209819...209898...210108...210596...210939...212753...212791...213015...213381...213808...213966...214505...215696...216512...216828...218729...218881...219339...219342...219509...220621...221173...221226...221552...221580...221895...222327...222368...222615...222666...222773...223424...223671...223981...224633...224725...225274...225621...225999...229306...230422...231192...232450...233153...233183...233303...234521...234679...234829...235187...235673...236280...239045...239313...239338...239520...241471...241535...241732...241773...241779...241840...242296...242356...242540...242721...242924...243145...243303...243329...243791...243838...243896...244021...244086...244223...244286...244414...244416...244663...245863...246354...246592...246726...246744...246898...247399...247411...247852...247992...249204...249357...249500...250357...250466...250819...250983...251049...251163...251317...252309...252698...252726...252865...253246...253531...253772...253975...254685...254961...255147...255528...255831...256085...256127...256516...256616...256661...257215...257217...257266...257587...257722...258940...258950...259131...259360...259400...259641...259689...259969...259997...260149...260383...260767...260883...261100...261371...261636...261712...261764...261959...262248...263015...264159...264423...264886...265208...265456...266048...266216...266436...267062...267139...267506...267607...268025...268677...268806...268851...268942...268944...268962...269420...269921...269973...270321...270417...270468...271647...271793...271975...272022...272260...272611...272702...272824...273642...273881...273927...274097...274237...275279...275583...275811...277348...277708...277792...278175...278379...278625...278737...278812...279398...280237...280342...280531...280724...281722...282479...282513...282660...282823...283771...284358...284687...284791...285004...285345...286503...287073...287250...287408...287529...287903...287948...289024...289224...289327...289462...289494...289535...289693...289975...290086...290277...290513...291125...292601...293034...293835...294179...294490...295704...295924...296811...297194...297241...297492...297683...297816...297836...297885...298292...298417...298713...299706...299807...299867...299955...300189...300321...300423...300474...301141...301359...301880...301914...302160...302189...302250...302383...302789...302806...303045...303127...303480...303543...303937...304429...304819...304922...305061...305360...305544...305623...305642...306078...306715...308335...308614...309194...309691...310416...310522...311356...311414...312112...312262...312563...313027...313909...314234...314669...315194...315461...315657...318521...320074...320803...320895...322040...322140...323370...323416...324244...325172...325910...326084...326381...326524...328229...328349...328840...329176...329300...329820...330031...330914...330939...331124...331214...331892...332109...332162...332236...332849...333193...333328...334008...334487...334898...335187...335258...335387...335760...335804...335913...335938...335978...335989...336153...336444...336480...337972...338134...338203...338217...338359...338494...338497...338547...338549...339280...339977...340046...341795...342329...342424...343820...343930...343978...344902...345406...346533...347170...347211...347524...347806...347945...347992...348103...348554...348683...349355...350373...351075...351647...352770...352896...352935...353410...353523...353689...354003...354194...354591...354719...354959...355298...355565...355667...355746...355815...355818...355869...355923...356373...356782...357044...357168...357228...357730...358401...358491...358586...358840...359551...360260...360615...360868...361054...361207...361607...362288...363173...363610...363826...363943...363975...364224...364922...364999...365026...365775...365920...365923...365942...365977...366041...366256...366268...366410...366447...366722...367402...367646...367735...367876...368398...368441...369042...369097...369172...370246...370257...370369...370779...371314...371418...371867...372073...372174...372534...372638...372691...372939...373399...373626...374454...374869...375253...375370...375877...376170...376780...376973...377475...377532...378250...378491...378843...379995...380541...382067...382425...383484...383578...383694...383885...385393...385638...385935...386058...386450...386819...387032...387123...387315...387783...387845...387895...388102...388450...388584...388728...388810...389089...389119...390533...391157...391803...393470...394202...394969...395056...395211...396416...397149...397532...398395...399321...399872...399925...400536...401101...402025...402075...402337...402360...402401...402522...402528...402579...405552...405744...406019...406066...406397...406510...406663...407658...407768...408690...408846...408968...409112...409335...409450...410443...410447...410649...410985...411338...412377...413363...413896...413929...414551...414933...415679...416133...416223...416427...416846...416892...418022...418856...419053...420070...420698...420964...420983...421088...421370...421406...422201...422291...422345...422525...422712...423910...424002...425057...426879...427868...429291...430101...430259...430530...430562...430632...430677...430996...431123...432323...433539...434953...436538...437268...437759...438165...439594...440079...440152...441639...442281...442523...443332...443593...443977...444482...444613...444799...444910...445583...447775...447816...447969...448114...448370...448714...448773...448815...449646...449720...449932...450355...450445...450495...450754...451409...451643...451910...452212...452454...452941...452962...453156...453263...453269...453367...453827...454428...454593...455408...455707...455964...456143...457558...457853...457920...458470...458942...459292...459324...459405...459474...459478...459772...459812...459893...459925...460802...460859...461034...461157...462147...462193...463064...463281...463339...463343...463887...464855...464945...465096...465098...465324...465463...465604...465695...466236...466844...467111...467138...467369...467578...467957...468056...468205...468975...469321...471564...472298...472959...473158...473248...473286...473559...474356...474790...475144...475530...475810...477128...477837...477878...478798...479201...479277...479497...481517...481563...481885...483816...484061...485443...485589...485894...485905...486223...486653...486713...487906...488199...488865...489277...490048...490068...490367...490989...492127...493023...493166...493286...494213...496826...498604...498621...498755...498972...499188...499830...499851...499859...499898...500114...500969...501568...502032...502727...503246...503586...504653...505209...505248...505333...505509...506345...506504...506539...506553...507014...507476...507762...507982...508198...508313...509725...510326...510584...510712...510760...510954...511131...511193...511629...511933...512145...512699...513730...513868...514101...514700...515502...515840...516136...518672...519343...519368...519373...519450...519565...519623...519640...520145...520156...520277...520726...520973...521023...521250...521534...522043...522057...522363...523178...523269...523933...524029...524084...524507...524930...525208...525281...525718...525853...525994...526025...526222...526762...526912...526995...527248...527266...527660...527667...527758...527864...528102...528168...528383...528500...528692...529378...529448...530088...530171...530196...530475...530544...530603...531344...532982...533125...533206...533313...533354...535339...535998...536058...536252...537272...537400...537409...538005...538804...538987...539062...539144...539695...541590...542137...543020...543148...543883...544041...545027...545041...545094...547446...548329...548785...549251...549272...549536...549597...549945...550126...550333...550813...551297...551646...552068...552998...554186...554213...554303...554340...554373...554532...554953...555514...557539...557784...558105...558241...558500...559099...559183...559482...559520...559622...559837...559904...561337...561631...564142...564190...564315...564367...564468...564496...564927...565883...565996...567091...567480...568316...568457...568551...568737...568835...568890...568939...569229...569385...569454...569784...570465...570747...571063...571887...573502...573756...573910...574443...574469...575501...576831...578626...579101...579419...580307...582501...582625...582937...583197...583249...583407...583580...583715...583927...584063...585200...585307...585638...587554...588082...589245...589756...589829...589876...590073...590184...590295...590865...591150...591489...591521...592361...592533...594062...594938...596030...597383...597601...598215...598953...601407...601716...601789...601810...602781...602894...603289...604519...604776...606258...606761...606887...607184...607418...607444...607689...607707...607712...607876...608262...608314...608401...608550...608665...608679...608948...609439...609629...609737...609789...610531...611038...611162...611814...613212...613641...613655...614149...614249...615062...615270...615479...615808...615960...616713...616982...617135...617207...617262...617489...617663...618300...618771...619800...620567...621488...621702...623164...623518...623551...623592...623824...624026...624097...624112...624510...625446...625467...625673...625748...626345...626351...626439...626880...626889...627106...627264...627530...628146...628148...628327...628425...628494...628631...628702...628739...628795...629108...629210...630006...630009...630225...630500...630622...630750...630842...630923...631036...631746...631856...632357...632554...633140...633677...634562...634927...636019...636061...636203...636368...636451...636633...637908...638048...638287...638463...638561...638586...638996...639129...639346...639403...639761...640332...640992...641281...641299...641355...641398...642012...642125...642160...643129...643529...644244...644569...646557...648128...648319...648409...648578...648673...648795...650375...651179...651294...651411...651460...651805...651929...652012...652050...652300...652414...653421...653820...654082...654110...654332...654367...654477...654900...654976...655516...655700...656144...657072...657179...657529...657670...657866...657939...658201...658468...660194...660277...660457...660476...660522...660532...660635...660926...661138...661821...661990...662033...662240...662396...662397...663136...663254...664306...664418...664850...665277...666637...666934...667143...668387...668462...670003...671382...671484...671725...672017...672109...672172...672326...672586...672683...672858...672986...673417...673851...673884...674176...674217...674622...675156...675194...675324...675480...675532...675742...676316...676370...676423...676510...676879...676971...677303...678176...678392...678551...678805...678927...679143...679358...679468...679580...679600...680004...680952...680990...681270...681361...681835...682580...682605...682760...683290...683310...683328...683339...683445...683494...683573...683746...683993...684098...684244...684329...684501...684807...684845...684916...685683...686633...686755...686806...686870...687107...687141...687153...687423...687851...688119...688271...688405...688515...688599...689106...689667...689672...689954...690103...691032...691081...691185...691287...691333...691368...692072...692287...692496...692632...693016...693061...693393...693586...693716...694788...694999...695969...696316...696513...697262...697907...698022...698076...698625...698652...698761...698883...698933...699768...699877...700183...700681...701971...702031...702787...703969...704180...704780...704893...705185...705706...705775...705964...706247...706608...706977...707634...707649...707679...707813...707861...707896...708010...708376...709001...710321...711343...711604...711798...711807...711985...712373...712399...712489...712718...714320...716086...716225...716556...717560...718066...719586...719842...719874...720885...720929...720978...721051...721406...721672...721999...722071...722270...722416...722913...723266...723359...724104...724268...724502...725794...726073...726556...726643...726678...726747...727160...727494...730001...730461...730572...731857...732309...732623...732958...732989...733611...733720...733759...734127...734178...734323...734544...734623...736258...736491...736824...737025...737338...737340...737753...738533...738656...738749...738819...739064...739103...739490...739951...740019...740051...740125...740255...740312...740628...740802...740869...741330...742024...743481...743912...744018...744161...744304...745251...745276...745296...745347...745503...745705...745957...746110...746243...746492...746617...746762...746899...747041...747067...747343...747362...747851...747991...748479...748840...749401...749822...749845...749976...750298...750661...750793...750953...751719...751774...751865...752123...752176...752286...752303...753236...753571...754663...754956...755119...755998...756220...756809...756883...756996...757082...757152...757510...758251...758312...758317...758338...758563...758592...758755...758805...759063...759384...760592...760595...760899...762987...763120...763261...763363...764443...764633...764802...765219...766566...766853...767004...767082...767170...767236...767566...768354...768465...768590...768593...768890...769132...769240...769447...769890...770229...770268...770302...770368...770684...770976...771048...771115...771975...772605...773020...773249...773393...773491...773713...774016...774715...774730...774938...775180...775830...776162...776309...777158...780212...780342...780913...781014...781272...781544...781606...781737...781801...782571...782723...782727...782728...782895...783043...783311...783549...783991...784414...785352...785578...785626...785864...786172...786605...786942...787120...787323...787629...787990...788048...788143...788383...788428...788647...790048...790114...790487...790491...790794...790800...791125...791169...791230...791764...791929...792091...792671...793078...793193...793332...793552...794319...795208...795349...796685...796971...797008...797184...797344...797378...798341...798870...800303...800680...801052...801679...802203...802322...802359...802644...803662...803677...803879...804249...804470...804536...806345...806567...806715...808484...808695...808736...808800...808938...809013...809085...809449...810227...811096...811628...812037...812534...812638...812942...813061...813918...814092...814244...814399...815087...815155...815558...815599...816047...816262...816468...816774...817020...817479...817589...817891...818708...818977...819234...820064...820162...820210...820261...820303...820496...821305...821326...821367...821588...821611...821774...821823...823156...825196...825267...825394...825441...825547...825645...825690...825842...825862...825893...826030...826651...827582...827591...828416...828574...828856...828996...829103...829652...829756...829770...829801...830791...831106...831253...831491...832749...835175...835228...835481...836136...836955...837051...837133...837240...837410...837954...838160...838748...838804...838892...839021...839716...839978...840840...840880...841041...841072...841270...841747...841974...842057...842149...842517...843385...843458...843620...843736...844072...844456...844516...844523...844561...844574...844674...844947...845288...846280...847215...847349...847531...847842...847938...848086...848610...848806...848809...849287...849660...849793...850046...850159...850265...850467...850909...851716...851935...851982...852181...852265...852502...852704...853049...853170...853863...854809...855410...856162...856228...856258...856869...856875...857166...857769...857792...857935...859828...859878...860654...860680...860978...861273...861382...862466...862619...863084...863123...863364...863627...863773...863818...863837...864000...864210...864287...865203...867036...867681...868187...868392...868400...868409...868464...868532...868958...869063...869150...869185...869276...869487...870038...870865...871339...871490...872474...872609...872940...873431...873968...873975...874110...874165...874220...874289...874476...874500...874766...875323...875712...875826...875930...876488...876528...877017...877682...877899...878068...878191...878267...878503...878520...878709...879448...879580...879784...879962...881091...881686...881720...881737...881850...882250...882840...883024...883201...883262...883635...883767...883805...883890...883986...884066...884156...884249...884324...884594...884679...884784...885132...886641...886713...886970...887603...887732...887984...888080...888340...888377...888402...888417...888580...888922...889015...889366...889372...889557...890585...891087...891306...891323...891370...891408...891553...891598...891704...892434...892456...892612...892711...893086...893608...893733...893840...894531...894900...895290...895695...896645...897615...897755...898277...898336...898381...898745...899088...899212...899424...899431...899652...899730...899865...899880...900066...900130...900552...901209...901352...901446...901586...901682...902308...903218...903239...904056...904307...904314...905802...906151...906525...906924...906964...907045...907169...907767...907944...908044...908190...909121...909162...909787...909896...910234...911123...911171...911532...911712...912255...912523...912626...912785...912839...912859...913000...913076...913102...913146...913205...913417...913504...913544...914315...915132...915360...915953...916293...917375...917384...917411...918062...918084...918145...918227...918323...918619...918655...920598...920608...920661...920964...921032...921078...921298...921456...921459...921744...921761...921834...922251...923700...923852...923907...923996...924054...924431...924435...924491...924634...924823...924829...925209...925615...925636...925823...925956...926004...926211...926342...926513...926637...926719...926777...926818...926834...926913...927681...928304...928344...928709...929708...931647...931882...932498...932515...932606...932752...933118...933364...933641...933737...934162...934713...935515...936829...937200...937684...938187...938527...938566...938610...939130...939468...939626...939906...940164...940608...940661...941485...941788...941979...942174...942189...942247...942254...942304...942409...942510...942694...943002...943311...944110...944252...944315...944494...944622...944936...945109...945642...946007...946035...946041...946289...947458...947513...947616...947706...947956...948004...948036...948550...949124...949535...949631...950643...950834...951376...951577...951866...952193...953334...953335...953568...954148...954400...954872...955147...955202...955294...955324...955422...955431...955703...956023...956146...957053...957490...957549...957972...959223...959299...960206...960329...960418...961047...961612...962607...962960...963243...963355...963386...963506...963633...963871...963932...963980...964419...964480...964939...965343...965358...965408...965595...965628...965667...965766...966270...966301...966384...966533...966982...967071...967561...967763...967968...968084...968450...968471...968893...969535...969630...969835...970043...970247...970471...970783...970826...972803...972854...973260...973618...974031...974111...974225...975034...975652...975888...976155...976990...977189...977248...977423...977444...977512...977851...978010...978106...978266...978600...979143...979391...979736...983230...983463...983637...984117...984578...984905...985024...986334...986987...987193...987383...988436...988538...988777...989950...990096...990655...990912...990950...991223...991642...991995...992326...992483...993303...993521...993612...995239...995282...995667...995964...997217...997332...998410...998607...998741...998990...999051...999638...1000139...1000495...1000565...1000622...1000646...1001796...1002297...1002569...1003796...1004817...1005354...1005421...1005490...1005681...1005894...1006228...1006429...1006503...1006726...1006972...1007083...1007278...1007682...1007981...1008301...1008980...1009080...1010001...1010071...1010148...1010277...1010349...1010440...1010750...1011074...1011202...1012492...1012797...1012828...1013340...1013501...1013528...1013576...1014061...1014215...1014221...1014463...1014696...1014842...1014907...1015049...1015212...1015517...1015534...1015589...1015758...1016021...1016464...1016470...1016761...1017361...1017587...1018359...1018847...1019600...1019673...1019770...1020069...1020539...1020614...1020683...1020852...1020930...1021032...1021568...1021783...1022037...1022193...1022561...1022949...1024132...1024268...1024629...1024716...1024997...1025114...1025189...1025425...1025448...1025764...1025978...1026199...1026706...1026744...1026781...1028350...1029366...1029437...1031399...1031597...1031880...1033749...1035588...1037302...1038434...1038873...1040149...1040588...1040650...1040823...1041542...1041603...1041860...1042203...1042876...1044534...1044771...1045822...1046242...1046746...1048483...1048676...1048934...1049001...1049266...1049410...1050299...1050498...1050993...1051236...1051241...1051665...1051810...1052345...1052976...1053310...1053386...1053633...1053899...1053938...1053951...1053974...1054039...1054096...1054388...1054656...1054798...1054972...1055461...1055523...1055547...1055722...1055725...1055776...1056254...1056485...1056639...1057135...1057749...1058089...1059879...1060429...1060987...1061067...1061459...1061507...1062221...1062275...1062357...1062890...1063651...1063754...1063982...1064285...1064388...1064484...1064797...1065252...1065254...1066200...1067126...1067196...1067560...1067961...1068225...1068969...1069182...1069397...1069427...1069563...1069617...1070117...1070688...1070772...1071464...1071481...1071501...1071571...1072382...1072802...1073854...1074249...1074332...1074530...1074780...1075102...1075269...1075565...1075598...1075829...1075910...1075976...1078029...1078498...1078602...1078953...1079011...1079098...1079556...1079567...1079818...1080279...1080343...1080456...1080600...1080625...1080642...1080688...1080944...1080989...1081129...1081971...1082305...1083912...1083929...1084146...1084347...1084627...1084672...1085093...1085917...1086459...1086503...1086706...1088099...1088175...1088724...1089393...1089398...1089511...1089724...1089765...1090440...1091116...1091235...1091408...1092298...1092574...1092626...1092902...1093247...1093460...1093502...1093604...1093955...1094004...1094427...1094615...1095023...1096035...1096085...1097092...1097663...1097728...1097752...1097836...1099876...1099951...1100246...1100308...1100344...1100429...1100712...1101647...1102617...1102788...1105049...1107420...1108414...1108631...1108740...1109090...1109265...1111017...1111217...1112010...1112160...1112285...1113618...1113667...1113745...1114081...1116564...1116584...1117842...1117943...1121116...1123700...1124025...1124080...1125330...1127044...1127631...1128012...1128219...1128551...1129190...1129832...1130198...1131399...1135838...1137034...1137186...1137598...1137814...1137952...1138124...1138253...1139064...1139180...1141271...1141433...1141517...1141933...1141997...1142559...1142795...1143046...1143137...1143321...1143430...1143709...1143814...1144029...1144773...1146938...1147523...1147771...1147981...1148191...1148289...1148452...1148622...1148765...1148810...1148995...1149221...1149405...1149472...1150060...1150167...1150469...1150632...1150658...1151841...1152385...1153310...1153508...1153978...1154057...1154357...1155333...1156018...1157031...1157215...1157248...1157323...1157455...1157627...1157660...1158020...1159972...1161513...1161911...1162723...1162857...1164724...1164854...1165215...1165372...1165852...1165937...1166228...1166395...1166472...1166806...1166905...1166932...1167018...1167089...1167172...1167213...1168033...1168118...1168710...1168972...1169258...1170145...1171914...1172497...1173262...1173335...1174346...1176042...1176498...1176644...1176763...1176858...1177528...1177853...1177860...1177898...1177941...1178032...1178094...1178102...1178332...1178878...1178929...1178936...1179561...1180050...1180365...1180972...1181062...1182542...1182652...1183317...1183535...1184375...1184935...1185978...1186240...1187300...1187387...1187856...1188518...1188701...1188720...1188996...1189545...1189957...1191094...1191614...1192066...1192917...1193066...1193133...1195385...1196683...1196870...1197542...1197599...1197642...1198719...1198765...1199052...1199236...1199671...1199891...1199994...1200100...1200181...1200623...1201025...1201169...1201477...1202793...1203365...1203388...1204038...1205023...1205641...1205797...1205846...1205935...1206052...1206198...1206500...1207243...1207291...1207345...1207432...1208012...1208307...1209820...1210298...1210391...1210443...1213988...1214079...1214452...1214669...1214848...1214879...1214952...1215152...1215278...1215852...1216888...1217358...1218635...1218946...1219214...1219735...1221764...1221812...1222136...1224125...1224210...1225223...1225320...1225594...1225766...1226065...1226072...1226204...1226955...1226956...1227631...1227755...1228697...1228977...1229345...1229384...1230683...1230925...1230970...1232162...1233051...1233236...1234185...1236574...1237200...1237210...1237632...1238448...1238828...1238862...1239133...1239607...1239773...1240405...1240735...1240986...1241618...1241781...1242303...1242604...1242741...1242917...1242975...1243117...1243251...1243415...1243563...1244096...1244276...1244397...1244562...1244595...1244841...1245246...1245502...1245716...1246771...1246853...1246874...1247138...1248002...1248434...1248695...1249124...1249820...1251113...1252068...1253423...1254232...1254335...1254547...1254554...1254620...1254798...1254901...1255715...1256312...1256510...1256886...1257619...1258333...1259119...1260501...1262786...1262908...1263463...1265963...1268057...1268297...1268642...1268782...1269568...1270250...1271161...1271864...1271878...1271942...1272017...1272086...1272460...1272570...1272613...1274899...1275174...1275619...1275691...1275832...1276217...1276676...1276739...1276837...1277080...1279026...1279295...1279351...1279439...1280049...1280720...1280934...1280956...1281030...1282720...1282864...1283794...1283878...1283942...1284535...1284784...1284925...1285062...1285795...1285868...1286055...1286595...1287045...1287348...1287513...1287747...1287862...1287880...1288050...1288055...1288325...1289023...1289182...1289375...1289412...1289467...1289775...1290366...1290374...1290421...1292507...1292659...1293950...1294393...1295591...1296094...1296185...1296644...1297970...1298260...1298425...1298497...1298787...1298798...1298988...1299305...1299524...1299583...1300152...1300340...1300502...1300809...1301179...1301392...1302418...1302462...1302563...1302716...1303131...1303329...1303576...1303667...1304253...1304303...1304494...1304620...1304634...1304660...1305364...1305776...1305812...1306280...1306444...1306504...1306635...1306876...1307423...1307509...1308388...1308473...1308523...1308643...1309115...1309298...1310167...1310367...1310465...1310544...1310712...1310899...1312724...1312757...1313406...1315449...1315594...1315653...1316005...1316628...1316879...1317738...1318166...1318242...1318432...1318877...1320687...1321217...1321253...1321316...1321830...1322373...1323030...1323305...1323768...1324268...1324275...1324362...1324554...1324619...1325229...1325314...1326149...1326230...1327624...1328160...1328781...1328867...1329020...1329034...1329406...1329413...1329736...1329974...1330174...1330217...1330301...1330505...1330764...1330811...1330817...1331119...1331770...1332103...1333124...1333181...1333651...1333709...1333820...1333879...1334051...1334683...1334837...1335098...1335513...1335555...1336287...1337502...1337921...1338667...1338959...1340833...1341151...1341212...1342391...1346393...1348520...1349079...1350992...1351011...1351231...1351270...1351607...1351743...1351808...1351864...1352247...1352297...1352426...1352537...1352640...1352643...1352907...1353571...1353746...1354873...1355682...1356138...1357247...1357418...1357715...1357805...1358310...1358904...1358957...1359499...1359668...1360637...1360683...1361191...1361384...1361439...1361573...1361758...1363990...1364769...1365010...1365267...1365376...1365789...1366603...1368410...1368711...1369016...1369224...1369579...1369686...1369727...1369864...1370095...1370104...1370244...1370560...1370669...1370717...1373276...1373516...1374427...1375782...1376026...1376139...1376407...1376442...1376700...1376706...1376798...1377152...1377460...1377682...1378516...1378790...1379363...1379724...1382980...1383348...1384671...1385511...1388115...1388930...1388990...1389267...1389974...1391973...1396666...1396793...1397176...1399819...1400433...1400596...1400779...1401198...1401441...1401560...1401705...1402538...1402673...1402913...1403240...1403354...1404032...1404801...1405224...1405284...1405369...1405381...1405662...1406218...1407320...1407824...1407866...1408201...1408798...1409096...1409708...1409840...1410982...1411096...1411102...1411135...1411482...1411524...1411666...1412759...1412922...1412980...1413136...1413187...1413571...1413672...1413683...1413953...1414098...1414522...1414683...1414894...1415088...1415319...1415439...1416173...1416211...1416655...1417457...1417723...1417866...1418372...1418454...1418812...1418842...1419034...1419469...1420222...1420929...1421117...1421896...1422127...1422286...1422318...1422799...1422896...1423020...1423082...1423185...1423462...1423623...1423805...1423820...1424084...1424601...1424692...1424992...1425381...1425599...1426433...1426611...1427628...1427639...1428052...1428315...1428604...1429047...1429058...1429193...1429855...1430531...1430577...1430748...1431216...1431489...1431819...1432319...1432335...1435518...1435752...1435824...1438426...1438818...1438839...1439304...1440046...1440644...1440910...1440941...1441278...1441379...1441514...1441735...1442003...1442011...1442246...1442425...1442930...1443062...1443514...1443686...1443916...1445149...1445580...1445654...1447846...1448039...1448574...1448654...1449486...1449529...1449734...1449833...1450289...1450494...1451048...1453019...1454175...1454235...1454413...1454579...1455064...1455145...1455267...1455620...1455847...1456090...1456186...1456718...1456923...1457677...1457962...1458229...1459720...1460918...1461119...1461972...1462884...1463272...1464553...1464985...1465308...1465787...1466716...1467014...1467031...1467076...1467391...1467440...1468138...1468958...1468988...1469087...1469587...1469627...1469847...1471350...1471840...1472051...1472150...1472721...1472796...1474562...1475760...1475840...1476202...1476203...1476302...1476356...1476943...1477946...1479060...1479369...1479721...1480371...1480911...1482306...1482366...1482920...1484094...1484588...1484757...1485217...1485810...1485869...1485936...1486010...1486179...1486828...1487475...1487530...1487634...1490908...1491799...1492157...1492236...1494998...1495205...1495886...1496082...1496256...1496355...1496975...1497314...1497743...1498792...1499260...1499520...1499937...1500390...1502539...1502839...1503999...1504190...1504245...1504344...1504352...1504363...1505040...1505653...1505859...1506725...1507103...1507234...1507971...1508285...1508356...1508709...1508936...1510784...1511871...1512429...1512503...1513191...1513806...1514472...1514742...1514933...1515723...1515830...1515888...1516030...1516060...1516230...1516410...1516466...1516886...1517059...1517310...1517534...1518982...1519105...1519137...1519165...1519212...1519416...1519552...1519728...1519736...1519780...1520021...1520125...1520831...1520914...1520944...1521368...1521452...1522167...1525976...1526207...1526240...1526523...1526657...1527259...1527547...1527663...1527831...1527893...1528057...1528122...1528234...1528429...1528501...1528504...1528611...1528799...1528959...1529504...1529779...1530532...1531193...1531532...1531656...1531705...1532026...1532256...1532456...1532549...1532993...1533384...1533493...1533770...1533813...1533866...1534656...1535179...1535463...1537522...1537585...1537653...1537690...1537925...1537956...1538324...1538636...1538756...1539091...1539618...1539944...1541226...1541344...1541566...1542060...1542166...1542555...1542643...1542923...1543008...1543946...1544427...1544892...1545381...1545449...1545826...1546017...1546285...1546643...1546702...1547321...1547719...1547986...1548017...1548614...1548854...1551216...1551783...1551996...1552282...1552533...1553822...1554000...1554388...1554513...1555221...1555278...1555326...1555332...1555445...1555625...1555809...1556209...1556502...1556534...1556583...1556593...1556696...1557564...1557648...1557742...1557814...1557984...1558160...1558527...1559267...1559317...1559335...1559844...1560064...1560790...1560918...1560954...1561032...1561182...1561308...1561941...1561944...1562035...1562228...1562235...1562322...1562453...1562878...1563006...1563124...1563585...1563646...1563739...1564591...1565484...1565657...1567266...1567496...1567582...1567959...1568076...1568330...1568368...1568714...1569110...1569428...1569595...1569640...1570360...1571346...1572543...1575282...1575488...1575643...1575730...1575843...1576045...1576184...1577028...1577202...1577374...1577409...1577740...1578347...1578639...1578970...1579007...1579579...1580204...1580408...1580649...1581505...1581862...1582275...1582888...1583564...1583884...1584231...1585170...1585752...1586354...1586966...1586970...1587590...1587734...1587829...1587891...1587978...1588036...1588080...1588258...1588521...1588977...1589138...1589268...1589276...1589647...1592899...1593093...1593913...1594919...1595934...1596417...1596905...1598374...1598729...1598752...1599719...1599813...1600052...1600437...1600989...1601613...1601688...1601728...1601870...1602306...1602522...1603386...1603670...1603731...1604682...1604795...1604853...1604857...1604936...1605111...1605319...1606064...1606186...1606234...1607136...1607515...1607634...1607663...1607998...1608594...1608861...1608886...1609911...1609955...1610005...1610373...1610575...1611013...1611646...1611681...1611819...1612252...1612448...1612597...1612883...1613331...1613882...1614154...1614389...1614832...1614857...1614964...1614971...1615446...1615578...1615625...1615850...1615995...1616065...1616437...1616532...1616683...1616822...1616838...1617402...1617479...1617849...1617925...1618181...1618761...1619340...1619378...1619526...1619659...1620044...1620092...1620152...1620904...1620967...1621018...1621228...1621463...1621631...1621797...1621979...1621988...1622292...1622388...1622671...1622820...1623055...1623525...1623909...1624061...1624064...1624937...1625949...1626739...1627102...1627532...1627569...1627601...1627670...1627692...1627915...1627962...1628099...1628272...1628411...1628949...1629057...1629116...1629478...1629597...1629833...1630359...1630861...1631617...1631660...1631914...1632077...1632176...1632381...1632420...1632500...1632606...1633018...1633101...1633306...1633489...1633565...1633748...1634359...1634368...1634824...1634885...1635021...1635272...1635653...1636283...1636322...1636866...1638039...1639012...1639410...1639425...1640106...1640232...1640732...1640933...1641643...1641889...1642113...1642218...1642548...1642781...1643501...1643914...1644020...1644330...1644401...1645292...1646391...1646624...1646638...1647049...1647249...1647265...1647562...1647642...1647766...1648247...1648319...1648382...1648825...1648919...1649282...1649483...1650157...1650414...1650549...1650651...1650783...1650913...1651764...1652007...1652795...1652996...1653156...1653175...1653406...1653436...1653451...1653487...1653636...1653650...1653694...1653780...1654019...1654026...1654438...1654676...1654679...1655071...1655414...1655713...1655721...1655761...1656003...1656046...1656213...1656434...1657358...1657626...1657719...1658127...1658155...1658267...1658751...1658805...1658925...1658930...1659438...1659954...1660416...1660793...1661370...1661602...1662600...1662747...1662869...1662918...1662922...1663067...1663193...1663415...1663485...1663490...1664134...1664397...1664626...1664638...1664825...1665661...1665875...1665910...1666731...1666884...1667206...1668414...1669561...1670662...1670822...1670913...1670977...1671374...1671489...1671667...1671988...1672524...1672540...1673756...1673800...1674377...1674564...1674670...1675506...1675704...1675951...1676766...1677553...1677588...1678261...1678461...1678499...1678801...1678826...1679175...1679765...1679940...1679947...1680025...1680064...1680108...1680939...1681334...1681823...1682102...1682379...1682452...1683086...1684238...1684515...1684914...1684951...1685489...1687638...1687951...1688030...1688709...1688776...1689061...1689327...1689344...1689525...1689780...1690377...1690496...1690739...1690806...1690921...1691085...1691261...1691393...1691577...1691694...1691707...1691709...1691829...1691937...1692024...1692261...1692309...1692316...1692426...1692452...1692516...1692631...1692644...1692670...1692702...1693186...1693845...1694040...1694744...1694956...1694987...1695270...1695307...1695624...1696161...1696223...1696413...1697274...1697622...1697696...1698196...1698741...1698909...1698958...1699397...1699428...1699433...1699663...1699887...1700318...1700755...1700808...1700874...1701300...1701501...1701847...1701873...1702266...1702527...1703596...1703811...1704030...1704203...1705202...1706031...1706270...1706291...1706501...1706542...1706627...1706755...1706891...1707113...1707664...1707780...1708201...1708366...1708418...1708689...1708699...1708813...1708976...1709042...1709109...1709155...1709617...1709755...1710216...1711116...1711814...1712028...1713179...1713714...1714165...1714223...1714273...1714576...1714581...1714712...1714818...1715236...1715334...1715413...1715443...1715487...1715857...1716175...1716366...1716722...1716760...1716802...1717164...1717592...1718375...1718434...1718584...1718754...1719152...1719328...1719587...1719589...1719634...1719864...1720329...1720530...1720966...1721090...1721317...1721529...1722310...1723035...1723090...1723337...1723505...1723535...1723740...1723847...1723977...1724065...1724408...1724564...1724685...1724994...1725193...1725846...1726248...1726275...1726341...1726539...1726826...1727225...1727372...1727413...1727424...1727444...1727470...1727562...1728420...1728465...1728555...1728663...1728733...1729675...1729875...1729948...1730009...1730282...1731068...1731605...1731784...1732013...1732297...1732342...1732611...1732655...1732849...1732912...1733254...1733781...1733947...1734025...1734262...1734927...1735110...1735585...1735998...1736050...1736401...1736738...1736862...1736991...1737664...1737935...1738378...1738801...1739021...1739904...1740236...1740431...1740487...1740626...1740675...1740764...1741330...1741513...1741552...1741614...1741879...1742618...1742699...1742771...1742806...1743040...1743085...1743456...1743705...1743810...1744748...1745704...1745788...1745833...1745837...1746348...1747059...1748680...1748841...1749080...1749523...1749590...1749804...1749845...1749861...1749865...1749914...1750103...1750235...1750280...1750447...1750514...1751035...1751383...1751438...1754015...1754342...1756423...1756823...1758560...1758910...1760253...1760292...1760439...1760646...1760978...1761027...1761386...1762577...1762647...1762790...1762832...1762913...1763294...1763295...1763415...1763626...1763977...1764112...1765258...1765364...1766452...1766723...1766771...1767333...1767346...1767687...1767964...1768013...1768106...1768726...1768860...1769027...1769218...1769401...1769640...1769988...1770705...1771106...1774533...1775373...1777031...1777508...1777532...1777632...1778413...1779036...1779414...1779559...1780313...1782539...1782700...1782717...1782888...1783343...1783500...1783969...1784143...1784524...1784538...1784760...1784785...1784988...1785124...1785590...1785597...1785804...1786072...1786507...1787272...1787612...1787617...1789637...1790198...1790444...1791697...1792163...1792372...1792716...1792924...1793772...1793945...1795303...1795518...1796960...1797116...1797548...1798601...1799646...1799657...1800234...1800350...1800531...1801365...1801624...1801708...1801716...1802602...1803010...1803447...1804586...1804695...1804746...1804798...1804835...1805134...1805581...1805981...1806378...1807287...1807995...1808319...1808907...1809241...1809936...1810462...1810659...1810717...1810806...1810916...1810937...1811069...1811300...1811729...1812366...1812392...1813911...1813922...1814176...1815681...1816002...1817182...1817554...1817779...1818827...1819010...1819076...1819177...1819204...1820186...1820607...1820720...1820871...1821458...1822300...1822422...1822503...1822543...1822668...1822740...1822831...1822916...1822981...1823020...1823350...1823413...1823610...1823728...1823804...1823868...1824418...1824427...1824827...1824995...1825078...1825456...1825587...1825649...1825721...1825747...1825850...1825903...1825989...1826017...1826091...1826201...1826602...1827003...1827625...1828122...1828521...1829362...1829998...1830203...1830388...1830554...1831379...1831435...1831688...1832030...1832527...1832612...1833058...1833142...1833315...1833505...1833582...1833680...1833755...1833905...1834212...1834363...1834940...1835226...1835326...1835342...1835367...1835542...1835625...1835854...1836040...1836555...1838462...1838543...1838610...1839387...1839751...1839872...1839917...1839967...1840198...1842373...1843745...1844952...1845546...1845675...1846520...1847433...1848275...1848689...1848777...1849211...1849558...1849664...1850289...1850799...1850990...1851072...1851440...1851463...1852302...1852590...1852712...1852803...1853376...1855142...1855203...1855789...1857533...1857828...1858146...1858194...1858676...1858931...1859353...1859907...1860297...1860537...1860576...1860845...1860951...1861529...1861817...1862170...1862282...1862980...1863723...1867620...1868112...1868799...1869290...1869736...1870218...1871888...1872081...1872308...1872485...1872628...1872791...1873009...1873166...1874676...1874773...1875164...1875313...1875451...1875791...1877637...1878512...1878603...1878642...1879283...1879769...1880139...1881997...1883592...1884491...1884611...1884741...1884862...1885805...1885843...1886588...1886837...1886952...1887117...1887856...1888407...1888462...1889245...1889481...1889652...1890402...1890431...1890479...1890541...1890599...1890684...1890898...1891054...1891524...1891554...1892778...1892785...1892808...1892888...1893270...1893337...1893340...1894333...1894707...1895121...1895319...1895395...1895448...1896320...1897046...1897536...1899774...1900360...1900386...1900626...1900639...1901039...1901175...1901504...1901960...1902062...1903037...1903209...1903282...1903304...1904284...1904421...1906772...1907174...1907532...1907769...1908176...1908650...1908786...1908939...1911554...1913855...1915475...1915512...1915716...1915923...1917202...1919678...1921176...1921182...1921394...1922301...1923046...1923082...1924194...1925280...1925625...1926209...1927474...1927682...1928192...1929023...1930285...1930891...1931398...1932314...1932399...1932816...1934643...1935467...1936573...1937082...1937103...1937179...1937382...1937436...1937452...1937548...1937623...1938566...1938768...1938858...1938956...1939109...1939177...1939217...1939607...1939740...1940193...1940321...1940351...1940649...1941170...1941173...1941367...1941563...1941651...1942607...1943765...1943888...1945358...1945650...1946043...1946330...1946539...1946662...1946727...1947547...1947653...1947756...1947885...1947976...1948288...1948293...1948708...1948962...1949223...1949394...1949854...1949885...1949995...1950077...1952015...1952071...1952441...1952977...1953118...1953124...1953245...1953758...1954325...1954354...1954964...1954981...1955228...1955529...1955801...1956224...1956264...1956271...1956488...1957029...1957127...1957608...1957964...1958159...1958674...1958798...1958930...1958997...1959075...1959516...1959603...1959731...1959790...1959863...1959990...1960401...1960407...1960530...1960822...1960955...1961539...1961880...1961979...1962368...1962567...1962859...1963163...1963316...1963536...1963660...1963668...1963673...1964264...1964416...1964551...1965070...1965175...1965511...1965878...1966021...1966379...1966526...1967620...1967688...1967740...1967792...1967928...1968847...1969111...1969864...1970331...1970554...1970611...1970783...1970813...1970933...1971316...1971374...1971970...1972100...1972176...1972426...1972543...1972624...1972821...1973732...1973814...1974063...1974984...1975049...1975237...1975359...1975405...1975420...1976118...1976348...1977006...1977027...1977171...1977251...1977325...1977419...1977583...1979664...1980657...1981105...1981810...1981983...1982233...1982356...1982361...1983749...1984366...1985432...1985912...1986319...1987612...1987669...1987916...1988347...1988493...1989075...1989330...1989437...1989445...1989807...1990329...1990853...1991242...1991311...1992316...1992421...1992635...1992676...1992839...1994132...1994479...1994647...1995809...1996145...1997147...1997272...1997309...1997895...1998430...1998565...1999542...1999670...2000111...2000214...2001544...2002006...2002246...2002249...2002292...2003197...2003279...2003442...2003459...2003463...2006111...2006383...2006492...2006664...2007203...2007915...2007970...2008021...2008188...2008892...2009100...2009424...2009658...2010359...2010979...2011074...2012213...2012508...2013122...2017272...2017315...2017337...2017362...2017560...2017949...2020308...2020610...2021111...2021637...2022399...2022700...2023192...2023363...2023388...2023529...2023605...2024071...2024365...2024548...2025041...2025407...2026029...2026504...2026826...2026861...2026863...2027031...2027249...2027302...2027375...2027529...2029272...2029921...2029969...2030530...2030778...2033123...2034401...2036045...2036902...2036950...2037214...2038661...2039425...2039641...2040437...2040871...2040926...2041356...2041800...2042045...2042190...2042438...2042693...2043007...2043081...2043269...2044059...2044599...2044678...2044714...2045246...2045911...2048788...2050143...2050293...2050557...2050952...2051422...2051500...2051836...2051974...2052140...2053653...2054638...2055382...2055643...2055846...2055944...2058072...2058899...2061824...2062228...2062804...2062853...2062908...2063643...2064022...2064124...2064854...2064946...2065666...2065772...2066576...2067062...2067392...2067632...2067835...2067927...2068169...2070055...2070075...2070743...2070789...2071139...2071217...2071461...2071668...2072046...2072059...2072424...2072640...2073549...2074423...2076723...2076950...2077500...2077560...2077715...2078028...2078801...2079104...2079347...2079393...2079419...2080237...2080256...2080341...2080471...2080776...2081115...2081138...2081312...2081513...2081522...2081766...2081937...2082079...2082665...2082949...2083036...2083049...2084131...2084439...2084451...2084889...2084986...2085040...2085237...2085390...2085677...2086248...2086428...2086431...2086816...2086878...2087070...2087124...2087224...2087281...2087340...2088182...2088249...2088418...2088576...2088607...2088652...2088687...2088750...2088854...2088962...2089150...2089327...2089483...2089523...2090834...2092127...2093135...2093836...2094497...2094987...2095055...2095417...2095847...2096582...2096849...2097016...2097323...2097733...2098546...2098726...2099284...2099635...2099768...2100668...2101163...2101269...2101550...2101572...2101655...2101800...2101856...2101969...2102409...2102441...2102720...2102919...2102927...2103263...2103519...2103620...2103634...2103660...2103833...2104277...2104420...2104872...2105101...2105322...2105580...2106106...2106800...2107061...2107169...2107408...2108078...2108100...2108109...2109476...2111686...2112644...2112864...2113022...2113176...2114006...2115304...2115929...2116601...2117722...2117892...2118172...2119016...2119059...2120003...2120084...2120841...2121809...2121948...2123023...2123105...2123665...2126103...2128880...2128884...2129015...2129099...2129254...2130244...2130501...2130747...2131573...2131918...2132771...2133889...2134518...2134635...2135430...2136658...2137216...2137261...2137305...2137331...2137578...2137703...2138561...2138662...2138829...2138888...2139659...2140607...2140656...2140929...2141513...2141648...2141841...2141857...2142229...2142318...2142393...2142503...2143255...2143402...2144746...2145453...2145661...2145708...2147470...2147520...2148312...2148891...2149136...2149561...2149709...2149804...2150253...2150546...2150647...2150775...2151464...2151517...2151569...2151739...2152801...2153153...2153477...2154284...2154443...2154829...2155557...2156070...2156236...2156337...2156349...2156727...2156883...2156960...2157080...2157090...2157097...2158217...2158242...2159271...2159363...2160648...2160810...2160927...2161627...2161631...2161647...2161808...2161861...2162113...2162172...2162565...2162592...2162697...2162723...2163094...2164056...2164963...2165278...2166036...2168784...2169978...2170728...2171546...2172839...2172920...2175130...2175201...2175567...2176117...2176190...2176387...2176536...2176622...2176739...2177246...2177970...2178390...2179087...2180859...2180952...2181228...2182158...2182553...2183411...2183764...2183786...2183825...2183900...2184333...2184561...2184684...2184757...2185126...2185439...2185508...2185581...2186062...2186204...2186573...2186792...2186869...2186882...2187021...2187312...2187421...2187866...2187911...2187938...2188413...2188474...2188542...2188544...2188767...2189361...2189901...2190562...2190649...2190672...2190801...2190876...2190912...2191152...2191339...2191920...2192068...2192165...2192758...2192963...2193004...2193327...2193447...2193485...2194115...2197700...2200656...2201036...2201043...2201730...2201864...2202673...2205620...2206313...2206446...2207671...2207986...2208402...2208566...2208813...2209302...2209625...2209954...2210551...2211109...2211372...2211458...2211998...2212215...2212824...2213303...2213533...2213741...2213987...2214016...2214396...2215035...2216022...2216096...2216296...2216497...2216585...2216816...2217063...2217148...2217257...2217414...2217517...2217772...2218210...2218427...2218663...2218714...2218876...2219010...2219026...2219348...2219430...2219658...2219698...2220540...2220710...2220850...2221058...2221690...2222066...2222236...2222357...2222513...2223125...2223791...2223845...2223873...2224340...2224647...2225154...2226020...2226159...2226360...2227758...2227833...2227890...2227894...2227997...2228646...2228811...2229630...2230046...2230140...2230395...2231581...2231751...2231830...2232723...2234068...2234353...2234449...2234468...2236098...2236140...2236850...2237019...2238166...2238183...2239146...2239855...2240454...2240888...2240931...2241053...2241091...2241550...2241573...2242430...2242944...2243388...2243401...2243492...2243617...2243656...2243663...2243707...2244291...2244628...2244673...2245430...2245661...2245705...2245779...2245829...2245893...2246260...2246517...2246764...2247166...2247432...2247582...2247870...2248082...2248147...2248590...2249003...2249796...2250082...2250708...2251329...2251678...2251895...2252519...2253150...2253521...2253600...2254287...2255477...2255551...2255971...2256045...2256843...2256896...2257086...2258897...2259154...2259323...2259777...2260040...2260344...2260378...2260483...2260976...2261049...2261160...2261163...2261539...2262172...2262409...2262804...2262841...2264102...2264220...2264399...2265034...2265944...2266183...2266269...2267011...2267231...2267316...2267410...2267607...2267773...2267896...2267939...2268002...2268299...2269031...2269322...2269455...2269530...2270035...2270321...2270371...2270384...2270433...2271227...2271460...2272776...2272977...2273180...2273826...2274211...2274252...2274530...2274602...2275277...2275396...2275477...2275875...2276697...2277244...2277749...2278589...2279105...2280029...2280111...2280526...2280614...2280954...2281678...2282129...2282818...2283743...2283879...2283930...2284074...2284187...2284247...2284282...2284866...2285149...2285219...2285329...2285373...2285729...2285750...2285826...2286068...2286247...2286293...2286613...2286813...2287138...2287218...2287254...2287442...2288062...2288200...2288632...2289072...2289400...2289537...2289583...2290418...2291773...2292025...2293365...2293586...2293730...2293821...2294149...2294620...2294683...2294774...2295330...2295465...2295491...2295609...2295795...2295799...2295851...2296271...2296612...2296934...2297558...2299304...2300914...2304606...2304942...2307052...2307817...2309418...2309560...2309928...2310579...2310771...2311485...2312544...2313385...2314664...2314968...2315028...2315849...2319711...2319896...2324938...2325355...2329573...2330616...2331194...2331230...2331609...2331651...2331676...2333384...2333603...2334538...2335005...2335127...2335873...2336756...2337471...2337929...2339275...2339773...2340016...2341653...2342217...2342372...2343985...2344329...2344997...2345155...2345159...2345253...2345673...2345736...2345931...2347539...2347969...2347999...2348996...2349141...2349412...2349714...2350463...2352161...2352362...2355377...2355699...2356316...2358199...2358894...2358994...2359023...2359995...2360106...2361124...2361599...2362003...2362268...2364461...2364641...2365320...2365423...2365632...2365771...2366738...2367088...2367461...2368144...2368576...2368972...2369051...2369802...2369823...2369899...2370006...2370049...2370273...2370471...2370602...2371018...2371201...2372009...2372382...2373014...2373107...2373727...2374364...2374410...2374758...2375667...2375996...2376223...2376927...2377116...2377151...2377350...2379753...2379899...2379975...2380287...2380357...2380474...2380535...2380788...2380909...2381542...2381927...2381991...2382603...2383212...2383385...2383686...2384048...2384073...2385440...2385473...2385805...2386992...2387036...2387069...2387155...2387760...2387837...2388022...2389008...2389050...2389342...2389455...2390291...2391263...2391345...2391451...2392223...2392623...2392853...2392939...2393001...2393870...2394585...2394782...2394857...2395127...2395628...2395989...2396343...2396514...2396604...2396904...2396957...2397289...2397739...2402816...2403020...2403446...2403595...2403888...2404648...2404796...2404843...2406620...2407873...2408703...2409641...2410309...2410390...2410482...2411099...2411428...2411718...2412381...2412508...2413075...2413151...2413162...2414331...2416137...2417391...2417433...2417490...2418013...2418089...2418153...2418156...2418236...2419082...2419366...2419561...2419755...2419846...2420019...2420058...2420103...2420543...2420979...2421135...2421190...2421289...2422197...2422331...2422408...2422870...2422981...2423290...2423345...2423770...2423832...2423957...2424537...2424731...2424798...2424833...2425098...2426169...2426336...2426406...2426803...2427302...2428648...2429370...2429687...2430031...2430431...2430904...2430919...2431088...2431627...2431993...2432108...2432152...2433194...2433851...2434236...2435266...2435755...2436045...2436089...2436208...2436595...2436847...2437810...2438003...2438148...2438376...2438545...2439220...2439517...2439551...2440096...2440661...2441091...2441145...2441326...2441613...2441962...2441996...2442702...2442917...2443249...2443371...2444047...2444561...2444827...2447497...2448469...2448517...2449211...2449244...2449559...2449569...2450279...2450415...2451595...2452732...2453117...2453523...2454346...2455666...2455684...2455747...2456034...2456413...2456988...2457090...2458179...2458395...2458781...2459619...2460009...2460414...2461852...2462306...2462589...2462790...2462854...2463046...2463893...2464111...2464165...2464274...2464460...2464497...2464686...2465031...2465719...2466747...2466876...2467116...2467807...2467873...2467912...2468488...2468602...2469043...2469121...2469913...2470477...2470535...2471684...2472098...2473095...2473325...2473811...2476294...2477274...2477521...2477566...2479242...2479496...2479648...2480539...2480620...2481086...2483543...2483617...2483969...2484056...2484124...2484432...2484568...2484682...2485274...2485278...2485535...2485821...2486067...2486304...2486913...2486947...2487064...2487234...2487988...2488137...2488225...2488285...2488447...2488953...2489460...2489624...2489755...2489991...2490007...2490548...2490859...2490947...2491052...2492174...2492440...2492594...2492798...2493173...2493496...2494121...2494172...2494190...2494244...2494488...2494804...2494990...2495019...2495068...2495199...2496059...2497233...2498506...2498683...2498927...2499251...2499263...2499294...2499426...2499662...2499820...2499860...2499933...2499979...2500307...2500430...2500530...2500700...2501011...2501189...2501299...2501790...2501816...2501986...2502006...2502135...2502175...2502291...2502300...2502619...2502684...2502814...2502955...2502994...2503171...2503185...2503368...2503411...2503679...2504903...2504973...2505088...2505465...2505474...2505563...2505637...2505732...2506225...2506533...2507018...2507172...2507325...2507402...2507721...2508837...2509458...2509570...2509939...2510227...2510280...2510295...2510830...2511802...2512385...2513573...2519133...2520493...2521783...2521869...2523431...2525539...2525599...2526019...2534586...2535632...2537925...2538822...2538893...2540864...2542091...2543082...2544637...2544658...2544778...2547457...2549388...2549457...2551931...2552840...2554068...2554140...2554216...2554366...2565172...2567035...2567622...2568998...2569070...2572133...2572319...2574078...2574134...2574269...2584173...2592838...2594261...2595250...2603603...2603810...2604911...2607790...2609093...2613112...2614462...2616712...2621896...2622120...2625005...2625801...2625924...2627637...2628059...2631512...2631979...2636366...2640942...2641518...2643303...2648910...2651600...2665927...2667392...2670173...2672399...2675217...2675704...2682261...2685007...2685176...2686827...2687067...2688728...2692406...2692486...2692524...2692605...2693259...2698442...2703781...2704597...2706911...2708087...2708551...2709761...2714001...2715121...2715794...2715949...2716095...2717314...2724341...2734252...2734374...2737441...2739714...2741267...2744655...2747695...2747765...2748948...2751497...2758699...2759480...2768586...2768732...2771001...2774289...2774858...2795002...2799114...2802950...2805877...2813663...2815092...2819381...2821371...2827717...2827807...2832588...2834505...2843100...2843963...2844032...2844375...2847779...2849154...2849263...2851153...2855315...2856824...2857808...2858020...2870405...2872698...2880241...2882790...2883622...2884070...2884229...2890110...2894693...2899029...2901220...2911456...2913484...2915385...2916960...2918543...2922682...2924823...2930133...2936892...2944384...2951685...2951797...2955072...2961704...2961760...2963888...2964364...2973054...2976385...2980115...2984946...2992371...2992576...2995386...2997870...3001158...3001193...3012538...3017002...3021781...3033048...3033151...3039702...3039810...3044903...3047823...3048725...3048856...3053282...3054344...3055650...3063484...3064290...3069431...3076940...3083423...3091966...3097235...3105327...3107049...3108562...3115670...3117677...3117800...3117862...3119084...3119153...3120285...3121508...3121600...3122676...3129515...3136772...3138014...3139787...3140652...3144671...3147646...3148506...3148565...3154813...3154850...3156363...3163011...3163447...3176165...3177202...3181832...3184391...3188815...3188937...3192050...3193465...3195731...3200111...3201174...3206000...3217271...3217404...3218583...3220837...3221193...3225090...3226076...3229500...3233490...3233724...3239371...3240138...3246065...3246834...3253144...3258934...3274990...3279157...3279272...3279342...3279781...3281314...3281390...3281525...3286616...3288236...3291446...3300357...3307913...3308388...3309328...3315489...3317977...3319709...3330593...3334379...3351854...3353257...3360347...3361322...3362530...3363139...3364638...3367231...3369823...3372214...3376077...3378329...3379289...3379365...3379908...3381594...3381755...3390591...3398356...3404326...3417351...3421977...3423099...3423333...3423669...3423688...3425095...3429352...3431983...3432489...3444785...3446059...3446347...3455557...3460982...3465074...3465512...3465984...3467830...3469163...3472215...3472285...3474089...3476984...3491347...3491987...3493654...3494138...3495698...3495809...3497121...3499119...3499652...3500536...3504324...3504440...3511772...3514871...3516474...3520371...3521214...3533006...3533045...3533976...3534214...3538777...3542061...3542145...3546692...3552953...3552998...3557095...3562842...3565139...3566216...3568130...3568221...3571113...3571541...3578312...3578629...3579318...3583099...3601410...3601488...3609641...3613756...3615078...3615121...3617988...3619948...3630560...3641596...3647305...3650237...3650367...3651496...3651594...3651741...3655301...3661894...3662435...3670944...3671165...3673159...3673684...3681939...3684366...3687238...3700516...3700802...3705926...3707378...3708483...3709005...3710432...3714277...3714827...3718895...3721980...3722778...3724068...3725919...3727019...3727546...3727906...3733300...3741000...3741726...3744235...3749496...3751239...3759147...3766558...3767325...3767420...3772168...3773907...3776192...3781099...3788078...3789637...3789707...3790994...3793281...3798630...3799614...3805250...3806344...3808189...3811309...3815696...3817589...3817647...3818649...3819140...3823822...3824765...3824895...3825382...3825728...3827740...3830639...3843209...3843223...3846006...3854384...3854886...3855622...3858504...3867299...3867583...3872094...3872506...3872920...3881244...3881301...3881419...3882933...3901350...3902136...3903198...3904259...3907808...3910489...3911034...3911623...3915897...3916193...3917208...3917381...3918445...3919412...3921732...3923225...3924017...3931473...3933503...3934066...3938289...3941547...3941581...3942609...3944906...3950941...3952405...3953520...3954244...3959807...3967606...3967867...3969128...3970026...3972050...3972105...3972769...3977858...3978198...3978720...3978801...3990171...3991153...3992538...3995641...3997854...4000532...4005795...4006199...4006563...4006901...4007161...4009831...4025766...4028511...4032609...4041651...4045181...4046927...4047028...4047195...4047782...4049860...4049949...4050023...4058696...4058817...4058917...4058954...4060429...4061234...4061481...4065550...4068334...4071947...4072613...4075568...4076249...4084760...4087675...4089606...4090679...4091013...4092398...4093211...4093250...4095985...4096074...4101076...4109821...4109900...4110426...4120120...4120186...4123608...4124522...4125953...4132034...4132414...4132516...4136758...4140702...4144872...4148040...4149040...4149123...4152358...4153851...4154800...4158604...4160068...4162590...4163244...4176273...4178465...4179177...4179269...4183972...4186491...4190125...4193186...4193927...4194776...4196104...4206048...4217003...4217762...4218589...4222961...4223136...4231958...4233067...4238287...4238629...4238712...4239900...4240726...4241258...4242274...4242742...4253332...4261541...4265104...4267297...4270825...4274118...4276144...4284853...4286509...4287061...4292105...4294114...4294471...4294505...4294916...4295056...4295090...4311178...4324142...4324285...4325451...4328456...4328547...4329613...4330048...4331962...4333544...4334585...4339869...4342069...4342159...4354467...4364184...4368153...4371411...4379738...4391350...4394144...4395792...4402021...4402393...4415305...4415377...4416685...4419361...4423096...4435984...4437901...4440664...4452752...4452821...4452900...4457312...4462556...4484855...4485460...4485501...4486263...4491898...4493010...4500387...4500516...4500596...4504061...4504180...4504286...4526495...4526632...4526683...4530291...4530479...4537199...4556746...4573664...4579557...4579632...4586672...4587100...4613854...4613984...4614150...4618537...4618589...4629143...4629177...4647241...4648440...4651514...4710699...4719007...4719151...4719195...4720687...4782136...4788354...4793079...4838399...4838476...4839029...4840569...4844553...4844633...4845294...4845936...4846003...4846041...4848080...4848240...4849288...4853860...4891760...4897816...4903187...4903527...4906670...4919108...4919908...4921251...4935466...4936809...All jobs completed. Finish execution
Final value of timer: 4936879.000000 seconds (1371.355278 hours)
Time when number of pending job is zero: 4936879.000000 seconds (1371.355278 hours)

Plot preemption vectors for different policies as heatmaps

  • If time_limit is set (the value can be copied from the output of the previous cell), it will help exclude the tail end of execution when not all of the nodes are utilized (i.e., number of pending jobs is zero); for consistency reasons, such tail end should not be compared to the rest of the experiment when all nodes are running jobs.
In [32]:
preemptions = pd.read_csv("preemptions.csv")
# Exclude index column recorded in the file
preemptions.drop(["Unnamed: 0"], inplace=True, axis=1)

# Plot data only up to this time limit (in seconds); if not set, trimming will not be enforced
time_limit = 4936879.000000

# Trim to the limit
if time_limit:
    preemptions = preemptions[preemptions["Time"] <= time_limit]

node_count = len([node for node in preemptions.columns.values if "node-" in node])

grouped_preemptions = preemptions.groupby(["Policy"])

for p, group in grouped_preemptions:

    # rename columns: Node-X -> X
    column_name_map = {"node-%d" % id: id for id in range(node_count)}
    x = group.rename(columns=column_name_map)
    # print x.head()

    # drop unnecessary column
    x = x.drop(['Policy'], axis=1)
    # print x.head(20)
    
    # Convert time from seconds to hours for cleaner plotting
    x['Time'] = x['Time']/3600.0
    
    xticklabel_count = 8
    xticklabel_interval = int(len(x)/xticklabel_count)

    x = pd.melt(x, id_vars=['Time'], var_name='Node')
    
    x = x.pivot("Node", "Time", "value")

    fig, ax = plt.subplots(1,1, figsize=FSIZE)
    
    sns.heatmap(x, cmap="YlOrBr", xticklabels=xticklabel_interval, ax=ax, cbar_kws={"label": "Preemption Value"})
    # sns.heatmap(x, cmap="YlOrBr", ax=ax, cbar_kws={"label": "Preemption Value"})
    
    labels = ["%.1f" % float(item.get_text()) for item in ax.get_xticklabels()]
    ax.set_xticklabels(labels)
    ax.set_xlabel('Time, hours')
    
    ax.set_title("Runtime-based Preemption Vectors. Workload: %s. Policy: %s" % (MODE.upper(),p))
    ax.set_xticklabels(ax.xaxis.get_majorticklabels(), rotation=0)
    fig.tight_layout()
    fig.savefig(p + '-heatmap.png', dpi=300)

Create timeline and violin plots for wasted cycles

  • Same as above, if time_limit is set, the tail end of execution when not all of the nodes are utilized will be excluded.
In [5]:
wasted_cycles = pd.read_csv("wasted_cycles.csv")
wasted_cycles.drop(["Unnamed: 0"], inplace=True, axis=1)

# Plot data only up to this time limit (in seconds); if not set, trimming will not be enforced
time_limit = 4936879.000000

# If HTC, exclude PAP policy because it is the same as LIFO
if MODE == "htc":
    wasted_cycles = wasted_cycles[wasted_cycles["Policy"] != "PAP"]

sns.set_style("white")
sns.set_palette(sns.color_palette("Paired"))

gp_vals = sorted(wasted_cycles["GracePeriod"].unique().tolist())
#norm = plt.Normalize()
#gp_cols = plt.cm.jet(norm(range(len(gp_vals))))
gp_cols = sns.color_palette(n_colors=4) 

grouped_wc = wasted_cycles.groupby(["Policy"])

violin_data = pd.DataFrame()
for p, p_group in grouped_wc:
    # Loop over different policies
    fig, ax = plt.subplots(figsize=(10,4))
    
    col_id = 0
    for g, pg_group in p_group.groupby(["GracePeriod"]):
        # Loop over different grace periods within the same policy
        for_plot=pg_group.sort_values(by=['Time'])
        # Trim to the limit
        if time_limit:
            for_plot = for_plot[for_plot["Time"] <= time_limit]
        
        # Convert time from seconds to hours for cleaner plotting
        for_plot['Time'] = for_plot['Time']/3600.0
        # Convert wasted cycles from seconds to hours for cleaner plotting
        for_plot['WastedCycles'] = for_plot['WastedCycles']/3600.0
        
        for_plot.plot(kind='line', x='Time', y='WastedCycles', \
                           c=gp_cols[col_id],label='%s-%d' % (p,g), ax = ax)
        col_id += 1
         
        #violin_data["%s-%d" %(p, g)] = pg_group["WastedCycles"].reset_index(drop=True)
        #violin_data = violin_data.append(pg_group[["WastedCycles", "Policy", "GracePeriod"]])
        
        violin_data = violin_data.append(pg_group[["WastedCycles", "Policy", "GracePeriod"]])
        
        print "Policy: %s, GracePeriod: %s, # of samples: %d, avg. time between samples in seconds: %f" % (p, g, len(for_plot), for_plot['Time'].max() * 3600.0 / len(for_plot))
         
        
    ax.set_title("Wasted Cycles. Workload: %s. Policy: %s" % (MODE.upper(),p))
    ax.set_ylabel("Wasted Cycles, hours")
    ax.set_xlabel("Time, hours")
    ax.legend(loc="upper left") 
    
    fig.savefig(p + '-timeline.png', dpi=300)

# Convert wasted cycles from seconds to hours for cleaner plotting
violin_data['WastedCycles'] = violin_data['WastedCycles']/3600.0

if MODE == "htc":
    # Displaying 3 out 4 policies
    fig, ax = plt.subplots(figsize=(FSIZE[0]*(3.0/4),FSIZE[1]))
else:
    # In cases other than htc, PAP is shown and the graph needs to have full width
    fig, ax = plt.subplots(figsize=FSIZE)
    
sns.set_style("ticks")
sns.violinplot(data=violin_data, x="Policy", y="WastedCycles", hue="GracePeriod", cut=0, ax=ax);
#sns.despine(trim=True)
#for label in ax.get_xticklabels():
#    label.set_rotation(45)  
ax.set_title("Comparison of Policies and Grace Periods. Workload: %s" % (MODE.upper()))
ax.set_ylabel("Wasted Cycles, hours")
ax.legend(title="Grace Period, s", loc="upper center", ncol=4)

# No reason to show negative values
_,ylim_ub = ax.get_ylim()
ax.set_ylim(0,ylim_ub)

fig.tight_layout()
fig.savefig( 'wasted_cycles-violins.png', dpi=300)
Policy: FIFO, GracePeriod: 60, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: FIFO, GracePeriod: 120, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: FIFO, GracePeriod: 1200, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: FIFO, GracePeriod: 1800, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: LIFO, GracePeriod: 60, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: LIFO, GracePeriod: 120, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: LIFO, GracePeriod: 1200, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: LIFO, GracePeriod: 1800, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: PAP, GracePeriod: 60, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: PAP, GracePeriod: 120, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: PAP, GracePeriod: 1200, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: PAP, GracePeriod: 1800, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: RANDOM, GracePeriod: 60, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: RANDOM, GracePeriod: 120, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: RANDOM, GracePeriod: 1200, # of samples: 168107, avg. time between samples in seconds: 29.367421
Policy: RANDOM, GracePeriod: 1800, # of samples: 168107, avg. time between samples in seconds: 29.367421