#include <iostream>
#include <sstream>
#include <vector>
#include <fstream>
#include <igraph.h>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <chrono>
#include <climits>
#include "gurobi_c++.h"
 
#define VERBOSE false
#define WRITE_ILPS_TO_FILE false
#define PRINT_COMPONENT_SIZES false
#define PRINT_FACTOR 100
#define ILP_TIME_LIMIT 3600 // in seconds
 
using namespace std;
 
typedef struct edge_attributes_struct{
    igraph_integer_t edge_idx;
    igraph_real_t label;
    igraph_real_t variant;
}edge_attributes;
 
 
void print_variation_graph(const igraph_t *graph){
    igraph_vs_t vs;
    igraph_vit_t vit;
 
    igraph_vs_all(&vs);
    igraph_vit_create(graph, vs, &vit);
    while (!IGRAPH_VIT_END(vit)) {
        cout << IGRAPH_VIT_GET(vit) << ": " << endl;
 
        igraph_vector_int_t edges;
        igraph_vector_int_init(&edges, 0);
        igraph_incident(graph, &edges, IGRAPH_VIT_GET(vit), IGRAPH_OUT);
        for(long int i = 0; i < igraph_vector_int_size(&edges); i++){
            igraph_integer_t start, end;
            igraph_edge(graph, igraph_vector_int_get(&edges, i), &start, &end);
            cout << "\t(" << start << ", " << end << ", " 
                << "label: " << igraph_cattribute_EAN(graph, "label", igraph_vector_int_get(&edges, i)) << ", "
                << "variant: " << igraph_cattribute_EAN(graph, "variant" , igraph_vector_int_get(&edges, i)) << ")" << endl; 
            ;
        }
        igraph_vector_int_destroy(&edges);
        IGRAPH_VIT_NEXT(vit);
        cout << endl;
    }
    cout<< endl;
}
 
 
void print_alignment_graph(igraph_t *graph){
 
    cout << "\nPrinting alignment graph:" << endl;
    cout << "pos = " << igraph_cattribute_GAN(graph, "position")
        << ", substring = " << igraph_cattribute_GAS(graph, "substring") << endl;
 
    igraph_vs_t vs;
    igraph_vit_t vit;
 
    igraph_vs_all(&vs);
    igraph_vit_create(graph, vs, &vit);
    while (!IGRAPH_VIT_END(vit)) {
        cout << IGRAPH_VIT_GET(vit)  
            << " startend: " << igraph_cattribute_VAN(graph, "startend", IGRAPH_VIT_GET(vit))  
            << endl;
 
        igraph_vector_int_t edges;
        igraph_vector_int_init(&edges, 0);
        igraph_incident(graph, &edges, IGRAPH_VIT_GET(vit), IGRAPH_OUT);
        for(long int i = 0; i < igraph_vector_int_size(&edges); i++){
            igraph_integer_t start, end;
            igraph_edge(graph, igraph_vector_int_get(&edges, i), &start, &end);
            cout << "\t(" << start << ", " << end << ", " 
                << "weight: " << igraph_cattribute_EAN(graph, "weight", igraph_vector_int_get(&edges, i)) << ", "
                << "variant: " << igraph_cattribute_EAN(graph, "variant" , igraph_vector_int_get(&edges, i)) << ", "
                //<< "initsol: " << igraph_cattribute_EAN(graph, "initsol" , igraph_vector_int_get(&edges, i)) 
                << ")" << endl; 
        }
        IGRAPH_VIT_NEXT(vit);
        cout << endl;
    }
    cout<< endl;
}
 
 
void read_edge_file(string edge_file_name, igraph_t* graph, int* num_variants){
 
    ifstream infile(edge_file_name);
 
    int num_vertices = -1;
 
    igraph_vector_int_t edges;
    igraph_vector_int_init(&edges, 0);
 
    int start_vertex, end_vertex;
    char edge_label;
    string variant_number;
 
    vector<edge_attributes> attributes_vector;
    int i = 0;
    while (infile >> start_vertex >> end_vertex >> edge_label >> variant_number)
    {
        if(start_vertex > num_vertices-1){
            num_vertices = start_vertex + 1;
        }
        if(end_vertex > num_vertices-1){
            num_vertices= end_vertex + 1;
        }
 
        igraph_real_t label;
        if(edge_label == 'A'){
            label = 0;
        }else if(edge_label == 'T'){
            label = 1;
        }else if(edge_label == 'C'){
            label = 2;
        }else if(edge_label == 'G'){
            label = 3;
        }else if(edge_label == 'N'){
            label = 4;
        }
 
        igraph_real_t variant;
 
        if(variant_number != "-"){
            attributes_vector.push_back({i, label, stod(variant_number.c_str())});
        }else{
            attributes_vector.push_back({i, label, -1});
        }
 
        //add edge
        igraph_vector_int_push_back(&edges, start_vertex);
        igraph_vector_int_push_back(&edges, end_vertex);
        i++;
    }
 
    bool directed = true;
    igraph_empty(graph, num_vertices, directed);
    igraph_add_edges(graph, &edges, NULL);
    igraph_vector_int_destroy(&edges);
 
    int max_variant = -1;
    for(edge_attributes a: attributes_vector){
        igraph_cattribute_EAN_set(graph, "label", a.edge_idx, a.label);
        igraph_cattribute_EAN_set(graph, "variant", a.edge_idx, a.variant);
        if(a.variant > max_variant){
            max_variant = a.variant;
        }
    }
    *num_variants = max_variant + 1;
 
}
 
 
void write_alignment_graph_to_file(igraph_t *graph, string file_name){
 
    string output = to_string(igraph_ecount(graph)) + "\n";
 
    igraph_es_t es;
    igraph_eit_t eit;
 
    igraph_es_all(&es, IGRAPH_EDGEORDER_ID);
    igraph_eit_create(graph, es, &eit);
 
    int source, sink;
 
    while (!IGRAPH_EIT_END(eit)) {
        igraph_integer_t start, end;
        igraph_edge(graph, IGRAPH_EIT_GET(eit), &start, &end);
        int weight = igraph_cattribute_EAN(graph, "weight", IGRAPH_EIT_GET(eit));
        int variant = igraph_cattribute_EAN(graph, "variant", IGRAPH_EIT_GET(eit));
        int initsol = igraph_cattribute_EAN(graph, "initsol", IGRAPH_EIT_GET(eit));
        output += to_string(start) + " " + to_string(end) + " " + to_string(weight) + " " + to_string(variant) + " " + to_string(initsol) + "\n";
 
        if(igraph_cattribute_VAN(graph, "startend", start) == 1){
            source = start;
        }
        if(igraph_cattribute_VAN(graph, "startend", end) == 2){
            sink = end;
        }
 
        IGRAPH_EIT_NEXT(eit);
    }
 
    igraph_es_destroy(&es);
    igraph_eit_destroy(&eit);
 
    output += to_string(source) + " " + to_string(sink);
 
    ofstream out_file(file_name);
    out_file << output;
    out_file.close();
 
 
}
 
 
void read_alignment_graph_from_file(igraph_t *graph, string file_name){
 
    ifstream in_file(file_name);
 
    int E;
    in_file >> E;
 
    if(E == 0){
        bool directed = true;
        igraph_empty(graph, 0, directed);
        return;
    }
 
    igraph_vector_int_t edges;
    igraph_vector_t weights;
    igraph_vector_t variants;
    igraph_vector_t initsols;
 
    igraph_vector_int_init(&edges, 2*E);
    igraph_vector_init(&weights, E);
    igraph_vector_init(&variants, E);
    igraph_vector_init(&initsols, E);
 
    int num_vertices = 0;
    int start, end; 
    float weight, variant, initsol;
 
    int i = 0;
    int j = 0;
    while (in_file >> start >> end >> weight >> variant >> initsol){
        //cout << start << " " << end << " " << weight << " " << variant << endl;
 
        //edges[i] = start;
        igraph_vector_int_set(&edges, i, start);
 
        //edges[i+1] = end;
        igraph_vector_int_set(&edges, i+1, end);
 
        i += 2;
 
        //weights[j] = weight;
        igraph_vector_set(&weights, j, weight);
 
        //variants[j] = variant;
        igraph_vector_set(&variants, j, variant);
 
        igraph_vector_set(&initsols, j, initsol);
 
        j++;
 
        if(start > num_vertices-1){
            num_vertices = start + 1;
        }
        if(end > num_vertices-1){
            num_vertices= end + 1;
        }
    }
 
    in_file.close();
 
    bool directed = true;
    igraph_empty(graph, num_vertices, directed);
    igraph_add_edges(graph, &edges, NULL);
 
    igraph_cattribute_EAN_setv(graph, "weight", &weights);
    igraph_cattribute_EAN_setv(graph, "variant", &variants);
    igraph_cattribute_EAN_setv(graph, "initsol", &initsols);
    igraph_cattribute_VAN_set(graph, "startend", start, 1);
    igraph_cattribute_VAN_set(graph, "startend", end, 2);
 
    igraph_vector_int_destroy(&edges);
    igraph_vector_destroy(&weights);
    igraph_vector_destroy(&variants);
    igraph_vector_destroy(&initsols);
 
}
 
 
void read_pos_substring_file(string pos_string_file_name, vector<int>& positions, vector<string>& substrings){
    ifstream infile(pos_string_file_name);
    string line;
 
    while (std::getline(infile, line)){
 
        int pos;
        string substring;
 
        istringstream iss(line); // separates line over spaces
        iss >> pos;
 
       if (line.size() > 0){
            while (iss >> substring){
                positions.push_back(pos);
                substrings.push_back(substring); 
            }
        }
    }
}
 
 
void get_reachable_vertex(igraph_t* graph, igraph_vs_t vertex_selector, int dist, igraph_vector_int_list_t* reachable_list){
 
    igraph_integer_t order = dist;
    igraph_integer_t mindist = 0;
 
    igraph_neighborhood(graph, reachable_list, vertex_selector, order, IGRAPH_OUT, mindist);
}
 
 
// obtains induced graph in time polylogarithmic in the size of the induced graph
// this is written because the native igraph library requires size proportional to the size of original graph
void get_induced_variation_graph(igraph_t* graph, igraph_vector_int_t* vertex_set, igraph_t* result){
    unordered_map<int, int> umap;
    int n = igraph_vector_int_size(vertex_set);
    for(int i = 0; i < n; i++){
        // unordered map records the existence of a vertex and gives it a new index
        umap[igraph_vector_int_get(vertex_set, i)] = i;
    }
 
    // tempory vector to incident edges for each vertex
    igraph_vector_int_t incident_edges;
    igraph_vector_int_init(&incident_edges, 0);
 
    igraph_vector_int_t induced_edges;
    igraph_vector_int_init(&induced_edges, 0);
 
    vector<edge_attributes> attributes_vector;
 
    int new_eid = 0;
    for(int i = 0; i < n; i++){
        igraph_incident(graph, &incident_edges, igraph_vector_int_get(vertex_set, i), IGRAPH_OUT);
 
        //cout << igraph_vector_int_get(vertex_set, i) << "~: ";
 
        int m_v = igraph_vector_int_size(&incident_edges);
        for (int j = 0; j < m_v; j++){
            igraph_integer_t start, end;
            int old_eid = igraph_vector_int_get(&incident_edges, j);
            igraph_edge(graph, old_eid, &start, &end);
 
            //cout << "(" << start << ", " << end << ") ";
 
            // check if end is in the vertex_set
            if(umap.find(end) != umap.end()){
                //add edge
                igraph_vector_int_push_back(&induced_edges, umap[start]);
                igraph_vector_int_push_back(&induced_edges, umap[end]);
                attributes_vector.push_back({new_eid, 
                    igraph_cattribute_EAN(graph, "label", old_eid), 
                    igraph_cattribute_EAN(graph, "variant", old_eid)});
                new_eid++;
            }
        }
        //cout << endl;
    }
    bool directed = true;
    igraph_empty(result, n, directed);
    igraph_add_edges(result, &induced_edges, NULL);
    igraph_vector_int_destroy(&induced_edges);
    igraph_vector_int_destroy(&incident_edges);
 
    for(edge_attributes a: attributes_vector){
        igraph_cattribute_EAN_set(result, "label", a.edge_idx, a.label);
        igraph_cattribute_EAN_set(result, "variant", a.edge_idx, a.variant);
    }
 
    //print_variation_graph(result);
}
 
 
void reverse_weighted_reachable(igraph_t* graph, igraph_integer_t start_vid, igraph_vector_int_t* result, int delta){
 
    // topologically sort the vertices of the reversed graph
    igraph_vector_int_t sorted_vertex;
    igraph_vector_int_init(&sorted_vertex, igraph_vcount(graph));
    igraph_topological_sorting(graph, &sorted_vertex, IGRAPH_IN);
    int n = igraph_vector_int_size(&sorted_vertex);
 
    //cout << "size = " << n << endl;
 
    // get start index
    int start_idx = -1;
 
    //cout << "reverse top order: ";
    for(int i = 0; i < n; i++){
        //cout << i << ":" << igraph_vector_int_get(&sorted_vertex, i) << ", ";
        if(start_vid == igraph_vector_int_get(&sorted_vertex, i)){
            start_idx = i;
            break;
        }
    }
    //cout << endl;
 
    vector<int> distance(n, INT_MAX-1);
    //cout << "index of start: " << igraph_vector_int_get(&sorted_vertex, start_idx) << endl;
    distance[igraph_vector_int_get(&sorted_vertex, start_idx)] = 0;
 
    igraph_vector_int_t incident_edges;
    igraph_vector_int_init(&incident_edges, 0);
 
    for(int i = start_idx; i < n; i++){
        igraph_integer_t vid = igraph_vector_int_get(&sorted_vertex, i);
        // update neightbors
        igraph_incident(graph, &incident_edges, vid, IGRAPH_IN);
        int m = igraph_vector_int_size(&incident_edges);
        //cout << "vid = " << vid  << endl;
        for(int i = 0; i < m; i++){
 
            igraph_integer_t start, end;
            igraph_edge(graph, igraph_vector_int_get(&incident_edges, i), &start, &end);
            int weight = igraph_cattribute_EAN(graph, "weight", igraph_vector_int_get(&incident_edges, i));
            //cout << "start = " << start << " end = " << end << " weight = " << weight << endl;
 
            if(distance[start] > distance[end] + weight){
                distance[start] = distance[end] + weight;
            }
        }
    }
 
    igraph_vector_int_destroy(&incident_edges);
    igraph_vector_int_destroy(&sorted_vertex);
 
    for(int i = 0; i < n; i++){
        //cout << i << ":" << distance[i] << ", ";
        if(distance[i] <= delta){
            igraph_vector_int_push_back(result, i);
        }
    }
 
}
 
 
/*
The main idea is that we consider the vertices of the alignment graph as laided out in |P||V| grid.
Each row of length |V| is sorted in the same topological order.
We hash x,y coordinates to track if a vertex as already been encountered and store as value the min dist
result graph should not be initialized
*/
void create_pruned_alignment_graph(igraph_t* graph, string pattern, int delta, igraph_t* result){
 
    // topologically sort the vertices, this will be used to get the delta_x for every edge considered
    igraph_vector_int_t sorted_vertex;
    igraph_vector_int_init(&sorted_vertex, igraph_vcount(graph));
    igraph_topological_sorting(graph, &sorted_vertex, IGRAPH_OUT);
    int n = igraph_vector_int_size(&sorted_vertex);
    vector<int> inv_sorted_vertex(n);
    for(int i = 0; i < n; i++){
        inv_sorted_vertex[igraph_vector_int_get(&sorted_vertex, i)] = i;
    }
 
    /*
    for(int i = 0; i < n; i++){
        cout << igraph_vector_int_get(&sorted_vertex, i) << ", ";
    }
    cout << endl;
    for(int i = 0; i < n; i++){
        cout << inv_sorted_vertex[i] << ", ";
    }
    cout << endl;
    */
 
    typedef struct vertex_struct{
        int id;
        int x;
        int y;
        int dist;
    }vertex;
 
    //  hash to track seen coordinates, distances are stored here, not in queue
    unordered_map<int, vertex> seen_coordinates;
 
    igraph_vector_int_t alignment_graph_edges; // start, end,   start, end, 
    vector <int> weights; 
    vector <int> variants;
 
    igraph_vector_int_init(&alignment_graph_edges, 0);
 
    int source_vertex_id = 0;
    int sink_vertex_id = 0;
 
    queue<vertex> q;
    vertex u = {0, inv_sorted_vertex[0], 0, 0};
    q.push(u);
 
    int new_vid = 1;
    igraph_vector_int_t incident_edges;
    igraph_vector_int_init(&incident_edges, 0);
 
    while(!q.empty()){
 
        vertex u = q.front();
        q.pop();
        igraph_integer_t old_uid = igraph_vector_int_get(&sorted_vertex, u.x);
 
 
        int u_coord = u.y * n + u.x;
        vertex u_ = seen_coordinates[u_coord];
        int u_dist = u_.dist;
 
        //cout << u.x << ", " << u.y << ": " << u_dist << endl;
 
        // vertices on same level (insertion)
        if(u_dist + 1 <= delta){
 
            igraph_incident(graph, &incident_edges, old_uid, IGRAPH_OUT);
            int m = igraph_vector_int_size(&incident_edges);
            //cout << "m = " << m << endl;
            for(int i = 0; i < m; i++){
 
                igraph_integer_t start, end;
                igraph_edge(graph, igraph_vector_int_get(&incident_edges, i), &start, &end);
 
                int v_x = inv_sorted_vertex[end];
                int v_y = u.y;
                int v_coordinate = v_y * n + v_x;
                int vid;
 
                if(seen_coordinates.find(v_coordinate) == seen_coordinates.end()){
                    // never encounter coordinate
                    // add vertex with new vertex id and edge
 
                    vid = new_vid;
                    seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist + 1};
                    new_vid++;
 
 
                    // enque vertex
                    q.push({vid, v_x, v_y, -1});
 
                }else{
                    // coordinate seen before 
                    vertex v = seen_coordinates[v_coordinate];
                    vid = v.id;
 
                    // update distance if needed
                    if(u_dist + 1 < v.dist){
                        seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist + 1};
                    }
                }
                igraph_vector_int_push_back(&alignment_graph_edges, u.id);
                igraph_vector_int_push_back(&alignment_graph_edges, vid);
                weights.push_back(1);
                variants.push_back(igraph_cattribute_EAN(graph, "variant", igraph_vector_int_get(&incident_edges, i)));
            }
        }
 
        // deletion edges
        if(u.y < pattern.length() && u_dist + 1 <= delta){
            int v_x = u.x;
            int v_y = u.y + 1;
            int v_coordinate = v_y * n + v_x;
 
            int vid;
            // never seen before
            if(seen_coordinates.find(v_coordinate) == seen_coordinates.end()){
 
                vid = new_vid;
                seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist + 1};
                new_vid++;
 
                // enque vertex
                q.push({vid, v_x, v_y, -1});
 
            }else{
                // coordinate seen before 
                vertex v = seen_coordinates[v_coordinate];
                vid = v.id;
 
                // update distance if needed
                if(u_dist + 1 < v.dist){
                    seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist + 1};
                }
            }
            igraph_vector_int_push_back(&alignment_graph_edges, u.id);
            igraph_vector_int_push_back(&alignment_graph_edges, vid);
            weights.push_back(1);
            variants.push_back(-2);
        }
 
        // sub/match edges
 
        if(u.y < pattern.length()){
            igraph_incident(graph, &incident_edges, old_uid, IGRAPH_OUT);
            int m = igraph_vector_int_size(&incident_edges);
 
            for(int i = 0; i < m; i++){
 
                // check if symbol matches
                int sym = (int) igraph_cattribute_EAN(graph, "label", igraph_vector_int_get(&incident_edges, i));
 
                //cout << "(" << u.x << ", " << u.y << ") sym: " << sym << endl;
                if(    (pattern[u.y] == 'A' && sym == 0) 
                    || (pattern[u.y] == 'T' && sym == 1)
                    || (pattern[u.y] == 'C' && sym == 2)
                    || (pattern[u.y] == 'G' && sym == 3)
                    || (pattern[u.y] == 'N' || sym == 4)
                    ){
 
                    igraph_integer_t start, end;
                    igraph_edge(graph, igraph_vector_int_get(&incident_edges, i), &start, &end);
 
                    int v_x = inv_sorted_vertex[end];
                    int v_y = u.y + 1;
                    int v_coordinate = v_y * n + v_x;
                    int vid;
 
                    if(seen_coordinates.find(v_coordinate) == seen_coordinates.end()){
                        // never encounter coordinate
                        // add vertex with new vertex id and edge
 
                        // Adds 0 to the distance from u
                        vid = new_vid;
                        seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist};
                        new_vid++;
 
                        // enque vertex
                        q.push({vid, v_x, v_y, -1});
 
                    }else{
                        // coordinate seen before 
                        vertex v = seen_coordinates[v_coordinate];
                        vid = v.id;
 
                        // update distance if needed
                        if(u_dist < v.dist){
                            seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist};
                        }
                    }
                    igraph_vector_int_push_back(&alignment_graph_edges, u.id);
                    igraph_vector_int_push_back(&alignment_graph_edges, vid);
                    weights.push_back(0);
                    variants.push_back(igraph_cattribute_EAN(graph, "variant", igraph_vector_int_get(&incident_edges, i)));
 
                }else if (u_dist + 1 <= delta){
 
                    igraph_integer_t start, end;
                    igraph_edge(graph, igraph_vector_int_get(&incident_edges, i), &start, &end);
 
                    int v_x = inv_sorted_vertex[end];
                    int v_y = u.y + 1;
                    int v_coordinate = v_y * n + v_x;
                    int vid;
 
                    if(seen_coordinates.find(v_coordinate) == seen_coordinates.end()){
                        // never encounter coordinate
                        // add vertex with new vertex id and edge
 
                        // Adds 1 to the distance from u
                        vid = new_vid;
                        seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist + 1};
                        new_vid++;
 
                        // enque vertex
                        q.push({vid, v_x, v_y, -1});
 
                    }else{
                        // coordinate seen before 
                        vertex v = seen_coordinates[v_coordinate];
                        vid = v.id;
 
                        // update distance if needed
                        if(u_dist + 1 < v.dist){
                            seen_coordinates[v_coordinate] = {vid, v_x, v_y, u_dist + 1};
                        }
                    }
                    igraph_vector_int_push_back(&alignment_graph_edges, u.id);
                    igraph_vector_int_push_back(&alignment_graph_edges, vid);
                    weights.push_back(1);
                    variants.push_back(igraph_cattribute_EAN(graph, "variant", igraph_vector_int_get(&incident_edges, i)));
                }
            }
        }
 
 
        // edges to sink vertex
 
        if(u.y == pattern.length()){
 
            int v_y = u.y+1;
            int v_coordinate = n * v_y;
 
            int vid;
 
            if(seen_coordinates.find(v_coordinate) == seen_coordinates.end()){
                vid = new_vid;
                seen_coordinates[v_coordinate] = {vid, 0, v_y, u_dist};
                sink_vertex_id = vid;
                new_vid++;
 
                //q.push({vid, 0, n*(pattern.length()+1), -1});
 
            }else{
                // coordinate seen before 
                vertex v = seen_coordinates[v_coordinate];
                vid = v.id;
 
                // update distance if needed
                if(u_dist < v.dist){
                    seen_coordinates[v_coordinate] = {vid, 0, v_y, u_dist};
                }
            }
 
            igraph_vector_int_push_back(&alignment_graph_edges, u.id);
            igraph_vector_int_push_back(&alignment_graph_edges, vid);
            weights.push_back(0);
            variants.push_back(-3);
 
        }
    }
    // construct temporary forward-pruned only alignment graph
    bool directed = true;
    igraph_t forward_pruned_only_graph;
    igraph_empty(&forward_pruned_only_graph, new_vid, directed);
    igraph_add_edges(&forward_pruned_only_graph, &alignment_graph_edges, NULL);
 
    for(int i = 0; i < weights.size(); i++){
        igraph_cattribute_EAN_set(&forward_pruned_only_graph, "weight", i, weights.at(i));
        igraph_cattribute_EAN_set(&forward_pruned_only_graph, "variant", i, variants.at(i));
    }
 
    igraph_vector_int_destroy(&alignment_graph_edges);
    igraph_vector_int_destroy(&sorted_vertex);
 
    igraph_vector_t zeros;
    igraph_vector_init(&zeros, igraph_vcount(&forward_pruned_only_graph));
    igraph_cattribute_VAN_setv(&forward_pruned_only_graph, "startend", &zeros);
    igraph_cattribute_VAN_set(&forward_pruned_only_graph, "startend", source_vertex_id, 1);
    igraph_cattribute_VAN_set(&forward_pruned_only_graph, "startend", sink_vertex_id, 2);
 
 
    //cout << "============= Forward Prunned Alignment Graph Constructed =============" << endl;
    //print_alignment_graph(&forward_pruned_only_graph);
    //cout << "Forward pruned alignment graph size: " << igraph_vcount(&forward_pruned_only_graph) << endl;
    // reverse pruning
 
    // get vertices reachable from the last vertex with distance at most delta
    igraph_vector_int_t reverse_reachable_vertex;
    igraph_vector_int_init(&reverse_reachable_vertex, 0);
 
    reverse_weighted_reachable(&forward_pruned_only_graph, sink_vertex_id, &reverse_reachable_vertex, delta);
 
    igraph_vs_t vs;
    igraph_vs_vector(&vs, &reverse_reachable_vertex);
 
    igraph_induced_subgraph(&forward_pruned_only_graph, result, vs, IGRAPH_SUBGRAPH_AUTO);
    igraph_destroy(&forward_pruned_only_graph);
    igraph_vector_int_destroy(&reverse_reachable_vertex);
 
} 
 
 
void add_initial_solution(igraph_t* alignment_graph){
 
    // get source and sink
    int start_vertex = 0;
    int end_vertex = 0;
    igraph_vs_t vs;
    igraph_vit_t vit;
    igraph_vs_all(&vs);
    igraph_vit_create(alignment_graph, vs, &vit);
    while (!IGRAPH_VIT_END(vit)) {
        int vid = IGRAPH_VIT_GET(vit);
        int startend = (int)igraph_cattribute_VAN(alignment_graph, "startend", vid);
        if(startend == 1){
            start_vertex = vid;
        }else if (startend == 2){
            end_vertex = vid;
        }
        IGRAPH_VIT_NEXT(vit);
    }
    igraph_vs_destroy(&vs);
    igraph_vit_destroy(&vit);
 
 
    // get edge weights
    igraph_es_t es;
    igraph_es_all(&es, IGRAPH_EDGEORDER_ID);
    igraph_vector_t weights;
    igraph_vector_init(&weights, 0);
    igraph_cattribute_EANV(alignment_graph, "weight", es, &weights);
    igraph_es_destroy(&es);
 
    // get path with minimum weight
    igraph_vector_int_t path_edges;
    igraph_vector_int_init(&path_edges, 0);
 
    //cout << "num vertex in graph: " << igraph_vcount(alignment_graph) << endl;
    //cout << "start:" << start_vertex << " end vertex: " << end_vertex << endl;
 
    igraph_get_shortest_path_dijkstra(alignment_graph, NULL, &path_edges, start_vertex, end_vertex, &weights, IGRAPH_OUT);
    igraph_vector_destroy(&weights);
 
    // put it in attribute vector
    igraph_vector_t attribute_vector;
    igraph_vector_init(&attribute_vector, igraph_ecount(alignment_graph));
    int m = igraph_vector_int_size(&path_edges);
    for(int i = 0; i < m; i++){
        int eid = igraph_vector_int_get(&path_edges, i);
        //int weight = igraph_cattribute_EAN(alignment_graph, "weight", eid);
        //cout << "edge id: " << eid << " weight: " << weight << endl;
        igraph_vector_set(&attribute_vector, eid, 1);
    }
    igraph_vector_int_destroy(&path_edges);
 
    // set edge attrbitue
    igraph_cattribute_EAN_setv(alignment_graph, "initsol", &attribute_vector);
    igraph_vector_destroy(&attribute_vector);
 
}
 
void create_alignment_graph(igraph_t* variation_graph, int pos, string s, int alpha, int delta, igraph_t* alignment_graph){
 
    igraph_vs_t start_vertex_selector;
    igraph_vs_1(&start_vertex_selector, pos);
 
    igraph_vector_int_list_t reachable_vertex_list;
    igraph_vector_int_list_init(&reachable_vertex_list, 0);
 
    get_reachable_vertex(variation_graph, start_vertex_selector, alpha + delta, &reachable_vertex_list);
    igraph_vs_destroy(&start_vertex_selector);
 
    // since vertex selector is only for one vertex, we only need the first element
    igraph_vector_int_t* reachable_vertex = igraph_vector_int_list_get_ptr(&reachable_vertex_list, 0);
 
    igraph_t reachable_graph;
    get_induced_variation_graph(variation_graph, reachable_vertex, &reachable_graph);
 
 
    //cout << "induced variation graph size: " << igraph_vcount(&reachable_graph) << endl;
 
    int start_vertex, end_vertex;
    create_pruned_alignment_graph(&reachable_graph, s, delta, alignment_graph);
 
    //cout << "pruned alignment graph size: " << igraph_vcount(alignment_graph) << endl;
 
    add_initial_solution(alignment_graph);
 
    igraph_vector_int_list_destroy(&reachable_vertex_list);
    igraph_destroy(&reachable_graph);
}
 
 
void get_variants(igraph_t* g, unordered_set<int>& variants){
 
    igraph_es_t es;
    igraph_es_all(&es, IGRAPH_EDGEORDER_ID);
    igraph_eit_t eit;
    igraph_eit_create(g, es, &eit);
 
    while (!IGRAPH_EIT_END(eit)) {
        int variant = igraph_cattribute_EAN(g, "variant" ,IGRAPH_EIT_GET(eit));
        if(variant >= 0){
            variants.insert(variant);
        }
 
        IGRAPH_EIT_NEXT(eit);
    }
    igraph_es_destroy(&es);
    igraph_eit_destroy(&eit);
}
 
 
// returns a vector that assigns each alignment graph to a set using an integer
// also prints the number of sets and size of each corresponding ILP
void analyze_alignment_graph_set(int num_variants,
                                vector<vector<int>*>& alignment_graph_to_variants,
                                vector<int>& global_variable_to_component,
                                vector<int>& subILP_to_component,
                                vector<int>& global_variable_to_local_idx,
                                vector<int>& component_to_global_variable_count,
                                vector<vector<int>>& component_to_subILPs,
                                int* num_components
                                ){
 
 
    igraph_vector_int_t edges;
    igraph_vector_int_init(&edges, 0);
 
    int ilp_idx = num_variants;
 
    for(int i = 0; i < alignment_graph_to_variants.size(); i++){
        //print_alignment_graph(&g);
 
        // obtain set of variants
        //unordered_set<int> variants;
        //get_variants(&g, variants);
 
        // add edges for bipartite graph
        //cout << i << ": ";
        for(int v: *alignment_graph_to_variants[i]){
            //cout << v << ", ";
            igraph_vector_int_push_back(&edges, ilp_idx);
            igraph_vector_int_push_back(&edges, v);
        }
        //cout << endl;
        ilp_idx++;
 
    }
    int n = num_variants + alignment_graph_to_variants.size();
 
    bool directed = false;
    igraph_t bipartite;
    igraph_empty(&bipartite, n, directed);
    igraph_add_edges(&bipartite, &edges, NULL);
 
    igraph_vector_int_destroy(&edges);
 
    igraph_vector_int_t membership;
    igraph_vector_int_init(&membership, n);
    igraph_connected_components(&bipartite, &membership, NULL, NULL, IGRAPH_STRONG);
 
 
    global_variable_to_component = vector<int>(num_variants);
    subILP_to_component = vector<int>(alignment_graph_to_variants.size());
    global_variable_to_local_idx = vector<int>(num_variants);
 
    unordered_map<int, int> sizes;
 
    *num_components = 0;
    for(int i = 0; i < n; i++){
 
        int component = igraph_vector_int_get(&membership, i);
        if(component + 1 > *num_components){
            *num_components = component + 1;
        }
 
        if(i < num_variants){
 
            global_variable_to_component[i] = component;
 
            if(sizes.find(component) == sizes.end()){
                sizes[component] = 1;
            }else{
                sizes[component] = sizes[component] + 1;
            }
            global_variable_to_local_idx[i] = sizes[component] - 1;
 
        }else{
            subILP_to_component[i - num_variants] = component;
        }
    }
 
 
    component_to_global_variable_count = vector<int>(*num_components, 0);
    component_to_subILPs = vector<vector<int>>(*num_components);
    for (auto size : sizes){
        component_to_global_variable_count[size.first] = size.second;
        component_to_subILPs[size.first] = vector<int>();
    }
 
    // clean up
    igraph_vector_int_destroy(&membership);
 
 
    // print statements for debugging
    if(VERBOSE){
        cout << "Global variable to component" << endl;
        for(int i = 0; i < global_variable_to_component.size(); i++){
            cout << "x_" << i << ": " << global_variable_to_component[i] << ", local:" << global_variable_to_local_idx[i] << endl;
        }
 
        cout << "\nSubILP to component" << endl;
        for(int i = 0; i < subILP_to_component.size(); i++){
            cout << "ILP_" << i << ": " << subILP_to_component[i] << endl;
        }
    }
 
    /*
    cout << "\nComponent to global variant count:\n" << endl;
    cout << "[";
    for(int i = 0; i < component_to_global_variable_count.size(); i++){
        //cout << "component_" << i << " has variants: " << component_to_global_variable_count[i] << endl;
        cout << component_to_global_variable_count[i] << ", ";
    }
    cout << "]" << endl;
    */
 
    unordered_map<int, int> component_to_num_edges;
    for(int i = 0; i < alignment_graph_to_variants.size(); i++){
 
        //igraph_t g = alignment_graphs.at(i);
        int component = subILP_to_component[i];
        component_to_subILPs[component].push_back(i);
        /*
        if(component_to_num_edges.find(component) == component_to_num_edges.end()){
            component_to_num_edges[component] = igraph_ecount(&g);
        }else{
            component_to_num_edges[component] = component_to_num_edges[component] + igraph_ecount(&g);
        }
        */
    }
    /*
    for(int i = 0; i < component_to_global_variable_count.size(); i++){
        cout << "component_" << i << " has total variables: " << component_to_global_variable_count[i] + component_to_num_edges[i] << endl;
    }
    */
}
 
 
void construct_ILPs(int component,
                    vector<vector<int>>& component_to_subILPs,
                    vector<int>& global_variable_to_local_idx,
                    vector<int>& component_to_global_variable_count,
                    GRBModel& model,
                    int delta,
                    string graph_directory,
                    vector<igraph_t*>& alignment_graphs,
                    bool use_files
                    ){
 
 
    GRBVar* global_var = model.addVars(component_to_global_variable_count[component]);
 
    GRBLinExpr obj = GRBLinExpr();
    for(int i = 0; i < component_to_global_variable_count[component]; i++){
        obj += global_var[i];
 
        global_var[i].set(GRB_DoubleAttr_Start, 0);
    }
    model.setObjective(obj, GRB_MAXIMIZE);
 
 
    if(PRINT_COMPONENT_SIZES){
        cout << "\nComponent "<< component << " has size (number of alignment graphs): " << component_to_subILPs[component].size() << endl;
    }
 
    for(int i = 0; i < component_to_subILPs[component].size(); i++){
 
        auto start = chrono::steady_clock::now();
 
        int alignment_graph_idx = component_to_subILPs[component][i];
 
        igraph_t alignment_graph;
 
        if(use_files == 1){
            string file_name = graph_directory + "g_" + to_string(alignment_graph_idx);
            //cout << file_name << endl;
            read_alignment_graph_from_file(&alignment_graph, file_name);
        }else{
            alignment_graph = *alignment_graphs[alignment_graph_idx];
        }
 
        if(igraph_ecount(&alignment_graph) == 0){
            cout << "no edges in alignment graph." << endl;
            continue;
        }
 
        /*
        if(VERBOSE){
            cout << "Alignment_graph_" << i << " ILP construction in component (model): " << component << endl;
        }else if(!VERBOSE && i % 1 == 0){
            cout << "Constructing ILP for alignment_graph: " << i << " out of " << component_to_subILPs[component].size() << " (increments of 1)" << endl;
        }
        */
 
        GRBVar* local_var = model.addVars(igraph_ecount(&alignment_graph), GRB_BINARY);
 
        igraph_vs_t vs;
        igraph_vit_t vit;
        igraph_bool_t loops = true;     // there are no loops, this is to get const. query time for degrees
 
        igraph_vs_all(&vs);
        igraph_vit_create(&alignment_graph, vs, &vit);
 
 
        while (!IGRAPH_VIT_END(vit)) {
 
            int vid = IGRAPH_VIT_GET(vit);
 
            igraph_integer_t in_degree, out_degree;
            igraph_degree_1(&alignment_graph, &in_degree, vid, IGRAPH_IN, loops);
            igraph_degree_1(&alignment_graph, &out_degree, vid, IGRAPH_OUT, loops);
 
            /*
            cout << "graph: " << i << " vertex: " << vid 
                << " in-degree: " << in_degree 
                << " out-degree: " << out_degree
                << " startend: " << igraph_cattribute_VAN(&alignment_graphs[i], "startend", vid) 
                << endl;
            */
 
            GRBLinExpr lhs, rhs;
            if(igraph_cattribute_VAN(&alignment_graph, "startend", vid) == 1){
                lhs = GRBLinExpr(1);
                rhs = GRBLinExpr();
 
                // iterate through outbound edges
                igraph_vector_int_t edges;
                igraph_vector_int_init(&edges, 0);
                igraph_incident(&alignment_graph, &edges, vid, IGRAPH_OUT);
                int m = igraph_vector_int_size(&edges);
                for(int j = 0; j < m; j++){
                    rhs += local_var[igraph_vector_int_get(&edges, j)];
                }
                igraph_vector_int_destroy(&edges);
 
            }else if(igraph_cattribute_VAN(&alignment_graph, "startend", vid) == 2){
                lhs = GRBLinExpr();
                rhs = GRBLinExpr(1);
 
                // iterate through inbound edges
                igraph_vector_int_t edges;
                igraph_vector_int_init(&edges, 0);
                igraph_incident(&alignment_graph, &edges, vid, IGRAPH_IN);
                int m = igraph_vector_int_size(&edges);
                for(int j = 0; j < m; j++){
                    lhs += local_var[igraph_vector_int_get(&edges, j)];
                }
                igraph_vector_int_destroy(&edges);                
 
            }else{
                lhs = GRBLinExpr();
                rhs = GRBLinExpr();
 
                igraph_vector_int_t edges;
                igraph_vector_int_init(&edges, 0);
 
                // iterate through in bound edges
                igraph_incident(&alignment_graph, &edges, vid, IGRAPH_IN);
                int m = igraph_vector_int_size(&edges);
                for(int j = 0; j < m; j++){
                    lhs += local_var[igraph_vector_int_get(&edges, j)];
                }
 
                // iterate through outbound edges
                igraph_incident(&alignment_graph, &edges, vid, IGRAPH_OUT);
                m = igraph_vector_int_size(&edges);
                for(int j = 0; j < m; j++){
                    rhs += local_var[igraph_vector_int_get(&edges, j)];
                }
 
                igraph_vector_int_destroy(&edges);  
 
            }
 
            model.addConstr(lhs, GRB_EQUAL, rhs);
            IGRAPH_VIT_NEXT(vit);
        }
 
        igraph_vs_destroy(&vs);
        igraph_vit_destroy(&vit);
 
        // add binding constraints and delta constraint
        igraph_es_t es;
        igraph_eit_t eit;
        igraph_es_all(&es, IGRAPH_EDGEORDER_ID);
        igraph_eit_create(&alignment_graph, es, &eit);
 
        GRBLinExpr delta_constraint_rhs = GRBLinExpr(delta);
        GRBLinExpr delta_constraint_lhs = GRBLinExpr();
 
        while(!IGRAPH_EIT_END(eit)){
            int eid = IGRAPH_EIT_GET(eit);
            int variant = igraph_cattribute_EAN(&alignment_graph, "variant", eid);
            if(variant >= 0){
                int idx = global_variable_to_local_idx[variant];
 
                GRBLinExpr lhs = GRBLinExpr();
                lhs += global_var[idx];
                lhs += local_var[eid];
                GRBLinExpr rhs = GRBLinExpr(1);
                model.addConstr(lhs, GRB_LESS_EQUAL, rhs);
            }
 
            delta_constraint_lhs += igraph_cattribute_EAN(&alignment_graph, "weight", eid)*local_var[eid];
 
 
            // added for feasibility check of initsol, delete afterward
            /*
            GRBLinExpr lhs = GRBLinExpr();
            lhs += local_var[eid];
            GRBLinExpr rhs = GRBLinExpr((int)igraph_cattribute_EAN(&alignment_graph, "initsol", eid));
            model.addConstr(lhs, GRB_EQUAL, rhs);
            */
 
            local_var[eid].set(GRB_DoubleAttr_Start , (int)igraph_cattribute_EAN(&alignment_graph, "initsol", eid));
 
 
            IGRAPH_EIT_NEXT(eit);
        }
 
        model.addConstr(delta_constraint_lhs, GRB_LESS_EQUAL, delta_constraint_rhs);
 
        igraph_es_destroy(&es);
        igraph_eit_destroy(&eit);
 
        /*
        if(VERBOSE){
            auto stop = chrono::steady_clock::now();
            auto duration = duration_cast<chrono::milliseconds>(stop - start);
            cout << "\tTime for alignment_graph_" << alignment_graph_idx << " ILP construction: " << duration.count() << " milliseconds" 
                " component (model): " << component << endl;
        }
        */
        igraph_destroy(&alignment_graph);
    }
 
    // update and view models for checking
    model.update();
    if(WRITE_ILPS_TO_FILE){
        string file_name = "model_" + to_string(component) + ".lp";
        model.write(file_name);
    }
 
}
 
 
int main(int argc, char** argv){
 
    GRBEnv env = GRBEnv();
    env.set("OutputFlag", "0");
    env.start();
 
    if(argc < 8){
        cout << "Wrong number of arguments provided" << endl;
        return 0;
    }
    string edge_file_name = argv[1];
    string pos_substring_file_name = argv[2];
    string scratch_directory = argv[3];
    string sol_directory = argv[4];
    int alpha = atoi(argv[5]);
    int delta = atoi(argv[6]);
    int use_files = atoi(argv[7]);
 
    igraph_set_attribute_table(&igraph_cattribute_table);
 
    // construct variation graph
    igraph_t variation_graph;
    int num_variants;
 
    read_edge_file(edge_file_name, &variation_graph, &num_variants);
 
    cout << "\n============= Variation Graph Constructed =============\n" << endl;
    //cout << "Construction time: " << duration.count() << " milliseconds\n" <<endl;
    cout << "Number of variants: " << num_variants << endl;
    cout << "Number of vertices: " << igraph_vcount(&variation_graph) << endl;
    cout << "Number of edges: " << igraph_ecount(&variation_graph) << endl;
 
    cout << "\nReading pos_substring file...\n" << endl;
    // read locations and strings
    vector<int> positions;
    vector<string> substrings;
 
    read_pos_substring_file(pos_substring_file_name, positions, substrings);
 
    int N = positions.size();
 
    cout << "\nConstructing alignment graphs...\n" << endl;
    vector<vector<int>*> alignment_graph_to_variants = vector<vector<int>*>(N);
 
 
    vector<igraph_t*> alignment_graphs;
    for(int i = 0; i < N; i++){ 
        alignment_graphs.push_back(new igraph_t); 
    }
 
    #pragma omp parallel for
    for(int i = 0; i < N; i++){     
        if(VERBOSE){
            cout << "Constructing alignment graphs for position: " << positions[i] << endl;
        }else if (!VERBOSE && i % PRINT_FACTOR == 0){
            cout << "Constructing alignment graph: " << i << " (prints mod " << PRINT_FACTOR << ")" << endl;
        }
 
        igraph_t alignment_graph;
        create_alignment_graph(&variation_graph, positions[i], substrings[i], alpha, delta, &alignment_graph);
 
        // obtain set of variants
        alignment_graph_to_variants[i] = new vector<int>;
        unordered_set<int> variants;
        get_variants(&alignment_graph, variants);
 
        for(int v: variants){
            alignment_graph_to_variants[i]->push_back(v);
        }
 
        igraph_cattribute_GAN_set(&alignment_graph, "position", positions[i]);
        igraph_cattribute_GAS_set(&alignment_graph, "substring", substrings[i].c_str());
 
        if(use_files == 1){
            string file_name = scratch_directory + "g_" + to_string(i);        
            write_alignment_graph_to_file(&alignment_graph, file_name);
        }else{
            igraph_copy(alignment_graphs[i], &alignment_graph);
        }
 
 
        //sum_of_sizes += igraph_ecount(&alignment_graph);
 
        igraph_destroy(&alignment_graph);
    }
 
    //cout << "average alignment graph size: " << (float)sum_of_sizes/(float)N << endl;
 
 
    positions.clear();
    positions.shrink_to_fit();
    substrings.clear();
    substrings.shrink_to_fit();
 
    igraph_destroy(&variation_graph);
    cout << "\n============= Alignment Graphs Constructed =============\n" << endl;
 
    cout << "Analyzing alignment graph set..." << endl;
 
    vector<int> global_variable_to_component;
    vector<int> subILP_to_component;
    vector<int> global_variable_to_local_idx;
    vector<int> component_to_variant_count;
    vector<vector<int>> component_to_subILPs;
    int num_components;
    analyze_alignment_graph_set(num_variants,
                                alignment_graph_to_variants, 
                                global_variable_to_component, 
                                subILP_to_component, 
                                global_variable_to_local_idx, 
                                component_to_variant_count,
                                component_to_subILPs,
                                &num_components);
 
    alignment_graph_to_variants.clear();
    alignment_graph_to_variants.shrink_to_fit();
 
    cout << "\n============= Alignment Graphs Analyzed =============\n" << endl;
    cout << "number of components: " << num_components << endl;
 
    // we need to invert the map from separate ILPs
    map<pair<int, int>, int> component_index_pair_to_variant;
    for(int i = 0; i < num_variants; i++){
 
        auto p = make_pair(global_variable_to_component[i], global_variable_to_local_idx[i]);
 
        if(component_index_pair_to_variant.find(p) == component_index_pair_to_variant.end()){
            component_index_pair_to_variant[p] = i;
        }
    }
 
 
    cout << "\nConstructing ILP models from alignment graphs...\n" << endl;
 
    vector<int> solution = vector<int>(num_variants, 1);
 
    bool some_ILP_timed_out = false;
 
    #pragma omp parallel for
    for(int component = 0; component < num_components; component++){
 
        if(component % PRINT_FACTOR == 0){
            cout << "Solving ILP_" << component << " out of " <<  num_components << " (prints mod " << PRINT_FACTOR << ")" <<endl;
        }
 
        //cout << "Solving ILP_" << component << " out of " <<  num_components << endl;
 
 
        //cout << "component: " << component << endl; 
        if(component_to_subILPs[component].size() > 0){
 
            GRBModel model = GRBModel(env);
 
            construct_ILPs(component,
                            component_to_subILPs,
                            global_variable_to_local_idx, 
                            component_to_variant_count,
                            model,
                            delta,
                            scratch_directory,
                            alignment_graphs,
                            use_files
                            );
            //cout << "\n============= ILP model "<< component << " constructed =============\n" << endl;
 
 
            model.getEnv().set(GRB_DoubleParam_TimeLimit, ILP_TIME_LIMIT);
            auto start = chrono::steady_clock::now();
            model.optimize();
            auto stop = chrono::steady_clock::now();
            auto duration = duration_cast<chrono::seconds>(stop - start);
 
            if(duration.count() > .95 * ILP_TIME_LIMIT){
                cout << "ILP was timed out" << endl;
                some_ILP_timed_out = true;
            }
            //if(VERBOSE){
            //    cout << "time: " << duration.count() << " milliseconds\n" <<endl;
            //}
 
            //cout << "\n============= ILP models solved =============\n" << endl;
 
            GRBVar* vars = NULL;
            vars = model.getVars();
            //cout << "ILP_" << component << " local assignments: " << endl;
            //cout << "variable count: " << component_to_variant_count[component] << endl;
            for (int j = 0; j < component_to_variant_count[component]; j++) {
                //cout << vars[j].get(GRB_StringAttr_VarName) << " = " << vars[j].get(GRB_DoubleAttr_X) << endl;
                solution[component_index_pair_to_variant[make_pair(component, j)]] = vars[j].get(GRB_DoubleAttr_X);
            }
        }
 
    }
 
    int sum = 0;
    cout << "\nFinal assignment: " << endl;
 
 
    string sol_file_name = sol_directory + "ILP_sol_" + to_string(alpha) + "_" + to_string(delta) + "_" + to_string(N);
    ofstream out_file(sol_file_name);
    for(int i = 0; i < solution.size(); i++){
        cout << "x_" << i << " = " << solution[i] << endl;
        out_file << solution[i] << endl;
        sum += solution[i];
    }
    out_file.close();
    cout << "\nNumber of variants deleted: " << sum << " out of " << num_variants <<endl;
    if(some_ILP_timed_out){
        cout << "Some ILP was timed-out, solution may be sub-optimal" << endl;
    }else{
        cout << "No ILPs were timed-out, solution is optimal" << endl;
    }
 
 
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGZzdHJlYW0+CiNpbmNsdWRlIDxpZ3JhcGguaD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxjaHJvbm8+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSAiZ3Vyb2JpX2MrKy5oIgoKI2RlZmluZSBWRVJCT1NFIGZhbHNlCiNkZWZpbmUgV1JJVEVfSUxQU19UT19GSUxFIGZhbHNlCiNkZWZpbmUgUFJJTlRfQ09NUE9ORU5UX1NJWkVTIGZhbHNlCiNkZWZpbmUgUFJJTlRfRkFDVE9SIDEwMAojZGVmaW5lIElMUF9USU1FX0xJTUlUIDM2MDAgLy8gaW4gc2Vjb25kcwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgc3RydWN0IGVkZ2VfYXR0cmlidXRlc19zdHJ1Y3R7CiAgICBpZ3JhcGhfaW50ZWdlcl90IGVkZ2VfaWR4OwogICAgaWdyYXBoX3JlYWxfdCBsYWJlbDsKICAgIGlncmFwaF9yZWFsX3QgdmFyaWFudDsKfWVkZ2VfYXR0cmlidXRlczsKCgp2b2lkIHByaW50X3ZhcmlhdGlvbl9ncmFwaChjb25zdCBpZ3JhcGhfdCAqZ3JhcGgpewogICAgaWdyYXBoX3ZzX3QgdnM7CiAgICBpZ3JhcGhfdml0X3Qgdml0OwoKICAgIGlncmFwaF92c19hbGwoJnZzKTsKICAgIGlncmFwaF92aXRfY3JlYXRlKGdyYXBoLCB2cywgJnZpdCk7CiAgICB3aGlsZSAoIUlHUkFQSF9WSVRfRU5EKHZpdCkpIHsKICAgICAgICBjb3V0IDw8IElHUkFQSF9WSVRfR0VUKHZpdCkgPDwgIjogIiA8PCBlbmRsOwoKICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF90IGVkZ2VzOwogICAgICAgIGlncmFwaF92ZWN0b3JfaW50X2luaXQoJmVkZ2VzLCAwKTsKICAgICAgICBpZ3JhcGhfaW5jaWRlbnQoZ3JhcGgsICZlZGdlcywgSUdSQVBIX1ZJVF9HRVQodml0KSwgSUdSQVBIX09VVCk7CiAgICAgICAgZm9yKGxvbmcgaW50IGkgPSAwOyBpIDwgaWdyYXBoX3ZlY3Rvcl9pbnRfc2l6ZSgmZWRnZXMpOyBpKyspewogICAgICAgICAgICBpZ3JhcGhfaW50ZWdlcl90IHN0YXJ0LCBlbmQ7CiAgICAgICAgICAgIGlncmFwaF9lZGdlKGdyYXBoLCBpZ3JhcGhfdmVjdG9yX2ludF9nZXQoJmVkZ2VzLCBpKSwgJnN0YXJ0LCAmZW5kKTsKICAgICAgICAgICAgY291dCA8PCAiXHQoIiA8PCBzdGFydCA8PCAiLCAiIDw8IGVuZCA8PCAiLCAiIAogICAgICAgICAgICAgICAgPDwgImxhYmVsOiAiIDw8IGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgImxhYmVsIiwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZlZGdlcywgaSkpIDw8ICIsICIKICAgICAgICAgICAgICAgIDw8ICJ2YXJpYW50OiAiIDw8IGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgInZhcmlhbnQiICwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZlZGdlcywgaSkpIDw8ICIpIiA8PCBlbmRsOyAKICAgICAgICAgICAgOwogICAgICAgIH0KICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZlZGdlcyk7CiAgICAgICAgSUdSQVBIX1ZJVF9ORVhUKHZpdCk7CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQogICAgY291dDw8IGVuZGw7Cn0KCgp2b2lkIHByaW50X2FsaWdubWVudF9ncmFwaChpZ3JhcGhfdCAqZ3JhcGgpewoKICAgIGNvdXQgPDwgIlxuUHJpbnRpbmcgYWxpZ25tZW50IGdyYXBoOiIgPDwgZW5kbDsKICAgIGNvdXQgPDwgInBvcyA9ICIgPDwgaWdyYXBoX2NhdHRyaWJ1dGVfR0FOKGdyYXBoLCAicG9zaXRpb24iKQogICAgICAgIDw8ICIsIHN1YnN0cmluZyA9ICIgPDwgaWdyYXBoX2NhdHRyaWJ1dGVfR0FTKGdyYXBoLCAic3Vic3RyaW5nIikgPDwgZW5kbDsKCiAgICBpZ3JhcGhfdnNfdCB2czsKICAgIGlncmFwaF92aXRfdCB2aXQ7CgogICAgaWdyYXBoX3ZzX2FsbCgmdnMpOwogICAgaWdyYXBoX3ZpdF9jcmVhdGUoZ3JhcGgsIHZzLCAmdml0KTsKICAgIHdoaWxlICghSUdSQVBIX1ZJVF9FTkQodml0KSkgewogICAgICAgIGNvdXQgPDwgSUdSQVBIX1ZJVF9HRVQodml0KSAgCiAgICAgICAgICAgIDw8ICIgc3RhcnRlbmQ6ICIgPDwgaWdyYXBoX2NhdHRyaWJ1dGVfVkFOKGdyYXBoLCAic3RhcnRlbmQiLCBJR1JBUEhfVklUX0dFVCh2aXQpKSAgCiAgICAgICAgICAgIDw8IGVuZGw7CgogICAgICAgIGlncmFwaF92ZWN0b3JfaW50X3QgZWRnZXM7CiAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmZWRnZXMsIDApOwogICAgICAgIGlncmFwaF9pbmNpZGVudChncmFwaCwgJmVkZ2VzLCBJR1JBUEhfVklUX0dFVCh2aXQpLCBJR1JBUEhfT1VUKTsKICAgICAgICBmb3IobG9uZyBpbnQgaSA9IDA7IGkgPCBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKCZlZGdlcyk7IGkrKyl7CiAgICAgICAgICAgIGlncmFwaF9pbnRlZ2VyX3Qgc3RhcnQsIGVuZDsKICAgICAgICAgICAgaWdyYXBoX2VkZ2UoZ3JhcGgsIGlncmFwaF92ZWN0b3JfaW50X2dldCgmZWRnZXMsIGkpLCAmc3RhcnQsICZlbmQpOwogICAgICAgICAgICBjb3V0IDw8ICJcdCgiIDw8IHN0YXJ0IDw8ICIsICIgPDwgZW5kIDw8ICIsICIgCiAgICAgICAgICAgICAgICA8PCAid2VpZ2h0OiAiIDw8IGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgIndlaWdodCIsIGlncmFwaF92ZWN0b3JfaW50X2dldCgmZWRnZXMsIGkpKSA8PCAiLCAiCiAgICAgICAgICAgICAgICA8PCAidmFyaWFudDogIiA8PCBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oZ3JhcGgsICJ2YXJpYW50IiAsIGlncmFwaF92ZWN0b3JfaW50X2dldCgmZWRnZXMsIGkpKSA8PCAiLCAiCiAgICAgICAgICAgICAgICAvLzw8ICJpbml0c29sOiAiIDw8IGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgImluaXRzb2wiICwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZlZGdlcywgaSkpIAogICAgICAgICAgICAgICAgPDwgIikiIDw8IGVuZGw7IAogICAgICAgIH0KICAgICAgICBJR1JBUEhfVklUX05FWFQodml0KTsKICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICB9CiAgICBjb3V0PDwgZW5kbDsKfQoKCnZvaWQgcmVhZF9lZGdlX2ZpbGUoc3RyaW5nIGVkZ2VfZmlsZV9uYW1lLCBpZ3JhcGhfdCogZ3JhcGgsIGludCogbnVtX3ZhcmlhbnRzKXsKICAgIAogICAgaWZzdHJlYW0gaW5maWxlKGVkZ2VfZmlsZV9uYW1lKTsKCiAgICBpbnQgbnVtX3ZlcnRpY2VzID0gLTE7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBlZGdlczsKICAgIGlncmFwaF92ZWN0b3JfaW50X2luaXQoJmVkZ2VzLCAwKTsKCiAgICBpbnQgc3RhcnRfdmVydGV4LCBlbmRfdmVydGV4OwogICAgY2hhciBlZGdlX2xhYmVsOwogICAgc3RyaW5nIHZhcmlhbnRfbnVtYmVyOwoKICAgIHZlY3RvcjxlZGdlX2F0dHJpYnV0ZXM+IGF0dHJpYnV0ZXNfdmVjdG9yOwogICAgaW50IGkgPSAwOwogICAgd2hpbGUgKGluZmlsZSA+PiBzdGFydF92ZXJ0ZXggPj4gZW5kX3ZlcnRleCA+PiBlZGdlX2xhYmVsID4+IHZhcmlhbnRfbnVtYmVyKQogICAgewogICAgICAgIGlmKHN0YXJ0X3ZlcnRleCA+IG51bV92ZXJ0aWNlcy0xKXsKICAgICAgICAgICAgbnVtX3ZlcnRpY2VzID0gc3RhcnRfdmVydGV4ICsgMTsKICAgICAgICB9CiAgICAgICAgaWYoZW5kX3ZlcnRleCA+IG51bV92ZXJ0aWNlcy0xKXsKICAgICAgICAgICAgbnVtX3ZlcnRpY2VzPSBlbmRfdmVydGV4ICsgMTsKICAgICAgICB9CgogICAgICAgIGlncmFwaF9yZWFsX3QgbGFiZWw7CiAgICAgICAgaWYoZWRnZV9sYWJlbCA9PSAnQScpewogICAgICAgICAgICBsYWJlbCA9IDA7CiAgICAgICAgfWVsc2UgaWYoZWRnZV9sYWJlbCA9PSAnVCcpewogICAgICAgICAgICBsYWJlbCA9IDE7CiAgICAgICAgfWVsc2UgaWYoZWRnZV9sYWJlbCA9PSAnQycpewogICAgICAgICAgICBsYWJlbCA9IDI7CiAgICAgICAgfWVsc2UgaWYoZWRnZV9sYWJlbCA9PSAnRycpewogICAgICAgICAgICBsYWJlbCA9IDM7CiAgICAgICAgfWVsc2UgaWYoZWRnZV9sYWJlbCA9PSAnTicpewogICAgICAgICAgICBsYWJlbCA9IDQ7CiAgICAgICAgfQoKICAgICAgICBpZ3JhcGhfcmVhbF90IHZhcmlhbnQ7CgogICAgICAgIGlmKHZhcmlhbnRfbnVtYmVyICE9ICItIil7CiAgICAgICAgICAgIGF0dHJpYnV0ZXNfdmVjdG9yLnB1c2hfYmFjayh7aSwgbGFiZWwsIHN0b2QodmFyaWFudF9udW1iZXIuY19zdHIoKSl9KTsKICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgYXR0cmlidXRlc192ZWN0b3IucHVzaF9iYWNrKHtpLCBsYWJlbCwgLTF9KTsKICAgICAgICB9CgogICAgICAgIC8vYWRkIGVkZ2UKICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9wdXNoX2JhY2soJmVkZ2VzLCBzdGFydF92ZXJ0ZXgpOwogICAgICAgIGlncmFwaF92ZWN0b3JfaW50X3B1c2hfYmFjaygmZWRnZXMsIGVuZF92ZXJ0ZXgpOwogICAgICAgIGkrKzsKICAgIH0KCiAgICBib29sIGRpcmVjdGVkID0gdHJ1ZTsKICAgIGlncmFwaF9lbXB0eShncmFwaCwgbnVtX3ZlcnRpY2VzLCBkaXJlY3RlZCk7CiAgICBpZ3JhcGhfYWRkX2VkZ2VzKGdyYXBoLCAmZWRnZXMsIE5VTEwpOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmZWRnZXMpOwoKICAgIGludCBtYXhfdmFyaWFudCA9IC0xOwogICAgZm9yKGVkZ2VfYXR0cmlidXRlcyBhOiBhdHRyaWJ1dGVzX3ZlY3Rvcil7CiAgICAgICAgaWdyYXBoX2NhdHRyaWJ1dGVfRUFOX3NldChncmFwaCwgImxhYmVsIiwgYS5lZGdlX2lkeCwgYS5sYWJlbCk7CiAgICAgICAgaWdyYXBoX2NhdHRyaWJ1dGVfRUFOX3NldChncmFwaCwgInZhcmlhbnQiLCBhLmVkZ2VfaWR4LCBhLnZhcmlhbnQpOwogICAgICAgIGlmKGEudmFyaWFudCA+IG1heF92YXJpYW50KXsKICAgICAgICAgICAgbWF4X3ZhcmlhbnQgPSBhLnZhcmlhbnQ7CiAgICAgICAgfQogICAgfQogICAgKm51bV92YXJpYW50cyA9IG1heF92YXJpYW50ICsgMTsKCn0KCgp2b2lkIHdyaXRlX2FsaWdubWVudF9ncmFwaF90b19maWxlKGlncmFwaF90ICpncmFwaCwgc3RyaW5nIGZpbGVfbmFtZSl7CiAgICAKICAgIHN0cmluZyBvdXRwdXQgPSB0b19zdHJpbmcoaWdyYXBoX2Vjb3VudChncmFwaCkpICsgIlxuIjsKCiAgICBpZ3JhcGhfZXNfdCBlczsKICAgIGlncmFwaF9laXRfdCBlaXQ7CgogICAgaWdyYXBoX2VzX2FsbCgmZXMsIElHUkFQSF9FREdFT1JERVJfSUQpOwogICAgaWdyYXBoX2VpdF9jcmVhdGUoZ3JhcGgsIGVzLCAmZWl0KTsKCiAgICBpbnQgc291cmNlLCBzaW5rOwoKICAgIHdoaWxlICghSUdSQVBIX0VJVF9FTkQoZWl0KSkgewogICAgICAgIGlncmFwaF9pbnRlZ2VyX3Qgc3RhcnQsIGVuZDsKICAgICAgICBpZ3JhcGhfZWRnZShncmFwaCwgSUdSQVBIX0VJVF9HRVQoZWl0KSwgJnN0YXJ0LCAmZW5kKTsKICAgICAgICBpbnQgd2VpZ2h0ID0gaWdyYXBoX2NhdHRyaWJ1dGVfRUFOKGdyYXBoLCAid2VpZ2h0IiwgSUdSQVBIX0VJVF9HRVQoZWl0KSk7CiAgICAgICAgaW50IHZhcmlhbnQgPSBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oZ3JhcGgsICJ2YXJpYW50IiwgSUdSQVBIX0VJVF9HRVQoZWl0KSk7CiAgICAgICAgaW50IGluaXRzb2wgPSBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oZ3JhcGgsICJpbml0c29sIiwgSUdSQVBIX0VJVF9HRVQoZWl0KSk7CiAgICAgICAgb3V0cHV0ICs9IHRvX3N0cmluZyhzdGFydCkgKyAiICIgKyB0b19zdHJpbmcoZW5kKSArICIgIiArIHRvX3N0cmluZyh3ZWlnaHQpICsgIiAiICsgdG9fc3RyaW5nKHZhcmlhbnQpICsgIiAiICsgdG9fc3RyaW5nKGluaXRzb2wpICsgIlxuIjsKCiAgICAgICAgaWYoaWdyYXBoX2NhdHRyaWJ1dGVfVkFOKGdyYXBoLCAic3RhcnRlbmQiLCBzdGFydCkgPT0gMSl7CiAgICAgICAgICAgIHNvdXJjZSA9IHN0YXJ0OwogICAgICAgIH0KICAgICAgICBpZihpZ3JhcGhfY2F0dHJpYnV0ZV9WQU4oZ3JhcGgsICJzdGFydGVuZCIsIGVuZCkgPT0gMil7CiAgICAgICAgICAgIHNpbmsgPSBlbmQ7CiAgICAgICAgfQoKICAgICAgICBJR1JBUEhfRUlUX05FWFQoZWl0KTsKICAgIH0KCiAgICBpZ3JhcGhfZXNfZGVzdHJveSgmZXMpOwogICAgaWdyYXBoX2VpdF9kZXN0cm95KCZlaXQpOwoKICAgIG91dHB1dCArPSB0b19zdHJpbmcoc291cmNlKSArICIgIiArIHRvX3N0cmluZyhzaW5rKTsKCiAgICBvZnN0cmVhbSBvdXRfZmlsZShmaWxlX25hbWUpOwogICAgb3V0X2ZpbGUgPDwgb3V0cHV0OwogICAgb3V0X2ZpbGUuY2xvc2UoKTsKCiAgICAKfQoKCnZvaWQgcmVhZF9hbGlnbm1lbnRfZ3JhcGhfZnJvbV9maWxlKGlncmFwaF90ICpncmFwaCwgc3RyaW5nIGZpbGVfbmFtZSl7CiAgICAKICAgIGlmc3RyZWFtIGluX2ZpbGUoZmlsZV9uYW1lKTsKCiAgICBpbnQgRTsKICAgIGluX2ZpbGUgPj4gRTsKCiAgICBpZihFID09IDApewogICAgICAgIGJvb2wgZGlyZWN0ZWQgPSB0cnVlOwogICAgICAgIGlncmFwaF9lbXB0eShncmFwaCwgMCwgZGlyZWN0ZWQpOwogICAgICAgIHJldHVybjsKICAgIH0KCiAgICBpZ3JhcGhfdmVjdG9yX2ludF90IGVkZ2VzOwogICAgaWdyYXBoX3ZlY3Rvcl90IHdlaWdodHM7CiAgICBpZ3JhcGhfdmVjdG9yX3QgdmFyaWFudHM7CiAgICBpZ3JhcGhfdmVjdG9yX3QgaW5pdHNvbHM7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmZWRnZXMsIDIqRSk7CiAgICBpZ3JhcGhfdmVjdG9yX2luaXQoJndlaWdodHMsIEUpOwogICAgaWdyYXBoX3ZlY3Rvcl9pbml0KCZ2YXJpYW50cywgRSk7CiAgICBpZ3JhcGhfdmVjdG9yX2luaXQoJmluaXRzb2xzLCBFKTsKCiAgICBpbnQgbnVtX3ZlcnRpY2VzID0gMDsKICAgIGludCBzdGFydCwgZW5kOyAKICAgIGZsb2F0IHdlaWdodCwgdmFyaWFudCwgaW5pdHNvbDsKCiAgICBpbnQgaSA9IDA7CiAgICBpbnQgaiA9IDA7CiAgICB3aGlsZSAoaW5fZmlsZSA+PiBzdGFydCA+PiBlbmQgPj4gd2VpZ2h0ID4+IHZhcmlhbnQgPj4gaW5pdHNvbCl7CiAgICAgICAgLy9jb3V0IDw8IHN0YXJ0IDw8ICIgIiA8PCBlbmQgPDwgIiAiIDw8IHdlaWdodCA8PCAiICIgPDwgdmFyaWFudCA8PCBlbmRsOwogICAgICAgCiAgICAgICAgLy9lZGdlc1tpXSA9IHN0YXJ0OwogICAgICAgIGlncmFwaF92ZWN0b3JfaW50X3NldCgmZWRnZXMsIGksIHN0YXJ0KTsKICAgICAgICAKICAgICAgICAvL2VkZ2VzW2krMV0gPSBlbmQ7CiAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfc2V0KCZlZGdlcywgaSsxLCBlbmQpOwogICAgICAgIAogICAgICAgIGkgKz0gMjsKCiAgICAgICAgLy93ZWlnaHRzW2pdID0gd2VpZ2h0OwogICAgICAgIGlncmFwaF92ZWN0b3Jfc2V0KCZ3ZWlnaHRzLCBqLCB3ZWlnaHQpOwoKICAgICAgICAvL3ZhcmlhbnRzW2pdID0gdmFyaWFudDsKICAgICAgICBpZ3JhcGhfdmVjdG9yX3NldCgmdmFyaWFudHMsIGosIHZhcmlhbnQpOwoKICAgICAgICBpZ3JhcGhfdmVjdG9yX3NldCgmaW5pdHNvbHMsIGosIGluaXRzb2wpOwoKICAgICAgICBqKys7CgogICAgICAgIGlmKHN0YXJ0ID4gbnVtX3ZlcnRpY2VzLTEpewogICAgICAgICAgICBudW1fdmVydGljZXMgPSBzdGFydCArIDE7CiAgICAgICAgfQogICAgICAgIGlmKGVuZCA+IG51bV92ZXJ0aWNlcy0xKXsKICAgICAgICAgICAgbnVtX3ZlcnRpY2VzPSBlbmQgKyAxOwogICAgICAgIH0KICAgIH0KCiAgICBpbl9maWxlLmNsb3NlKCk7CgogICAgYm9vbCBkaXJlY3RlZCA9IHRydWU7CiAgICBpZ3JhcGhfZW1wdHkoZ3JhcGgsIG51bV92ZXJ0aWNlcywgZGlyZWN0ZWQpOwogICAgaWdyYXBoX2FkZF9lZGdlcyhncmFwaCwgJmVkZ2VzLCBOVUxMKTsKCiAgICBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU5fc2V0dihncmFwaCwgIndlaWdodCIsICZ3ZWlnaHRzKTsKICAgIGlncmFwaF9jYXR0cmlidXRlX0VBTl9zZXR2KGdyYXBoLCAidmFyaWFudCIsICZ2YXJpYW50cyk7CiAgICBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU5fc2V0dihncmFwaCwgImluaXRzb2wiLCAmaW5pdHNvbHMpOwogICAgaWdyYXBoX2NhdHRyaWJ1dGVfVkFOX3NldChncmFwaCwgInN0YXJ0ZW5kIiwgc3RhcnQsIDEpOwogICAgaWdyYXBoX2NhdHRyaWJ1dGVfVkFOX3NldChncmFwaCwgInN0YXJ0ZW5kIiwgZW5kLCAyKTsKCiAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZlZGdlcyk7CiAgICBpZ3JhcGhfdmVjdG9yX2Rlc3Ryb3koJndlaWdodHMpOwogICAgaWdyYXBoX3ZlY3Rvcl9kZXN0cm95KCZ2YXJpYW50cyk7CiAgICBpZ3JhcGhfdmVjdG9yX2Rlc3Ryb3koJmluaXRzb2xzKTsKCn0KCgp2b2lkIHJlYWRfcG9zX3N1YnN0cmluZ19maWxlKHN0cmluZyBwb3Nfc3RyaW5nX2ZpbGVfbmFtZSwgdmVjdG9yPGludD4mIHBvc2l0aW9ucywgdmVjdG9yPHN0cmluZz4mIHN1YnN0cmluZ3MpewogICAgaWZzdHJlYW0gaW5maWxlKHBvc19zdHJpbmdfZmlsZV9uYW1lKTsKICAgIHN0cmluZyBsaW5lOwoKICAgIHdoaWxlIChzdGQ6OmdldGxpbmUoaW5maWxlLCBsaW5lKSl7CgogICAgICAgIGludCBwb3M7CiAgICAgICAgc3RyaW5nIHN1YnN0cmluZzsKICAgICAgICAKICAgICAgICBpc3RyaW5nc3RyZWFtIGlzcyhsaW5lKTsgLy8gc2VwYXJhdGVzIGxpbmUgb3ZlciBzcGFjZXMKICAgICAgICBpc3MgPj4gcG9zOwoKICAgICAgIGlmIChsaW5lLnNpemUoKSA+IDApewogICAgICAgICAgICB3aGlsZSAoaXNzID4+IHN1YnN0cmluZyl7CiAgICAgICAgICAgICAgICBwb3NpdGlvbnMucHVzaF9iYWNrKHBvcyk7CiAgICAgICAgICAgICAgICBzdWJzdHJpbmdzLnB1c2hfYmFjayhzdWJzdHJpbmcpOyAKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKCnZvaWQgZ2V0X3JlYWNoYWJsZV92ZXJ0ZXgoaWdyYXBoX3QqIGdyYXBoLCBpZ3JhcGhfdnNfdCB2ZXJ0ZXhfc2VsZWN0b3IsIGludCBkaXN0LCBpZ3JhcGhfdmVjdG9yX2ludF9saXN0X3QqIHJlYWNoYWJsZV9saXN0KXsKICAgIAogICAgaWdyYXBoX2ludGVnZXJfdCBvcmRlciA9IGRpc3Q7CiAgICBpZ3JhcGhfaW50ZWdlcl90IG1pbmRpc3QgPSAwOwoKICAgIGlncmFwaF9uZWlnaGJvcmhvb2QoZ3JhcGgsIHJlYWNoYWJsZV9saXN0LCB2ZXJ0ZXhfc2VsZWN0b3IsIG9yZGVyLCBJR1JBUEhfT1VULCBtaW5kaXN0KTsKfQoKCi8vIG9idGFpbnMgaW5kdWNlZCBncmFwaCBpbiB0aW1lIHBvbHlsb2dhcml0aG1pYyBpbiB0aGUgc2l6ZSBvZiB0aGUgaW5kdWNlZCBncmFwaAovLyB0aGlzIGlzIHdyaXR0ZW4gYmVjYXVzZSB0aGUgbmF0aXZlIGlncmFwaCBsaWJyYXJ5IHJlcXVpcmVzIHNpemUgcHJvcG9ydGlvbmFsIHRvIHRoZSBzaXplIG9mIG9yaWdpbmFsIGdyYXBoCnZvaWQgZ2V0X2luZHVjZWRfdmFyaWF0aW9uX2dyYXBoKGlncmFwaF90KiBncmFwaCwgaWdyYXBoX3ZlY3Rvcl9pbnRfdCogdmVydGV4X3NldCwgaWdyYXBoX3QqIHJlc3VsdCl7CiAgICB1bm9yZGVyZWRfbWFwPGludCwgaW50PiB1bWFwOwogICAgaW50IG4gPSBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKHZlcnRleF9zZXQpOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgLy8gdW5vcmRlcmVkIG1hcCByZWNvcmRzIHRoZSBleGlzdGVuY2Ugb2YgYSB2ZXJ0ZXggYW5kIGdpdmVzIGl0IGEgbmV3IGluZGV4CiAgICAgICAgdW1hcFtpZ3JhcGhfdmVjdG9yX2ludF9nZXQodmVydGV4X3NldCwgaSldID0gaTsKICAgIH0KCiAgICAvLyB0ZW1wb3J5IHZlY3RvciB0byBpbmNpZGVudCBlZGdlcyBmb3IgZWFjaCB2ZXJ0ZXgKICAgIGlncmFwaF92ZWN0b3JfaW50X3QgaW5jaWRlbnRfZWRnZXM7CiAgICBpZ3JhcGhfdmVjdG9yX2ludF9pbml0KCZpbmNpZGVudF9lZGdlcywgMCk7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBpbmR1Y2VkX2VkZ2VzOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmaW5kdWNlZF9lZGdlcywgMCk7CgogICAgdmVjdG9yPGVkZ2VfYXR0cmlidXRlcz4gYXR0cmlidXRlc192ZWN0b3I7CgogICAgaW50IG5ld19laWQgPSAwOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgaWdyYXBoX2luY2lkZW50KGdyYXBoLCAmaW5jaWRlbnRfZWRnZXMsIGlncmFwaF92ZWN0b3JfaW50X2dldCh2ZXJ0ZXhfc2V0LCBpKSwgSUdSQVBIX09VVCk7CiAgICAgICAgCiAgICAgICAgLy9jb3V0IDw8IGlncmFwaF92ZWN0b3JfaW50X2dldCh2ZXJ0ZXhfc2V0LCBpKSA8PCAifjogIjsKICAgICAgICAKICAgICAgICBpbnQgbV92ID0gaWdyYXBoX3ZlY3Rvcl9pbnRfc2l6ZSgmaW5jaWRlbnRfZWRnZXMpOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbV92OyBqKyspewogICAgICAgICAgICBpZ3JhcGhfaW50ZWdlcl90IHN0YXJ0LCBlbmQ7CiAgICAgICAgICAgIGludCBvbGRfZWlkID0gaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZpbmNpZGVudF9lZGdlcywgaik7CiAgICAgICAgICAgIGlncmFwaF9lZGdlKGdyYXBoLCBvbGRfZWlkLCAmc3RhcnQsICZlbmQpOwogICAgICAgICAgICAKICAgICAgICAgICAgLy9jb3V0IDw8ICIoIiA8PCBzdGFydCA8PCAiLCAiIDw8IGVuZCA8PCAiKSAiOwogICAgICAgICAgICAKICAgICAgICAgICAgLy8gY2hlY2sgaWYgZW5kIGlzIGluIHRoZSB2ZXJ0ZXhfc2V0CiAgICAgICAgICAgIGlmKHVtYXAuZmluZChlbmQpICE9IHVtYXAuZW5kKCkpewogICAgICAgICAgICAgICAgLy9hZGQgZWRnZQogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZpbmR1Y2VkX2VkZ2VzLCB1bWFwW3N0YXJ0XSk7CiAgICAgICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9wdXNoX2JhY2soJmluZHVjZWRfZWRnZXMsIHVtYXBbZW5kXSk7CiAgICAgICAgICAgICAgICBhdHRyaWJ1dGVzX3ZlY3Rvci5wdXNoX2JhY2soe25ld19laWQsIAogICAgICAgICAgICAgICAgICAgIGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgImxhYmVsIiwgb2xkX2VpZCksIAogICAgICAgICAgICAgICAgICAgIGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgInZhcmlhbnQiLCBvbGRfZWlkKX0pOwogICAgICAgICAgICAgICAgbmV3X2VpZCsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIC8vY291dCA8PCBlbmRsOwogICAgfQogICAgYm9vbCBkaXJlY3RlZCA9IHRydWU7CiAgICBpZ3JhcGhfZW1wdHkocmVzdWx0LCBuLCBkaXJlY3RlZCk7CiAgICBpZ3JhcGhfYWRkX2VkZ2VzKHJlc3VsdCwgJmluZHVjZWRfZWRnZXMsIE5VTEwpOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmaW5kdWNlZF9lZGdlcyk7CiAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZpbmNpZGVudF9lZGdlcyk7CgogICAgZm9yKGVkZ2VfYXR0cmlidXRlcyBhOiBhdHRyaWJ1dGVzX3ZlY3Rvcil7CiAgICAgICAgaWdyYXBoX2NhdHRyaWJ1dGVfRUFOX3NldChyZXN1bHQsICJsYWJlbCIsIGEuZWRnZV9pZHgsIGEubGFiZWwpOwogICAgICAgIGlncmFwaF9jYXR0cmlidXRlX0VBTl9zZXQocmVzdWx0LCAidmFyaWFudCIsIGEuZWRnZV9pZHgsIGEudmFyaWFudCk7CiAgICB9CgogICAgLy9wcmludF92YXJpYXRpb25fZ3JhcGgocmVzdWx0KTsKfQoKCnZvaWQgcmV2ZXJzZV93ZWlnaHRlZF9yZWFjaGFibGUoaWdyYXBoX3QqIGdyYXBoLCBpZ3JhcGhfaW50ZWdlcl90IHN0YXJ0X3ZpZCwgaWdyYXBoX3ZlY3Rvcl9pbnRfdCogcmVzdWx0LCBpbnQgZGVsdGEpewogICAgCiAgICAvLyB0b3BvbG9naWNhbGx5IHNvcnQgdGhlIHZlcnRpY2VzIG9mIHRoZSByZXZlcnNlZCBncmFwaAogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBzb3J0ZWRfdmVydGV4OwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmc29ydGVkX3ZlcnRleCwgaWdyYXBoX3Zjb3VudChncmFwaCkpOwogICAgaWdyYXBoX3RvcG9sb2dpY2FsX3NvcnRpbmcoZ3JhcGgsICZzb3J0ZWRfdmVydGV4LCBJR1JBUEhfSU4pOwogICAgaW50IG4gPSBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKCZzb3J0ZWRfdmVydGV4KTsKCiAgICAvL2NvdXQgPDwgInNpemUgPSAiIDw8IG4gPDwgZW5kbDsKCiAgICAvLyBnZXQgc3RhcnQgaW5kZXgKICAgIGludCBzdGFydF9pZHggPSAtMTsKCiAgICAvL2NvdXQgPDwgInJldmVyc2UgdG9wIG9yZGVyOiAiOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgLy9jb3V0IDw8IGkgPDwgIjoiIDw8IGlncmFwaF92ZWN0b3JfaW50X2dldCgmc29ydGVkX3ZlcnRleCwgaSkgPDwgIiwgIjsKICAgICAgICBpZihzdGFydF92aWQgPT0gaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZzb3J0ZWRfdmVydGV4LCBpKSl7CiAgICAgICAgICAgIHN0YXJ0X2lkeCA9IGk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KICAgIC8vY291dCA8PCBlbmRsOwoKICAgIHZlY3RvcjxpbnQ+IGRpc3RhbmNlKG4sIElOVF9NQVgtMSk7CiAgICAvL2NvdXQgPDwgImluZGV4IG9mIHN0YXJ0OiAiIDw8IGlncmFwaF92ZWN0b3JfaW50X2dldCgmc29ydGVkX3ZlcnRleCwgc3RhcnRfaWR4KSA8PCBlbmRsOwogICAgZGlzdGFuY2VbaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZzb3J0ZWRfdmVydGV4LCBzdGFydF9pZHgpXSA9IDA7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBpbmNpZGVudF9lZGdlczsKICAgIGlncmFwaF92ZWN0b3JfaW50X2luaXQoJmluY2lkZW50X2VkZ2VzLCAwKTsKCiAgICBmb3IoaW50IGkgPSBzdGFydF9pZHg7IGkgPCBuOyBpKyspewogICAgICAgIGlncmFwaF9pbnRlZ2VyX3QgdmlkID0gaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZzb3J0ZWRfdmVydGV4LCBpKTsKICAgICAgICAvLyB1cGRhdGUgbmVpZ2h0Ym9ycwogICAgICAgIGlncmFwaF9pbmNpZGVudChncmFwaCwgJmluY2lkZW50X2VkZ2VzLCB2aWQsIElHUkFQSF9JTik7CiAgICAgICAgaW50IG0gPSBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKCZpbmNpZGVudF9lZGdlcyk7CiAgICAgICAgLy9jb3V0IDw8ICJ2aWQgPSAiIDw8IHZpZCAgPDwgZW5kbDsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKCiAgICAgICAgICAgIGlncmFwaF9pbnRlZ2VyX3Qgc3RhcnQsIGVuZDsKICAgICAgICAgICAgaWdyYXBoX2VkZ2UoZ3JhcGgsIGlncmFwaF92ZWN0b3JfaW50X2dldCgmaW5jaWRlbnRfZWRnZXMsIGkpLCAmc3RhcnQsICZlbmQpOwogICAgICAgICAgICBpbnQgd2VpZ2h0ID0gaWdyYXBoX2NhdHRyaWJ1dGVfRUFOKGdyYXBoLCAid2VpZ2h0IiwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZpbmNpZGVudF9lZGdlcywgaSkpOwogICAgICAgICAgICAvL2NvdXQgPDwgInN0YXJ0ID0gIiA8PCBzdGFydCA8PCAiIGVuZCA9ICIgPDwgZW5kIDw8ICIgd2VpZ2h0ID0gIiA8PCB3ZWlnaHQgPDwgZW5kbDsKCiAgICAgICAgICAgIGlmKGRpc3RhbmNlW3N0YXJ0XSA+IGRpc3RhbmNlW2VuZF0gKyB3ZWlnaHQpewogICAgICAgICAgICAgICAgZGlzdGFuY2Vbc3RhcnRdID0gZGlzdGFuY2VbZW5kXSArIHdlaWdodDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZpbmNpZGVudF9lZGdlcyk7CiAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZzb3J0ZWRfdmVydGV4KTsKCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKICAgICAgICAvL2NvdXQgPDwgaSA8PCAiOiIgPDwgZGlzdGFuY2VbaV0gPDwgIiwgIjsKICAgICAgICBpZihkaXN0YW5jZVtpXSA8PSBkZWx0YSl7CiAgICAgICAgICAgIGlncmFwaF92ZWN0b3JfaW50X3B1c2hfYmFjayhyZXN1bHQsIGkpOwogICAgICAgIH0KICAgIH0KCn0KCgovKgpUaGUgbWFpbiBpZGVhIGlzIHRoYXQgd2UgY29uc2lkZXIgdGhlIHZlcnRpY2VzIG9mIHRoZSBhbGlnbm1lbnQgZ3JhcGggYXMgbGFpZGVkIG91dCBpbiB8UHx8VnwgZ3JpZC4KRWFjaCByb3cgb2YgbGVuZ3RoIHxWfCBpcyBzb3J0ZWQgaW4gdGhlIHNhbWUgdG9wb2xvZ2ljYWwgb3JkZXIuCldlIGhhc2ggeCx5IGNvb3JkaW5hdGVzIHRvIHRyYWNrIGlmIGEgdmVydGV4IGFzIGFscmVhZHkgYmVlbiBlbmNvdW50ZXJlZCBhbmQgc3RvcmUgYXMgdmFsdWUgdGhlIG1pbiBkaXN0CnJlc3VsdCBncmFwaCBzaG91bGQgbm90IGJlIGluaXRpYWxpemVkCiovCnZvaWQgY3JlYXRlX3BydW5lZF9hbGlnbm1lbnRfZ3JhcGgoaWdyYXBoX3QqIGdyYXBoLCBzdHJpbmcgcGF0dGVybiwgaW50IGRlbHRhLCBpZ3JhcGhfdCogcmVzdWx0KXsKCiAgICAvLyB0b3BvbG9naWNhbGx5IHNvcnQgdGhlIHZlcnRpY2VzLCB0aGlzIHdpbGwgYmUgdXNlZCB0byBnZXQgdGhlIGRlbHRhX3ggZm9yIGV2ZXJ5IGVkZ2UgY29uc2lkZXJlZAogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBzb3J0ZWRfdmVydGV4OwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmc29ydGVkX3ZlcnRleCwgaWdyYXBoX3Zjb3VudChncmFwaCkpOwogICAgaWdyYXBoX3RvcG9sb2dpY2FsX3NvcnRpbmcoZ3JhcGgsICZzb3J0ZWRfdmVydGV4LCBJR1JBUEhfT1VUKTsKICAgIGludCBuID0gaWdyYXBoX3ZlY3Rvcl9pbnRfc2l6ZSgmc29ydGVkX3ZlcnRleCk7CiAgICB2ZWN0b3I8aW50PiBpbnZfc29ydGVkX3ZlcnRleChuKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewogICAgICAgIGludl9zb3J0ZWRfdmVydGV4W2lncmFwaF92ZWN0b3JfaW50X2dldCgmc29ydGVkX3ZlcnRleCwgaSldID0gaTsKICAgIH0KCiAgICAvKgogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgY291dCA8PCBpZ3JhcGhfdmVjdG9yX2ludF9nZXQoJnNvcnRlZF92ZXJ0ZXgsIGkpIDw8ICIsICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGw7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKICAgICAgICBjb3V0IDw8IGludl9zb3J0ZWRfdmVydGV4W2ldIDw8ICIsICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGw7CiAgICAqLwoKICAgIHR5cGVkZWYgc3RydWN0IHZlcnRleF9zdHJ1Y3R7CiAgICAgICAgaW50IGlkOwogICAgICAgIGludCB4OwogICAgICAgIGludCB5OwogICAgICAgIGludCBkaXN0OwogICAgfXZlcnRleDsKCiAgICAvLyAgaGFzaCB0byB0cmFjayBzZWVuIGNvb3JkaW5hdGVzLCBkaXN0YW5jZXMgYXJlIHN0b3JlZCBoZXJlLCBub3QgaW4gcXVldWUKICAgIHVub3JkZXJlZF9tYXA8aW50LCB2ZXJ0ZXg+IHNlZW5fY29vcmRpbmF0ZXM7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBhbGlnbm1lbnRfZ3JhcGhfZWRnZXM7IC8vIHN0YXJ0LCBlbmQsICAgc3RhcnQsIGVuZCwgCiAgICB2ZWN0b3IgPGludD4gd2VpZ2h0czsgCiAgICB2ZWN0b3IgPGludD4gdmFyaWFudHM7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmYWxpZ25tZW50X2dyYXBoX2VkZ2VzLCAwKTsKCiAgICBpbnQgc291cmNlX3ZlcnRleF9pZCA9IDA7CiAgICBpbnQgc2lua192ZXJ0ZXhfaWQgPSAwOwoKICAgIHF1ZXVlPHZlcnRleD4gcTsKICAgIHZlcnRleCB1ID0gezAsIGludl9zb3J0ZWRfdmVydGV4WzBdLCAwLCAwfTsKICAgIHEucHVzaCh1KTsKCiAgICBpbnQgbmV3X3ZpZCA9IDE7CiAgICBpZ3JhcGhfdmVjdG9yX2ludF90IGluY2lkZW50X2VkZ2VzOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmaW5jaWRlbnRfZWRnZXMsIDApOwoKICAgIHdoaWxlKCFxLmVtcHR5KCkpewoKICAgICAgICB2ZXJ0ZXggdSA9IHEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGlncmFwaF9pbnRlZ2VyX3Qgb2xkX3VpZCA9IGlncmFwaF92ZWN0b3JfaW50X2dldCgmc29ydGVkX3ZlcnRleCwgdS54KTsKICAgICAgICAKCiAgICAgICAgaW50IHVfY29vcmQgPSB1LnkgKiBuICsgdS54OwogICAgICAgIHZlcnRleCB1XyA9IHNlZW5fY29vcmRpbmF0ZXNbdV9jb29yZF07CiAgICAgICAgaW50IHVfZGlzdCA9IHVfLmRpc3Q7CgogICAgICAgIC8vY291dCA8PCB1LnggPDwgIiwgIiA8PCB1LnkgPDwgIjogIiA8PCB1X2Rpc3QgPDwgZW5kbDsKCiAgICAgICAgLy8gdmVydGljZXMgb24gc2FtZSBsZXZlbCAoaW5zZXJ0aW9uKQogICAgICAgIGlmKHVfZGlzdCArIDEgPD0gZGVsdGEpewoKICAgICAgICAgICAgaWdyYXBoX2luY2lkZW50KGdyYXBoLCAmaW5jaWRlbnRfZWRnZXMsIG9sZF91aWQsIElHUkFQSF9PVVQpOwogICAgICAgICAgICBpbnQgbSA9IGlncmFwaF92ZWN0b3JfaW50X3NpemUoJmluY2lkZW50X2VkZ2VzKTsKICAgICAgICAgICAgLy9jb3V0IDw8ICJtID0gIiA8PCBtIDw8IGVuZGw7CiAgICAgICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBtOyBpKyspewoKICAgICAgICAgICAgICAgIGlncmFwaF9pbnRlZ2VyX3Qgc3RhcnQsIGVuZDsKICAgICAgICAgICAgICAgIGlncmFwaF9lZGdlKGdyYXBoLCBpZ3JhcGhfdmVjdG9yX2ludF9nZXQoJmluY2lkZW50X2VkZ2VzLCBpKSwgJnN0YXJ0LCAmZW5kKTsKCiAgICAgICAgICAgICAgICBpbnQgdl94ID0gaW52X3NvcnRlZF92ZXJ0ZXhbZW5kXTsKICAgICAgICAgICAgICAgIGludCB2X3kgPSB1Lnk7CiAgICAgICAgICAgICAgICBpbnQgdl9jb29yZGluYXRlID0gdl95ICogbiArIHZfeDsKICAgICAgICAgICAgICAgIGludCB2aWQ7CgogICAgICAgICAgICAgICAgaWYoc2Vlbl9jb29yZGluYXRlcy5maW5kKHZfY29vcmRpbmF0ZSkgPT0gc2Vlbl9jb29yZGluYXRlcy5lbmQoKSl7CiAgICAgICAgICAgICAgICAgICAgLy8gbmV2ZXIgZW5jb3VudGVyIGNvb3JkaW5hdGUKICAgICAgICAgICAgICAgICAgICAvLyBhZGQgdmVydGV4IHdpdGggbmV3IHZlcnRleCBpZCBhbmQgZWRnZQoKICAgICAgICAgICAgICAgICAgICB2aWQgPSBuZXdfdmlkOwogICAgICAgICAgICAgICAgICAgIHNlZW5fY29vcmRpbmF0ZXNbdl9jb29yZGluYXRlXSA9IHt2aWQsIHZfeCwgdl95LCB1X2Rpc3QgKyAxfTsKICAgICAgICAgICAgICAgICAgICBuZXdfdmlkKys7CiAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgLy8gZW5xdWUgdmVydGV4CiAgICAgICAgICAgICAgICAgICAgcS5wdXNoKHt2aWQsIHZfeCwgdl95LCAtMX0pOwoKICAgICAgICAgICAgICAgIH1lbHNlewogICAgICAgICAgICAgICAgICAgIC8vIGNvb3JkaW5hdGUgc2VlbiBiZWZvcmUgCiAgICAgICAgICAgICAgICAgICAgdmVydGV4IHYgPSBzZWVuX2Nvb3JkaW5hdGVzW3ZfY29vcmRpbmF0ZV07CiAgICAgICAgICAgICAgICAgICAgdmlkID0gdi5pZDsKCiAgICAgICAgICAgICAgICAgICAgLy8gdXBkYXRlIGRpc3RhbmNlIGlmIG5lZWRlZAogICAgICAgICAgICAgICAgICAgIGlmKHVfZGlzdCArIDEgPCB2LmRpc3QpewogICAgICAgICAgICAgICAgICAgICAgICBzZWVuX2Nvb3JkaW5hdGVzW3ZfY29vcmRpbmF0ZV0gPSB7dmlkLCB2X3gsIHZfeSwgdV9kaXN0ICsgMX07CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZhbGlnbm1lbnRfZ3JhcGhfZWRnZXMsIHUuaWQpOwogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZhbGlnbm1lbnRfZ3JhcGhfZWRnZXMsIHZpZCk7CiAgICAgICAgICAgICAgICB3ZWlnaHRzLnB1c2hfYmFjaygxKTsKICAgICAgICAgICAgICAgIHZhcmlhbnRzLnB1c2hfYmFjayhpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oZ3JhcGgsICJ2YXJpYW50IiwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZpbmNpZGVudF9lZGdlcywgaSkpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gZGVsZXRpb24gZWRnZXMKICAgICAgICBpZih1LnkgPCBwYXR0ZXJuLmxlbmd0aCgpICYmIHVfZGlzdCArIDEgPD0gZGVsdGEpewogICAgICAgICAgICBpbnQgdl94ID0gdS54OwogICAgICAgICAgICBpbnQgdl95ID0gdS55ICsgMTsKICAgICAgICAgICAgaW50IHZfY29vcmRpbmF0ZSA9IHZfeSAqIG4gKyB2X3g7CgogICAgICAgICAgICBpbnQgdmlkOwogICAgICAgICAgICAvLyBuZXZlciBzZWVuIGJlZm9yZQogICAgICAgICAgICBpZihzZWVuX2Nvb3JkaW5hdGVzLmZpbmQodl9jb29yZGluYXRlKSA9PSBzZWVuX2Nvb3JkaW5hdGVzLmVuZCgpKXsKCiAgICAgICAgICAgICAgICB2aWQgPSBuZXdfdmlkOwogICAgICAgICAgICAgICAgc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdID0ge3ZpZCwgdl94LCB2X3ksIHVfZGlzdCArIDF9OwogICAgICAgICAgICAgICAgbmV3X3ZpZCsrOwoKICAgICAgICAgICAgICAgIC8vIGVucXVlIHZlcnRleAogICAgICAgICAgICAgICAgcS5wdXNoKHt2aWQsIHZfeCwgdl95LCAtMX0pOwoKICAgICAgICAgICAgfWVsc2V7CiAgICAgICAgICAgICAgICAvLyBjb29yZGluYXRlIHNlZW4gYmVmb3JlIAogICAgICAgICAgICAgICAgdmVydGV4IHYgPSBzZWVuX2Nvb3JkaW5hdGVzW3ZfY29vcmRpbmF0ZV07CiAgICAgICAgICAgICAgICB2aWQgPSB2LmlkOwogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAvLyB1cGRhdGUgZGlzdGFuY2UgaWYgbmVlZGVkCiAgICAgICAgICAgICAgICBpZih1X2Rpc3QgKyAxIDwgdi5kaXN0KXsKICAgICAgICAgICAgICAgICAgICBzZWVuX2Nvb3JkaW5hdGVzW3ZfY29vcmRpbmF0ZV0gPSB7dmlkLCB2X3gsIHZfeSwgdV9kaXN0ICsgMX07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZhbGlnbm1lbnRfZ3JhcGhfZWRnZXMsIHUuaWQpOwogICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9wdXNoX2JhY2soJmFsaWdubWVudF9ncmFwaF9lZGdlcywgdmlkKTsKICAgICAgICAgICAgd2VpZ2h0cy5wdXNoX2JhY2soMSk7CiAgICAgICAgICAgIHZhcmlhbnRzLnB1c2hfYmFjaygtMik7CiAgICAgICAgfQoKICAgICAgICAvLyBzdWIvbWF0Y2ggZWRnZXMKCiAgICAgICAgaWYodS55IDwgcGF0dGVybi5sZW5ndGgoKSl7CiAgICAgICAgICAgIGlncmFwaF9pbmNpZGVudChncmFwaCwgJmluY2lkZW50X2VkZ2VzLCBvbGRfdWlkLCBJR1JBUEhfT1VUKTsKICAgICAgICAgICAgaW50IG0gPSBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKCZpbmNpZGVudF9lZGdlcyk7CgogICAgICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKCiAgICAgICAgICAgICAgICAvLyBjaGVjayBpZiBzeW1ib2wgbWF0Y2hlcwogICAgICAgICAgICAgICAgaW50IHN5bSA9IChpbnQpIGlncmFwaF9jYXR0cmlidXRlX0VBTihncmFwaCwgImxhYmVsIiwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZpbmNpZGVudF9lZGdlcywgaSkpOwoKICAgICAgICAgICAgICAgIC8vY291dCA8PCAiKCIgPDwgdS54IDw8ICIsICIgPDwgdS55IDw8ICIpIHN5bTogIiA8PCBzeW0gPDwgZW5kbDsKICAgICAgICAgICAgICAgIGlmKCAgICAocGF0dGVyblt1LnldID09ICdBJyAmJiBzeW0gPT0gMCkgCiAgICAgICAgICAgICAgICAgICAgfHwgKHBhdHRlcm5bdS55XSA9PSAnVCcgJiYgc3ltID09IDEpCiAgICAgICAgICAgICAgICAgICAgfHwgKHBhdHRlcm5bdS55XSA9PSAnQycgJiYgc3ltID09IDIpCiAgICAgICAgICAgICAgICAgICAgfHwgKHBhdHRlcm5bdS55XSA9PSAnRycgJiYgc3ltID09IDMpCiAgICAgICAgICAgICAgICAgICAgfHwgKHBhdHRlcm5bdS55XSA9PSAnTicgfHwgc3ltID09IDQpCiAgICAgICAgICAgICAgICAgICAgKXsKCiAgICAgICAgICAgICAgICAgICAgaWdyYXBoX2ludGVnZXJfdCBzdGFydCwgZW5kOwogICAgICAgICAgICAgICAgICAgIGlncmFwaF9lZGdlKGdyYXBoLCBpZ3JhcGhfdmVjdG9yX2ludF9nZXQoJmluY2lkZW50X2VkZ2VzLCBpKSwgJnN0YXJ0LCAmZW5kKTsKCiAgICAgICAgICAgICAgICAgICAgaW50IHZfeCA9IGludl9zb3J0ZWRfdmVydGV4W2VuZF07CiAgICAgICAgICAgICAgICAgICAgaW50IHZfeSA9IHUueSArIDE7CiAgICAgICAgICAgICAgICAgICAgaW50IHZfY29vcmRpbmF0ZSA9IHZfeSAqIG4gKyB2X3g7CiAgICAgICAgICAgICAgICAgICAgaW50IHZpZDsKCiAgICAgICAgICAgICAgICAgICAgaWYoc2Vlbl9jb29yZGluYXRlcy5maW5kKHZfY29vcmRpbmF0ZSkgPT0gc2Vlbl9jb29yZGluYXRlcy5lbmQoKSl7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIG5ldmVyIGVuY291bnRlciBjb29yZGluYXRlCiAgICAgICAgICAgICAgICAgICAgICAgIC8vIGFkZCB2ZXJ0ZXggd2l0aCBuZXcgdmVydGV4IGlkIGFuZCBlZGdlCgogICAgICAgICAgICAgICAgICAgICAgICAvLyBBZGRzIDAgdG8gdGhlIGRpc3RhbmNlIGZyb20gdQogICAgICAgICAgICAgICAgICAgICAgICB2aWQgPSBuZXdfdmlkOwogICAgICAgICAgICAgICAgICAgICAgICBzZWVuX2Nvb3JkaW5hdGVzW3ZfY29vcmRpbmF0ZV0gPSB7dmlkLCB2X3gsIHZfeSwgdV9kaXN0fTsKICAgICAgICAgICAgICAgICAgICAgICAgbmV3X3ZpZCsrOwogICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgLy8gZW5xdWUgdmVydGV4CiAgICAgICAgICAgICAgICAgICAgICAgIHEucHVzaCh7dmlkLCB2X3gsIHZfeSwgLTF9KTsKCiAgICAgICAgICAgICAgICAgICAgfWVsc2V7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIGNvb3JkaW5hdGUgc2VlbiBiZWZvcmUgCiAgICAgICAgICAgICAgICAgICAgICAgIHZlcnRleCB2ID0gc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdOwogICAgICAgICAgICAgICAgICAgICAgICB2aWQgPSB2LmlkOwoKICAgICAgICAgICAgICAgICAgICAgICAgLy8gdXBkYXRlIGRpc3RhbmNlIGlmIG5lZWRlZAogICAgICAgICAgICAgICAgICAgICAgICBpZih1X2Rpc3QgPCB2LmRpc3QpewogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdID0ge3ZpZCwgdl94LCB2X3ksIHVfZGlzdH07CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZhbGlnbm1lbnRfZ3JhcGhfZWRnZXMsIHUuaWQpOwogICAgICAgICAgICAgICAgICAgIGlncmFwaF92ZWN0b3JfaW50X3B1c2hfYmFjaygmYWxpZ25tZW50X2dyYXBoX2VkZ2VzLCB2aWQpOwogICAgICAgICAgICAgICAgICAgIHdlaWdodHMucHVzaF9iYWNrKDApOwogICAgICAgICAgICAgICAgICAgIHZhcmlhbnRzLnB1c2hfYmFjayhpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oZ3JhcGgsICJ2YXJpYW50IiwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZpbmNpZGVudF9lZGdlcywgaSkpKTsKCiAgICAgICAgICAgICAgICB9ZWxzZSBpZiAodV9kaXN0ICsgMSA8PSBkZWx0YSl7CgogICAgICAgICAgICAgICAgICAgIGlncmFwaF9pbnRlZ2VyX3Qgc3RhcnQsIGVuZDsKICAgICAgICAgICAgICAgICAgICBpZ3JhcGhfZWRnZShncmFwaCwgaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZpbmNpZGVudF9lZGdlcywgaSksICZzdGFydCwgJmVuZCk7CgogICAgICAgICAgICAgICAgICAgIGludCB2X3ggPSBpbnZfc29ydGVkX3ZlcnRleFtlbmRdOwogICAgICAgICAgICAgICAgICAgIGludCB2X3kgPSB1LnkgKyAxOwogICAgICAgICAgICAgICAgICAgIGludCB2X2Nvb3JkaW5hdGUgPSB2X3kgKiBuICsgdl94OwogICAgICAgICAgICAgICAgICAgIGludCB2aWQ7CgogICAgICAgICAgICAgICAgICAgIGlmKHNlZW5fY29vcmRpbmF0ZXMuZmluZCh2X2Nvb3JkaW5hdGUpID09IHNlZW5fY29vcmRpbmF0ZXMuZW5kKCkpewogICAgICAgICAgICAgICAgICAgICAgICAvLyBuZXZlciBlbmNvdW50ZXIgY29vcmRpbmF0ZQogICAgICAgICAgICAgICAgICAgICAgICAvLyBhZGQgdmVydGV4IHdpdGggbmV3IHZlcnRleCBpZCBhbmQgZWRnZQoKICAgICAgICAgICAgICAgICAgICAgICAgLy8gQWRkcyAxIHRvIHRoZSBkaXN0YW5jZSBmcm9tIHUKICAgICAgICAgICAgICAgICAgICAgICAgdmlkID0gbmV3X3ZpZDsKICAgICAgICAgICAgICAgICAgICAgICAgc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdID0ge3ZpZCwgdl94LCB2X3ksIHVfZGlzdCArIDF9OwogICAgICAgICAgICAgICAgICAgICAgICBuZXdfdmlkKys7CiAgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICAvLyBlbnF1ZSB2ZXJ0ZXgKICAgICAgICAgICAgICAgICAgICAgICAgcS5wdXNoKHt2aWQsIHZfeCwgdl95LCAtMX0pOwoKICAgICAgICAgICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgICAgICAgICAgLy8gY29vcmRpbmF0ZSBzZWVuIGJlZm9yZSAKICAgICAgICAgICAgICAgICAgICAgICAgdmVydGV4IHYgPSBzZWVuX2Nvb3JkaW5hdGVzW3ZfY29vcmRpbmF0ZV07CiAgICAgICAgICAgICAgICAgICAgICAgIHZpZCA9IHYuaWQ7CgogICAgICAgICAgICAgICAgICAgICAgICAvLyB1cGRhdGUgZGlzdGFuY2UgaWYgbmVlZGVkCiAgICAgICAgICAgICAgICAgICAgICAgIGlmKHVfZGlzdCArIDEgPCB2LmRpc3QpewogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdID0ge3ZpZCwgdl94LCB2X3ksIHVfZGlzdCArIDF9OwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGlncmFwaF92ZWN0b3JfaW50X3B1c2hfYmFjaygmYWxpZ25tZW50X2dyYXBoX2VkZ2VzLCB1LmlkKTsKICAgICAgICAgICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9wdXNoX2JhY2soJmFsaWdubWVudF9ncmFwaF9lZGdlcywgdmlkKTsKICAgICAgICAgICAgICAgICAgICB3ZWlnaHRzLnB1c2hfYmFjaygxKTsKICAgICAgICAgICAgICAgICAgICB2YXJpYW50cy5wdXNoX2JhY2soaWdyYXBoX2NhdHRyaWJ1dGVfRUFOKGdyYXBoLCAidmFyaWFudCIsIGlncmFwaF92ZWN0b3JfaW50X2dldCgmaW5jaWRlbnRfZWRnZXMsIGkpKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgoKICAgICAgICAvLyBlZGdlcyB0byBzaW5rIHZlcnRleAoKICAgICAgICBpZih1LnkgPT0gcGF0dGVybi5sZW5ndGgoKSl7CgogICAgICAgICAgICBpbnQgdl95ID0gdS55KzE7CiAgICAgICAgICAgIGludCB2X2Nvb3JkaW5hdGUgPSBuICogdl95OwoKICAgICAgICAgICAgaW50IHZpZDsKICAgICAgICAKICAgICAgICAgICAgaWYoc2Vlbl9jb29yZGluYXRlcy5maW5kKHZfY29vcmRpbmF0ZSkgPT0gc2Vlbl9jb29yZGluYXRlcy5lbmQoKSl7CiAgICAgICAgICAgICAgICB2aWQgPSBuZXdfdmlkOwogICAgICAgICAgICAgICAgc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdID0ge3ZpZCwgMCwgdl95LCB1X2Rpc3R9OwogICAgICAgICAgICAgICAgc2lua192ZXJ0ZXhfaWQgPSB2aWQ7CiAgICAgICAgICAgICAgICBuZXdfdmlkKys7CgogICAgICAgICAgICAgICAgLy9xLnB1c2goe3ZpZCwgMCwgbioocGF0dGVybi5sZW5ndGgoKSsxKSwgLTF9KTsKCiAgICAgICAgICAgIH1lbHNlewogICAgICAgICAgICAgICAgLy8gY29vcmRpbmF0ZSBzZWVuIGJlZm9yZSAKICAgICAgICAgICAgICAgIHZlcnRleCB2ID0gc2Vlbl9jb29yZGluYXRlc1t2X2Nvb3JkaW5hdGVdOwogICAgICAgICAgICAgICAgdmlkID0gdi5pZDsKCiAgICAgICAgICAgICAgICAvLyB1cGRhdGUgZGlzdGFuY2UgaWYgbmVlZGVkCiAgICAgICAgICAgICAgICBpZih1X2Rpc3QgPCB2LmRpc3QpewogICAgICAgICAgICAgICAgICAgIHNlZW5fY29vcmRpbmF0ZXNbdl9jb29yZGluYXRlXSA9IHt2aWQsIDAsIHZfeSwgdV9kaXN0fTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZhbGlnbm1lbnRfZ3JhcGhfZWRnZXMsIHUuaWQpOwogICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9wdXNoX2JhY2soJmFsaWdubWVudF9ncmFwaF9lZGdlcywgdmlkKTsKICAgICAgICAgICAgd2VpZ2h0cy5wdXNoX2JhY2soMCk7CiAgICAgICAgICAgIHZhcmlhbnRzLnB1c2hfYmFjaygtMyk7CgogICAgICAgIH0KICAgIH0KICAgIC8vIGNvbnN0cnVjdCB0ZW1wb3JhcnkgZm9yd2FyZC1wcnVuZWQgb25seSBhbGlnbm1lbnQgZ3JhcGgKICAgIGJvb2wgZGlyZWN0ZWQgPSB0cnVlOwogICAgaWdyYXBoX3QgZm9yd2FyZF9wcnVuZWRfb25seV9ncmFwaDsKICAgIGlncmFwaF9lbXB0eSgmZm9yd2FyZF9wcnVuZWRfb25seV9ncmFwaCwgbmV3X3ZpZCwgZGlyZWN0ZWQpOwogICAgaWdyYXBoX2FkZF9lZGdlcygmZm9yd2FyZF9wcnVuZWRfb25seV9ncmFwaCwgJmFsaWdubWVudF9ncmFwaF9lZGdlcywgTlVMTCk7CgogICAgZm9yKGludCBpID0gMDsgaSA8IHdlaWdodHMuc2l6ZSgpOyBpKyspewogICAgICAgIGlncmFwaF9jYXR0cmlidXRlX0VBTl9zZXQoJmZvcndhcmRfcHJ1bmVkX29ubHlfZ3JhcGgsICJ3ZWlnaHQiLCBpLCB3ZWlnaHRzLmF0KGkpKTsKICAgICAgICBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU5fc2V0KCZmb3J3YXJkX3BydW5lZF9vbmx5X2dyYXBoLCAidmFyaWFudCIsIGksIHZhcmlhbnRzLmF0KGkpKTsKICAgIH0KCiAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZhbGlnbm1lbnRfZ3JhcGhfZWRnZXMpOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmc29ydGVkX3ZlcnRleCk7CgogICAgaWdyYXBoX3ZlY3Rvcl90IHplcm9zOwogICAgaWdyYXBoX3ZlY3Rvcl9pbml0KCZ6ZXJvcywgaWdyYXBoX3Zjb3VudCgmZm9yd2FyZF9wcnVuZWRfb25seV9ncmFwaCkpOwogICAgaWdyYXBoX2NhdHRyaWJ1dGVfVkFOX3NldHYoJmZvcndhcmRfcHJ1bmVkX29ubHlfZ3JhcGgsICJzdGFydGVuZCIsICZ6ZXJvcyk7CiAgICBpZ3JhcGhfY2F0dHJpYnV0ZV9WQU5fc2V0KCZmb3J3YXJkX3BydW5lZF9vbmx5X2dyYXBoLCAic3RhcnRlbmQiLCBzb3VyY2VfdmVydGV4X2lkLCAxKTsKICAgIGlncmFwaF9jYXR0cmlidXRlX1ZBTl9zZXQoJmZvcndhcmRfcHJ1bmVkX29ubHlfZ3JhcGgsICJzdGFydGVuZCIsIHNpbmtfdmVydGV4X2lkLCAyKTsKCgogICAgLy9jb3V0IDw8ICI9PT09PT09PT09PT09IEZvcndhcmQgUHJ1bm5lZCBBbGlnbm1lbnQgR3JhcGggQ29uc3RydWN0ZWQgPT09PT09PT09PT09PSIgPDwgZW5kbDsKICAgIC8vcHJpbnRfYWxpZ25tZW50X2dyYXBoKCZmb3J3YXJkX3BydW5lZF9vbmx5X2dyYXBoKTsKICAgIC8vY291dCA8PCAiRm9yd2FyZCBwcnVuZWQgYWxpZ25tZW50IGdyYXBoIHNpemU6ICIgPDwgaWdyYXBoX3Zjb3VudCgmZm9yd2FyZF9wcnVuZWRfb25seV9ncmFwaCkgPDwgZW5kbDsKICAgIC8vIHJldmVyc2UgcHJ1bmluZwoKICAgIC8vIGdldCB2ZXJ0aWNlcyByZWFjaGFibGUgZnJvbSB0aGUgbGFzdCB2ZXJ0ZXggd2l0aCBkaXN0YW5jZSBhdCBtb3N0IGRlbHRhCiAgICBpZ3JhcGhfdmVjdG9yX2ludF90IHJldmVyc2VfcmVhY2hhYmxlX3ZlcnRleDsKICAgIGlncmFwaF92ZWN0b3JfaW50X2luaXQoJnJldmVyc2VfcmVhY2hhYmxlX3ZlcnRleCwgMCk7CgogICAgcmV2ZXJzZV93ZWlnaHRlZF9yZWFjaGFibGUoJmZvcndhcmRfcHJ1bmVkX29ubHlfZ3JhcGgsIHNpbmtfdmVydGV4X2lkLCAmcmV2ZXJzZV9yZWFjaGFibGVfdmVydGV4LCBkZWx0YSk7CgogICAgaWdyYXBoX3ZzX3QgdnM7CiAgICBpZ3JhcGhfdnNfdmVjdG9yKCZ2cywgJnJldmVyc2VfcmVhY2hhYmxlX3ZlcnRleCk7CgogICAgaWdyYXBoX2luZHVjZWRfc3ViZ3JhcGgoJmZvcndhcmRfcHJ1bmVkX29ubHlfZ3JhcGgsIHJlc3VsdCwgdnMsIElHUkFQSF9TVUJHUkFQSF9BVVRPKTsKICAgIGlncmFwaF9kZXN0cm95KCZmb3J3YXJkX3BydW5lZF9vbmx5X2dyYXBoKTsKICAgIGlncmFwaF92ZWN0b3JfaW50X2Rlc3Ryb3koJnJldmVyc2VfcmVhY2hhYmxlX3ZlcnRleCk7Cgp9IAoKCnZvaWQgYWRkX2luaXRpYWxfc29sdXRpb24oaWdyYXBoX3QqIGFsaWdubWVudF9ncmFwaCl7CgogICAgLy8gZ2V0IHNvdXJjZSBhbmQgc2luawogICAgaW50IHN0YXJ0X3ZlcnRleCA9IDA7CiAgICBpbnQgZW5kX3ZlcnRleCA9IDA7CiAgICBpZ3JhcGhfdnNfdCB2czsKICAgIGlncmFwaF92aXRfdCB2aXQ7CiAgICBpZ3JhcGhfdnNfYWxsKCZ2cyk7CiAgICBpZ3JhcGhfdml0X2NyZWF0ZShhbGlnbm1lbnRfZ3JhcGgsIHZzLCAmdml0KTsKICAgIHdoaWxlICghSUdSQVBIX1ZJVF9FTkQodml0KSkgewogICAgICAgIGludCB2aWQgPSBJR1JBUEhfVklUX0dFVCh2aXQpOwogICAgICAgIGludCBzdGFydGVuZCA9IChpbnQpaWdyYXBoX2NhdHRyaWJ1dGVfVkFOKGFsaWdubWVudF9ncmFwaCwgInN0YXJ0ZW5kIiwgdmlkKTsKICAgICAgICBpZihzdGFydGVuZCA9PSAxKXsKICAgICAgICAgICAgc3RhcnRfdmVydGV4ID0gdmlkOwogICAgICAgIH1lbHNlIGlmIChzdGFydGVuZCA9PSAyKXsKICAgICAgICAgICAgZW5kX3ZlcnRleCA9IHZpZDsKICAgICAgICB9CiAgICAgICAgSUdSQVBIX1ZJVF9ORVhUKHZpdCk7CiAgICB9CiAgICBpZ3JhcGhfdnNfZGVzdHJveSgmdnMpOwogICAgaWdyYXBoX3ZpdF9kZXN0cm95KCZ2aXQpOwoKCiAgICAvLyBnZXQgZWRnZSB3ZWlnaHRzCiAgICBpZ3JhcGhfZXNfdCBlczsKICAgIGlncmFwaF9lc19hbGwoJmVzLCBJR1JBUEhfRURHRU9SREVSX0lEKTsKICAgIGlncmFwaF92ZWN0b3JfdCB3ZWlnaHRzOwogICAgaWdyYXBoX3ZlY3Rvcl9pbml0KCZ3ZWlnaHRzLCAwKTsKICAgIGlncmFwaF9jYXR0cmlidXRlX0VBTlYoYWxpZ25tZW50X2dyYXBoLCAid2VpZ2h0IiwgZXMsICZ3ZWlnaHRzKTsKICAgIGlncmFwaF9lc19kZXN0cm95KCZlcyk7CgogICAgLy8gZ2V0IHBhdGggd2l0aCBtaW5pbXVtIHdlaWdodAogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBwYXRoX2VkZ2VzOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmcGF0aF9lZGdlcywgMCk7CiAgICAKICAgIC8vY291dCA8PCAibnVtIHZlcnRleCBpbiBncmFwaDogIiA8PCBpZ3JhcGhfdmNvdW50KGFsaWdubWVudF9ncmFwaCkgPDwgZW5kbDsKICAgIC8vY291dCA8PCAic3RhcnQ6IiA8PCBzdGFydF92ZXJ0ZXggPDwgIiBlbmQgdmVydGV4OiAiIDw8IGVuZF92ZXJ0ZXggPDwgZW5kbDsKCiAgICBpZ3JhcGhfZ2V0X3Nob3J0ZXN0X3BhdGhfZGlqa3N0cmEoYWxpZ25tZW50X2dyYXBoLCBOVUxMLCAmcGF0aF9lZGdlcywgc3RhcnRfdmVydGV4LCBlbmRfdmVydGV4LCAmd2VpZ2h0cywgSUdSQVBIX09VVCk7CiAgICBpZ3JhcGhfdmVjdG9yX2Rlc3Ryb3koJndlaWdodHMpOwoKICAgIC8vIHB1dCBpdCBpbiBhdHRyaWJ1dGUgdmVjdG9yCiAgICBpZ3JhcGhfdmVjdG9yX3QgYXR0cmlidXRlX3ZlY3RvcjsKICAgIGlncmFwaF92ZWN0b3JfaW5pdCgmYXR0cmlidXRlX3ZlY3RvciwgaWdyYXBoX2Vjb3VudChhbGlnbm1lbnRfZ3JhcGgpKTsKICAgIGludCBtID0gaWdyYXBoX3ZlY3Rvcl9pbnRfc2l6ZSgmcGF0aF9lZGdlcyk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKICAgICAgICBpbnQgZWlkID0gaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZwYXRoX2VkZ2VzLCBpKTsKICAgICAgICAvL2ludCB3ZWlnaHQgPSBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oYWxpZ25tZW50X2dyYXBoLCAid2VpZ2h0IiwgZWlkKTsKICAgICAgICAvL2NvdXQgPDwgImVkZ2UgaWQ6ICIgPDwgZWlkIDw8ICIgd2VpZ2h0OiAiIDw8IHdlaWdodCA8PCBlbmRsOwogICAgICAgIGlncmFwaF92ZWN0b3Jfc2V0KCZhdHRyaWJ1dGVfdmVjdG9yLCBlaWQsIDEpOwogICAgfQogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmcGF0aF9lZGdlcyk7CgogICAgLy8gc2V0IGVkZ2UgYXR0cmJpdHVlCiAgICBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU5fc2V0dihhbGlnbm1lbnRfZ3JhcGgsICJpbml0c29sIiwgJmF0dHJpYnV0ZV92ZWN0b3IpOwogICAgaWdyYXBoX3ZlY3Rvcl9kZXN0cm95KCZhdHRyaWJ1dGVfdmVjdG9yKTsKCn0KCnZvaWQgY3JlYXRlX2FsaWdubWVudF9ncmFwaChpZ3JhcGhfdCogdmFyaWF0aW9uX2dyYXBoLCBpbnQgcG9zLCBzdHJpbmcgcywgaW50IGFscGhhLCBpbnQgZGVsdGEsIGlncmFwaF90KiBhbGlnbm1lbnRfZ3JhcGgpewogICAgCiAgICBpZ3JhcGhfdnNfdCBzdGFydF92ZXJ0ZXhfc2VsZWN0b3I7CiAgICBpZ3JhcGhfdnNfMSgmc3RhcnRfdmVydGV4X3NlbGVjdG9yLCBwb3MpOwoKICAgIGlncmFwaF92ZWN0b3JfaW50X2xpc3RfdCByZWFjaGFibGVfdmVydGV4X2xpc3Q7CiAgICBpZ3JhcGhfdmVjdG9yX2ludF9saXN0X2luaXQoJnJlYWNoYWJsZV92ZXJ0ZXhfbGlzdCwgMCk7CiAgICAKICAgIGdldF9yZWFjaGFibGVfdmVydGV4KHZhcmlhdGlvbl9ncmFwaCwgc3RhcnRfdmVydGV4X3NlbGVjdG9yLCBhbHBoYSArIGRlbHRhLCAmcmVhY2hhYmxlX3ZlcnRleF9saXN0KTsKICAgIGlncmFwaF92c19kZXN0cm95KCZzdGFydF92ZXJ0ZXhfc2VsZWN0b3IpOwogICAgCiAgICAvLyBzaW5jZSB2ZXJ0ZXggc2VsZWN0b3IgaXMgb25seSBmb3Igb25lIHZlcnRleCwgd2Ugb25seSBuZWVkIHRoZSBmaXJzdCBlbGVtZW50CiAgICBpZ3JhcGhfdmVjdG9yX2ludF90KiByZWFjaGFibGVfdmVydGV4ID0gaWdyYXBoX3ZlY3Rvcl9pbnRfbGlzdF9nZXRfcHRyKCZyZWFjaGFibGVfdmVydGV4X2xpc3QsIDApOwogICAgCiAgICBpZ3JhcGhfdCByZWFjaGFibGVfZ3JhcGg7CiAgICBnZXRfaW5kdWNlZF92YXJpYXRpb25fZ3JhcGgodmFyaWF0aW9uX2dyYXBoLCByZWFjaGFibGVfdmVydGV4LCAmcmVhY2hhYmxlX2dyYXBoKTsKICAgIAoKICAgIC8vY291dCA8PCAiaW5kdWNlZCB2YXJpYXRpb24gZ3JhcGggc2l6ZTogIiA8PCBpZ3JhcGhfdmNvdW50KCZyZWFjaGFibGVfZ3JhcGgpIDw8IGVuZGw7CgogICAgaW50IHN0YXJ0X3ZlcnRleCwgZW5kX3ZlcnRleDsKICAgIGNyZWF0ZV9wcnVuZWRfYWxpZ25tZW50X2dyYXBoKCZyZWFjaGFibGVfZ3JhcGgsIHMsIGRlbHRhLCBhbGlnbm1lbnRfZ3JhcGgpOwoKICAgIC8vY291dCA8PCAicHJ1bmVkIGFsaWdubWVudCBncmFwaCBzaXplOiAiIDw8IGlncmFwaF92Y291bnQoYWxpZ25tZW50X2dyYXBoKSA8PCBlbmRsOwoKICAgIGFkZF9pbml0aWFsX3NvbHV0aW9uKGFsaWdubWVudF9ncmFwaCk7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfbGlzdF9kZXN0cm95KCZyZWFjaGFibGVfdmVydGV4X2xpc3QpOwogICAgaWdyYXBoX2Rlc3Ryb3koJnJlYWNoYWJsZV9ncmFwaCk7Cn0KCgp2b2lkIGdldF92YXJpYW50cyhpZ3JhcGhfdCogZywgdW5vcmRlcmVkX3NldDxpbnQ+JiB2YXJpYW50cyl7CgogICAgaWdyYXBoX2VzX3QgZXM7CiAgICBpZ3JhcGhfZXNfYWxsKCZlcywgSUdSQVBIX0VER0VPUkRFUl9JRCk7CiAgICBpZ3JhcGhfZWl0X3QgZWl0OwogICAgaWdyYXBoX2VpdF9jcmVhdGUoZywgZXMsICZlaXQpOwoKICAgIHdoaWxlICghSUdSQVBIX0VJVF9FTkQoZWl0KSkgewogICAgICAgIGludCB2YXJpYW50ID0gaWdyYXBoX2NhdHRyaWJ1dGVfRUFOKGcsICJ2YXJpYW50IiAsSUdSQVBIX0VJVF9HRVQoZWl0KSk7CiAgICAgICAgaWYodmFyaWFudCA+PSAwKXsKICAgICAgICAgICAgdmFyaWFudHMuaW5zZXJ0KHZhcmlhbnQpOwogICAgICAgIH0KCiAgICAgICAgSUdSQVBIX0VJVF9ORVhUKGVpdCk7CiAgICB9CiAgICBpZ3JhcGhfZXNfZGVzdHJveSgmZXMpOwogICAgaWdyYXBoX2VpdF9kZXN0cm95KCZlaXQpOwp9CgoKLy8gcmV0dXJucyBhIHZlY3RvciB0aGF0IGFzc2lnbnMgZWFjaCBhbGlnbm1lbnQgZ3JhcGggdG8gYSBzZXQgdXNpbmcgYW4gaW50ZWdlcgovLyBhbHNvIHByaW50cyB0aGUgbnVtYmVyIG9mIHNldHMgYW5kIHNpemUgb2YgZWFjaCBjb3JyZXNwb25kaW5nIElMUAp2b2lkIGFuYWx5emVfYWxpZ25tZW50X2dyYXBoX3NldChpbnQgbnVtX3ZhcmlhbnRzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pio+JiBhbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVjdG9yPGludD4mIGdsb2JhbF92YXJpYWJsZV90b19jb21wb25lbnQsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVjdG9yPGludD4mIHN1YklMUF90b19jb21wb25lbnQsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVjdG9yPGludD4mIGdsb2JhbF92YXJpYWJsZV90b19sb2NhbF9pZHgsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVjdG9yPGludD4mIGNvbXBvbmVudF90b19nbG9iYWxfdmFyaWFibGVfY291bnQsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiYgY29tcG9uZW50X3RvX3N1YklMUHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50KiBudW1fY29tcG9uZW50cwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICl7CiAgICAKCiAgICBpZ3JhcGhfdmVjdG9yX2ludF90IGVkZ2VzOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmZWRnZXMsIDApOwoKICAgIGludCBpbHBfaWR4ID0gbnVtX3ZhcmlhbnRzOwoKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBhbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHMuc2l6ZSgpOyBpKyspewogICAgICAgIC8vcHJpbnRfYWxpZ25tZW50X2dyYXBoKCZnKTsKCiAgICAgICAgLy8gb2J0YWluIHNldCBvZiB2YXJpYW50cwogICAgICAgIC8vdW5vcmRlcmVkX3NldDxpbnQ+IHZhcmlhbnRzOwogICAgICAgIC8vZ2V0X3ZhcmlhbnRzKCZnLCB2YXJpYW50cyk7CgogICAgICAgIC8vIGFkZCBlZGdlcyBmb3IgYmlwYXJ0aXRlIGdyYXBoCiAgICAgICAgLy9jb3V0IDw8IGkgPDwgIjogIjsKICAgICAgICBmb3IoaW50IHY6ICphbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHNbaV0pewogICAgICAgICAgICAvL2NvdXQgPDwgdiA8PCAiLCAiOwogICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF9wdXNoX2JhY2soJmVkZ2VzLCBpbHBfaWR4KTsKICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfcHVzaF9iYWNrKCZlZGdlcywgdik7CiAgICAgICAgfQogICAgICAgIC8vY291dCA8PCBlbmRsOwogICAgICAgIGlscF9pZHgrKzsKCiAgICB9CiAgICBpbnQgbiA9IG51bV92YXJpYW50cyArIGFsaWdubWVudF9ncmFwaF90b192YXJpYW50cy5zaXplKCk7CgogICAgYm9vbCBkaXJlY3RlZCA9IGZhbHNlOwogICAgaWdyYXBoX3QgYmlwYXJ0aXRlOwogICAgaWdyYXBoX2VtcHR5KCZiaXBhcnRpdGUsIG4sIGRpcmVjdGVkKTsKICAgIGlncmFwaF9hZGRfZWRnZXMoJmJpcGFydGl0ZSwgJmVkZ2VzLCBOVUxMKTsKCiAgICBpZ3JhcGhfdmVjdG9yX2ludF9kZXN0cm95KCZlZGdlcyk7CgogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBtZW1iZXJzaGlwOwogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmbWVtYmVyc2hpcCwgbik7CiAgICBpZ3JhcGhfY29ubmVjdGVkX2NvbXBvbmVudHMoJmJpcGFydGl0ZSwgJm1lbWJlcnNoaXAsIE5VTEwsIE5VTEwsIElHUkFQSF9TVFJPTkcpOwoKCiAgICBnbG9iYWxfdmFyaWFibGVfdG9fY29tcG9uZW50ID0gdmVjdG9yPGludD4obnVtX3ZhcmlhbnRzKTsKICAgIHN1YklMUF90b19jb21wb25lbnQgPSB2ZWN0b3I8aW50PihhbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHMuc2l6ZSgpKTsKICAgIGdsb2JhbF92YXJpYWJsZV90b19sb2NhbF9pZHggPSB2ZWN0b3I8aW50PihudW1fdmFyaWFudHMpOwoKICAgIHVub3JkZXJlZF9tYXA8aW50LCBpbnQ+IHNpemVzOwoKICAgICpudW1fY29tcG9uZW50cyA9IDA7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKCiAgICAgICAgaW50IGNvbXBvbmVudCA9IGlncmFwaF92ZWN0b3JfaW50X2dldCgmbWVtYmVyc2hpcCwgaSk7CiAgICAgICAgaWYoY29tcG9uZW50ICsgMSA+ICpudW1fY29tcG9uZW50cyl7CiAgICAgICAgICAgICpudW1fY29tcG9uZW50cyA9IGNvbXBvbmVudCArIDE7CiAgICAgICAgfQoKICAgICAgICBpZihpIDwgbnVtX3ZhcmlhbnRzKXsKICAgICAgICAgICAgCiAgICAgICAgICAgIGdsb2JhbF92YXJpYWJsZV90b19jb21wb25lbnRbaV0gPSBjb21wb25lbnQ7CgogICAgICAgICAgICBpZihzaXplcy5maW5kKGNvbXBvbmVudCkgPT0gc2l6ZXMuZW5kKCkpewogICAgICAgICAgICAgICAgc2l6ZXNbY29tcG9uZW50XSA9IDE7CiAgICAgICAgICAgIH1lbHNlewogICAgICAgICAgICAgICAgc2l6ZXNbY29tcG9uZW50XSA9IHNpemVzW2NvbXBvbmVudF0gKyAxOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGdsb2JhbF92YXJpYWJsZV90b19sb2NhbF9pZHhbaV0gPSBzaXplc1tjb21wb25lbnRdIC0gMTsKICAgICAgICAgICAgCiAgICAgICAgfWVsc2V7CiAgICAgICAgICAgIHN1YklMUF90b19jb21wb25lbnRbaSAtIG51bV92YXJpYW50c10gPSBjb21wb25lbnQ7CiAgICAgICAgfQogICAgfQoKCiAgICBjb21wb25lbnRfdG9fZ2xvYmFsX3ZhcmlhYmxlX2NvdW50ID0gdmVjdG9yPGludD4oKm51bV9jb21wb25lbnRzLCAwKTsKICAgIGNvbXBvbmVudF90b19zdWJJTFBzID0gdmVjdG9yPHZlY3RvcjxpbnQ+PigqbnVtX2NvbXBvbmVudHMpOwogICAgZm9yIChhdXRvIHNpemUgOiBzaXplcyl7CiAgICAgICAgY29tcG9uZW50X3RvX2dsb2JhbF92YXJpYWJsZV9jb3VudFtzaXplLmZpcnN0XSA9IHNpemUuc2Vjb25kOwogICAgICAgIGNvbXBvbmVudF90b19zdWJJTFBzW3NpemUuZmlyc3RdID0gdmVjdG9yPGludD4oKTsKICAgIH0KCiAgICAvLyBjbGVhbiB1cAogICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmbWVtYmVyc2hpcCk7CgogICAgCiAgICAvLyBwcmludCBzdGF0ZW1lbnRzIGZvciBkZWJ1Z2dpbmcKICAgIGlmKFZFUkJPU0UpewogICAgICAgIGNvdXQgPDwgIkdsb2JhbCB2YXJpYWJsZSB0byBjb21wb25lbnQiIDw8IGVuZGw7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IGdsb2JhbF92YXJpYWJsZV90b19jb21wb25lbnQuc2l6ZSgpOyBpKyspewogICAgICAgICAgICBjb3V0IDw8ICJ4XyIgPDwgaSA8PCAiOiAiIDw8IGdsb2JhbF92YXJpYWJsZV90b19jb21wb25lbnRbaV0gPDwgIiwgbG9jYWw6IiA8PCBnbG9iYWxfdmFyaWFibGVfdG9fbG9jYWxfaWR4W2ldIDw8IGVuZGw7CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8ICJcblN1YklMUCB0byBjb21wb25lbnQiIDw8IGVuZGw7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IHN1YklMUF90b19jb21wb25lbnQuc2l6ZSgpOyBpKyspewogICAgICAgICAgICBjb3V0IDw8ICJJTFBfIiA8PCBpIDw8ICI6ICIgPDwgc3ViSUxQX3RvX2NvbXBvbmVudFtpXSA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KCiAgICAvKgogICAgY291dCA8PCAiXG5Db21wb25lbnQgdG8gZ2xvYmFsIHZhcmlhbnQgY291bnQ6XG4iIDw8IGVuZGw7CiAgICBjb3V0IDw8ICJbIjsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBjb21wb25lbnRfdG9fZ2xvYmFsX3ZhcmlhYmxlX2NvdW50LnNpemUoKTsgaSsrKXsKICAgICAgICAvL2NvdXQgPDwgImNvbXBvbmVudF8iIDw8IGkgPDwgIiBoYXMgdmFyaWFudHM6ICIgPDwgY29tcG9uZW50X3RvX2dsb2JhbF92YXJpYWJsZV9jb3VudFtpXSA8PCBlbmRsOwogICAgICAgIGNvdXQgPDwgY29tcG9uZW50X3RvX2dsb2JhbF92YXJpYWJsZV9jb3VudFtpXSA8PCAiLCAiOwogICAgfQogICAgY291dCA8PCAiXSIgPDwgZW5kbDsKICAgICovCgogICAgdW5vcmRlcmVkX21hcDxpbnQsIGludD4gY29tcG9uZW50X3RvX251bV9lZGdlczsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBhbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHMuc2l6ZSgpOyBpKyspewogICAgICAgIAogICAgICAgIC8vaWdyYXBoX3QgZyA9IGFsaWdubWVudF9ncmFwaHMuYXQoaSk7CiAgICAgICAgaW50IGNvbXBvbmVudCA9IHN1YklMUF90b19jb21wb25lbnRbaV07CiAgICAgICAgY29tcG9uZW50X3RvX3N1YklMUHNbY29tcG9uZW50XS5wdXNoX2JhY2soaSk7CiAgICAgICAgLyoKICAgICAgICBpZihjb21wb25lbnRfdG9fbnVtX2VkZ2VzLmZpbmQoY29tcG9uZW50KSA9PSBjb21wb25lbnRfdG9fbnVtX2VkZ2VzLmVuZCgpKXsKICAgICAgICAgICAgY29tcG9uZW50X3RvX251bV9lZGdlc1tjb21wb25lbnRdID0gaWdyYXBoX2Vjb3VudCgmZyk7CiAgICAgICAgfWVsc2V7CiAgICAgICAgICAgIGNvbXBvbmVudF90b19udW1fZWRnZXNbY29tcG9uZW50XSA9IGNvbXBvbmVudF90b19udW1fZWRnZXNbY29tcG9uZW50XSArIGlncmFwaF9lY291bnQoJmcpOwogICAgICAgIH0KICAgICAgICAqLwogICAgfQogICAgLyoKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBjb21wb25lbnRfdG9fZ2xvYmFsX3ZhcmlhYmxlX2NvdW50LnNpemUoKTsgaSsrKXsKICAgICAgICBjb3V0IDw8ICJjb21wb25lbnRfIiA8PCBpIDw8ICIgaGFzIHRvdGFsIHZhcmlhYmxlczogIiA8PCBjb21wb25lbnRfdG9fZ2xvYmFsX3ZhcmlhYmxlX2NvdW50W2ldICsgY29tcG9uZW50X3RvX251bV9lZGdlc1tpXSA8PCBlbmRsOwogICAgfQogICAgKi8KfQoKCnZvaWQgY29uc3RydWN0X0lMUHMoaW50IGNvbXBvbmVudCwKICAgICAgICAgICAgICAgICAgICB2ZWN0b3I8dmVjdG9yPGludD4+JiBjb21wb25lbnRfdG9fc3ViSUxQcywKICAgICAgICAgICAgICAgICAgICB2ZWN0b3I8aW50PiYgZ2xvYmFsX3ZhcmlhYmxlX3RvX2xvY2FsX2lkeCwKICAgICAgICAgICAgICAgICAgICB2ZWN0b3I8aW50PiYgY29tcG9uZW50X3RvX2dsb2JhbF92YXJpYWJsZV9jb3VudCwKICAgICAgICAgICAgICAgICAgICBHUkJNb2RlbCYgbW9kZWwsCiAgICAgICAgICAgICAgICAgICAgaW50IGRlbHRhLAogICAgICAgICAgICAgICAgICAgIHN0cmluZyBncmFwaF9kaXJlY3RvcnksCiAgICAgICAgICAgICAgICAgICAgdmVjdG9yPGlncmFwaF90Kj4mIGFsaWdubWVudF9ncmFwaHMsCiAgICAgICAgICAgICAgICAgICAgYm9vbCB1c2VfZmlsZXMKICAgICAgICAgICAgICAgICAgICApewoKCiAgICBHUkJWYXIqIGdsb2JhbF92YXIgPSBtb2RlbC5hZGRWYXJzKGNvbXBvbmVudF90b19nbG9iYWxfdmFyaWFibGVfY291bnRbY29tcG9uZW50XSk7CgogICAgR1JCTGluRXhwciBvYmogPSBHUkJMaW5FeHByKCk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgY29tcG9uZW50X3RvX2dsb2JhbF92YXJpYWJsZV9jb3VudFtjb21wb25lbnRdOyBpKyspewogICAgICAgIG9iaiArPSBnbG9iYWxfdmFyW2ldOwoKICAgICAgICBnbG9iYWxfdmFyW2ldLnNldChHUkJfRG91YmxlQXR0cl9TdGFydCwgMCk7CiAgICB9CiAgICBtb2RlbC5zZXRPYmplY3RpdmUob2JqLCBHUkJfTUFYSU1JWkUpOwoKCiAgICBpZihQUklOVF9DT01QT05FTlRfU0laRVMpewogICAgICAgIGNvdXQgPDwgIlxuQ29tcG9uZW50ICI8PCBjb21wb25lbnQgPDwgIiBoYXMgc2l6ZSAobnVtYmVyIG9mIGFsaWdubWVudCBncmFwaHMpOiAiIDw8IGNvbXBvbmVudF90b19zdWJJTFBzW2NvbXBvbmVudF0uc2l6ZSgpIDw8IGVuZGw7CiAgICB9CgogICAgZm9yKGludCBpID0gMDsgaSA8IGNvbXBvbmVudF90b19zdWJJTFBzW2NvbXBvbmVudF0uc2l6ZSgpOyBpKyspewoKICAgICAgICBhdXRvIHN0YXJ0ID0gY2hyb25vOjpzdGVhZHlfY2xvY2s6Om5vdygpOwoKICAgICAgICBpbnQgYWxpZ25tZW50X2dyYXBoX2lkeCA9IGNvbXBvbmVudF90b19zdWJJTFBzW2NvbXBvbmVudF1baV07CgogICAgICAgIGlncmFwaF90IGFsaWdubWVudF9ncmFwaDsKCiAgICAgICAgaWYodXNlX2ZpbGVzID09IDEpewogICAgICAgICAgICBzdHJpbmcgZmlsZV9uYW1lID0gZ3JhcGhfZGlyZWN0b3J5ICsgImdfIiArIHRvX3N0cmluZyhhbGlnbm1lbnRfZ3JhcGhfaWR4KTsKICAgICAgICAgICAgLy9jb3V0IDw8IGZpbGVfbmFtZSA8PCBlbmRsOwogICAgICAgICAgICByZWFkX2FsaWdubWVudF9ncmFwaF9mcm9tX2ZpbGUoJmFsaWdubWVudF9ncmFwaCwgZmlsZV9uYW1lKTsKICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgYWxpZ25tZW50X2dyYXBoID0gKmFsaWdubWVudF9ncmFwaHNbYWxpZ25tZW50X2dyYXBoX2lkeF07CiAgICAgICAgfQoKICAgICAgICBpZihpZ3JhcGhfZWNvdW50KCZhbGlnbm1lbnRfZ3JhcGgpID09IDApewogICAgICAgICAgICBjb3V0IDw8ICJubyBlZGdlcyBpbiBhbGlnbm1lbnQgZ3JhcGguIiA8PCBlbmRsOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CgogICAgICAgIC8qCiAgICAgICAgaWYoVkVSQk9TRSl7CiAgICAgICAgICAgIGNvdXQgPDwgIkFsaWdubWVudF9ncmFwaF8iIDw8IGkgPDwgIiBJTFAgY29uc3RydWN0aW9uIGluIGNvbXBvbmVudCAobW9kZWwpOiAiIDw8IGNvbXBvbmVudCA8PCBlbmRsOwogICAgICAgIH1lbHNlIGlmKCFWRVJCT1NFICYmIGkgJSAxID09IDApewogICAgICAgICAgICBjb3V0IDw8ICJDb25zdHJ1Y3RpbmcgSUxQIGZvciBhbGlnbm1lbnRfZ3JhcGg6ICIgPDwgaSA8PCAiIG91dCBvZiAiIDw8IGNvbXBvbmVudF90b19zdWJJTFBzW2NvbXBvbmVudF0uc2l6ZSgpIDw8ICIgKGluY3JlbWVudHMgb2YgMSkiIDw8IGVuZGw7CiAgICAgICAgfQogICAgICAgICovCgogICAgICAgIEdSQlZhciogbG9jYWxfdmFyID0gbW9kZWwuYWRkVmFycyhpZ3JhcGhfZWNvdW50KCZhbGlnbm1lbnRfZ3JhcGgpLCBHUkJfQklOQVJZKTsKCiAgICAgICAgaWdyYXBoX3ZzX3QgdnM7CiAgICAgICAgaWdyYXBoX3ZpdF90IHZpdDsKICAgICAgICBpZ3JhcGhfYm9vbF90IGxvb3BzID0gdHJ1ZTsgICAgIC8vIHRoZXJlIGFyZSBubyBsb29wcywgdGhpcyBpcyB0byBnZXQgY29uc3QuIHF1ZXJ5IHRpbWUgZm9yIGRlZ3JlZXMKCiAgICAgICAgaWdyYXBoX3ZzX2FsbCgmdnMpOwogICAgICAgIGlncmFwaF92aXRfY3JlYXRlKCZhbGlnbm1lbnRfZ3JhcGgsIHZzLCAmdml0KTsKICAgICAgICAKICAgICAgICAKICAgICAgICB3aGlsZSAoIUlHUkFQSF9WSVRfRU5EKHZpdCkpIHsKICAgICAgICAgICAgCiAgICAgICAgICAgIGludCB2aWQgPSBJR1JBUEhfVklUX0dFVCh2aXQpOwogICAgICAgICAgICAKICAgICAgICAgICAgaWdyYXBoX2ludGVnZXJfdCBpbl9kZWdyZWUsIG91dF9kZWdyZWU7CiAgICAgICAgICAgIGlncmFwaF9kZWdyZWVfMSgmYWxpZ25tZW50X2dyYXBoLCAmaW5fZGVncmVlLCB2aWQsIElHUkFQSF9JTiwgbG9vcHMpOwogICAgICAgICAgICBpZ3JhcGhfZGVncmVlXzEoJmFsaWdubWVudF9ncmFwaCwgJm91dF9kZWdyZWUsIHZpZCwgSUdSQVBIX09VVCwgbG9vcHMpOwoKICAgICAgICAgICAgLyoKICAgICAgICAgICAgY291dCA8PCAiZ3JhcGg6ICIgPDwgaSA8PCAiIHZlcnRleDogIiA8PCB2aWQgCiAgICAgICAgICAgICAgICA8PCAiIGluLWRlZ3JlZTogIiA8PCBpbl9kZWdyZWUgCiAgICAgICAgICAgICAgICA8PCAiIG91dC1kZWdyZWU6ICIgPDwgb3V0X2RlZ3JlZQogICAgICAgICAgICAgICAgPDwgIiBzdGFydGVuZDogIiA8PCBpZ3JhcGhfY2F0dHJpYnV0ZV9WQU4oJmFsaWdubWVudF9ncmFwaHNbaV0sICJzdGFydGVuZCIsIHZpZCkgCiAgICAgICAgICAgICAgICA8PCBlbmRsOwogICAgICAgICAgICAqLwoKICAgICAgICAgICAgR1JCTGluRXhwciBsaHMsIHJoczsKICAgICAgICAgICAgaWYoaWdyYXBoX2NhdHRyaWJ1dGVfVkFOKCZhbGlnbm1lbnRfZ3JhcGgsICJzdGFydGVuZCIsIHZpZCkgPT0gMSl7CiAgICAgICAgICAgICAgICBsaHMgPSBHUkJMaW5FeHByKDEpOwogICAgICAgICAgICAgICAgcmhzID0gR1JCTGluRXhwcigpOwoKICAgICAgICAgICAgICAgIC8vIGl0ZXJhdGUgdGhyb3VnaCBvdXRib3VuZCBlZGdlcwogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfdCBlZGdlczsKICAgICAgICAgICAgICAgIGlncmFwaF92ZWN0b3JfaW50X2luaXQoJmVkZ2VzLCAwKTsKICAgICAgICAgICAgICAgIGlncmFwaF9pbmNpZGVudCgmYWxpZ25tZW50X2dyYXBoLCAmZWRnZXMsIHZpZCwgSUdSQVBIX09VVCk7CiAgICAgICAgICAgICAgICBpbnQgbSA9IGlncmFwaF92ZWN0b3JfaW50X3NpemUoJmVkZ2VzKTsKICAgICAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7IGogPCBtOyBqKyspewogICAgICAgICAgICAgICAgICAgIHJocyArPSBsb2NhbF92YXJbaWdyYXBoX3ZlY3Rvcl9pbnRfZ2V0KCZlZGdlcywgaildOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmZWRnZXMpOwoKICAgICAgICAgICAgfWVsc2UgaWYoaWdyYXBoX2NhdHRyaWJ1dGVfVkFOKCZhbGlnbm1lbnRfZ3JhcGgsICJzdGFydGVuZCIsIHZpZCkgPT0gMil7CiAgICAgICAgICAgICAgICBsaHMgPSBHUkJMaW5FeHByKCk7CiAgICAgICAgICAgICAgICByaHMgPSBHUkJMaW5FeHByKDEpOwoKICAgICAgICAgICAgICAgIC8vIGl0ZXJhdGUgdGhyb3VnaCBpbmJvdW5kIGVkZ2VzCiAgICAgICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF90IGVkZ2VzOwogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmZWRnZXMsIDApOwogICAgICAgICAgICAgICAgaWdyYXBoX2luY2lkZW50KCZhbGlnbm1lbnRfZ3JhcGgsICZlZGdlcywgdmlkLCBJR1JBUEhfSU4pOwogICAgICAgICAgICAgICAgaW50IG0gPSBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKCZlZGdlcyk7CiAgICAgICAgICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgbTsgaisrKXsKICAgICAgICAgICAgICAgICAgICBsaHMgKz0gbG9jYWxfdmFyW2lncmFwaF92ZWN0b3JfaW50X2dldCgmZWRnZXMsIGopXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlncmFwaF92ZWN0b3JfaW50X2Rlc3Ryb3koJmVkZ2VzKTsgICAgICAgICAgICAgICAgCgogICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgIGxocyA9IEdSQkxpbkV4cHIoKTsKICAgICAgICAgICAgICAgIHJocyA9IEdSQkxpbkV4cHIoKTsKCiAgICAgICAgICAgICAgICBpZ3JhcGhfdmVjdG9yX2ludF90IGVkZ2VzOwogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfaW5pdCgmZWRnZXMsIDApOwoKICAgICAgICAgICAgICAgIC8vIGl0ZXJhdGUgdGhyb3VnaCBpbiBib3VuZCBlZGdlcwogICAgICAgICAgICAgICAgaWdyYXBoX2luY2lkZW50KCZhbGlnbm1lbnRfZ3JhcGgsICZlZGdlcywgdmlkLCBJR1JBUEhfSU4pOwogICAgICAgICAgICAgICAgaW50IG0gPSBpZ3JhcGhfdmVjdG9yX2ludF9zaXplKCZlZGdlcyk7CiAgICAgICAgICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgbTsgaisrKXsKICAgICAgICAgICAgICAgICAgICBsaHMgKz0gbG9jYWxfdmFyW2lncmFwaF92ZWN0b3JfaW50X2dldCgmZWRnZXMsIGopXTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAvLyBpdGVyYXRlIHRocm91Z2ggb3V0Ym91bmQgZWRnZXMKICAgICAgICAgICAgICAgIGlncmFwaF9pbmNpZGVudCgmYWxpZ25tZW50X2dyYXBoLCAmZWRnZXMsIHZpZCwgSUdSQVBIX09VVCk7CiAgICAgICAgICAgICAgICBtID0gaWdyYXBoX3ZlY3Rvcl9pbnRfc2l6ZSgmZWRnZXMpOwogICAgICAgICAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IG07IGorKyl7CiAgICAgICAgICAgICAgICAgICAgcmhzICs9IGxvY2FsX3ZhcltpZ3JhcGhfdmVjdG9yX2ludF9nZXQoJmVkZ2VzLCBqKV07CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWdyYXBoX3ZlY3Rvcl9pbnRfZGVzdHJveSgmZWRnZXMpOyAgCgogICAgICAgICAgICB9CgogICAgICAgICAgICBtb2RlbC5hZGRDb25zdHIobGhzLCBHUkJfRVFVQUwsIHJocyk7CiAgICAgICAgICAgIElHUkFQSF9WSVRfTkVYVCh2aXQpOwogICAgICAgIH0KCiAgICAgICAgaWdyYXBoX3ZzX2Rlc3Ryb3koJnZzKTsKICAgICAgICBpZ3JhcGhfdml0X2Rlc3Ryb3koJnZpdCk7CgogICAgICAgIC8vIGFkZCBiaW5kaW5nIGNvbnN0cmFpbnRzIGFuZCBkZWx0YSBjb25zdHJhaW50CiAgICAgICAgaWdyYXBoX2VzX3QgZXM7CiAgICAgICAgaWdyYXBoX2VpdF90IGVpdDsKICAgICAgICBpZ3JhcGhfZXNfYWxsKCZlcywgSUdSQVBIX0VER0VPUkRFUl9JRCk7CiAgICAgICAgaWdyYXBoX2VpdF9jcmVhdGUoJmFsaWdubWVudF9ncmFwaCwgZXMsICZlaXQpOwoKICAgICAgICBHUkJMaW5FeHByIGRlbHRhX2NvbnN0cmFpbnRfcmhzID0gR1JCTGluRXhwcihkZWx0YSk7CiAgICAgICAgR1JCTGluRXhwciBkZWx0YV9jb25zdHJhaW50X2xocyA9IEdSQkxpbkV4cHIoKTsKCiAgICAgICAgd2hpbGUoIUlHUkFQSF9FSVRfRU5EKGVpdCkpewogICAgICAgICAgICBpbnQgZWlkID0gSUdSQVBIX0VJVF9HRVQoZWl0KTsKICAgICAgICAgICAgaW50IHZhcmlhbnQgPSBpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oJmFsaWdubWVudF9ncmFwaCwgInZhcmlhbnQiLCBlaWQpOwogICAgICAgICAgICBpZih2YXJpYW50ID49IDApewogICAgICAgICAgICAgICAgaW50IGlkeCA9IGdsb2JhbF92YXJpYWJsZV90b19sb2NhbF9pZHhbdmFyaWFudF07CgogICAgICAgICAgICAgICAgR1JCTGluRXhwciBsaHMgPSBHUkJMaW5FeHByKCk7CiAgICAgICAgICAgICAgICBsaHMgKz0gZ2xvYmFsX3ZhcltpZHhdOwogICAgICAgICAgICAgICAgbGhzICs9IGxvY2FsX3ZhcltlaWRdOwogICAgICAgICAgICAgICAgR1JCTGluRXhwciByaHMgPSBHUkJMaW5FeHByKDEpOwogICAgICAgICAgICAgICAgbW9kZWwuYWRkQ29uc3RyKGxocywgR1JCX0xFU1NfRVFVQUwsIHJocyk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGRlbHRhX2NvbnN0cmFpbnRfbGhzICs9IGlncmFwaF9jYXR0cmlidXRlX0VBTigmYWxpZ25tZW50X2dyYXBoLCAid2VpZ2h0IiwgZWlkKSpsb2NhbF92YXJbZWlkXTsKCgogICAgICAgICAgICAvLyBhZGRlZCBmb3IgZmVhc2liaWxpdHkgY2hlY2sgb2YgaW5pdHNvbCwgZGVsZXRlIGFmdGVyd2FyZAogICAgICAgICAgICAvKgogICAgICAgICAgICBHUkJMaW5FeHByIGxocyA9IEdSQkxpbkV4cHIoKTsKICAgICAgICAgICAgbGhzICs9IGxvY2FsX3ZhcltlaWRdOwogICAgICAgICAgICBHUkJMaW5FeHByIHJocyA9IEdSQkxpbkV4cHIoKGludClpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oJmFsaWdubWVudF9ncmFwaCwgImluaXRzb2wiLCBlaWQpKTsKICAgICAgICAgICAgbW9kZWwuYWRkQ29uc3RyKGxocywgR1JCX0VRVUFMLCByaHMpOwogICAgICAgICAgICAqLwoKICAgICAgICAgICAgbG9jYWxfdmFyW2VpZF0uc2V0KEdSQl9Eb3VibGVBdHRyX1N0YXJ0ICwgKGludClpZ3JhcGhfY2F0dHJpYnV0ZV9FQU4oJmFsaWdubWVudF9ncmFwaCwgImluaXRzb2wiLCBlaWQpKTsKCgogICAgICAgICAgICBJR1JBUEhfRUlUX05FWFQoZWl0KTsKICAgICAgICB9CgogICAgICAgIG1vZGVsLmFkZENvbnN0cihkZWx0YV9jb25zdHJhaW50X2xocywgR1JCX0xFU1NfRVFVQUwsIGRlbHRhX2NvbnN0cmFpbnRfcmhzKTsKCiAgICAgICAgaWdyYXBoX2VzX2Rlc3Ryb3koJmVzKTsKICAgICAgICBpZ3JhcGhfZWl0X2Rlc3Ryb3koJmVpdCk7CgogICAgICAgIC8qCiAgICAgICAgaWYoVkVSQk9TRSl7CiAgICAgICAgICAgIGF1dG8gc3RvcCA9IGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKTsKICAgICAgICAgICAgYXV0byBkdXJhdGlvbiA9IGR1cmF0aW9uX2Nhc3Q8Y2hyb25vOjptaWxsaXNlY29uZHM+KHN0b3AgLSBzdGFydCk7CiAgICAgICAgICAgIGNvdXQgPDwgIlx0VGltZSBmb3IgYWxpZ25tZW50X2dyYXBoXyIgPDwgYWxpZ25tZW50X2dyYXBoX2lkeCA8PCAiIElMUCBjb25zdHJ1Y3Rpb246ICIgPDwgZHVyYXRpb24uY291bnQoKSA8PCAiIG1pbGxpc2Vjb25kcyIgCiAgICAgICAgICAgICAgICAiIGNvbXBvbmVudCAobW9kZWwpOiAiIDw8IGNvbXBvbmVudCA8PCBlbmRsOwogICAgICAgIH0KICAgICAgICAqLwogICAgICAgIGlncmFwaF9kZXN0cm95KCZhbGlnbm1lbnRfZ3JhcGgpOwogICAgfQoKICAgIC8vIHVwZGF0ZSBhbmQgdmlldyBtb2RlbHMgZm9yIGNoZWNraW5nCiAgICBtb2RlbC51cGRhdGUoKTsKICAgIGlmKFdSSVRFX0lMUFNfVE9fRklMRSl7CiAgICAgICAgc3RyaW5nIGZpbGVfbmFtZSA9ICJtb2RlbF8iICsgdG9fc3RyaW5nKGNvbXBvbmVudCkgKyAiLmxwIjsKICAgICAgICBtb2RlbC53cml0ZShmaWxlX25hbWUpOwogICAgfQogICAgCn0KCgppbnQgbWFpbihpbnQgYXJnYywgY2hhcioqIGFyZ3YpewoKICAgIEdSQkVudiBlbnYgPSBHUkJFbnYoKTsKICAgIGVudi5zZXQoIk91dHB1dEZsYWciLCAiMCIpOwogICAgZW52LnN0YXJ0KCk7CgogICAgaWYoYXJnYyA8IDgpewogICAgICAgIGNvdXQgPDwgIldyb25nIG51bWJlciBvZiBhcmd1bWVudHMgcHJvdmlkZWQiIDw8IGVuZGw7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICBzdHJpbmcgZWRnZV9maWxlX25hbWUgPSBhcmd2WzFdOwogICAgc3RyaW5nIHBvc19zdWJzdHJpbmdfZmlsZV9uYW1lID0gYXJndlsyXTsKICAgIHN0cmluZyBzY3JhdGNoX2RpcmVjdG9yeSA9IGFyZ3ZbM107CiAgICBzdHJpbmcgc29sX2RpcmVjdG9yeSA9IGFyZ3ZbNF07CiAgICBpbnQgYWxwaGEgPSBhdG9pKGFyZ3ZbNV0pOwogICAgaW50IGRlbHRhID0gYXRvaShhcmd2WzZdKTsKICAgIGludCB1c2VfZmlsZXMgPSBhdG9pKGFyZ3ZbN10pOwoKICAgIGlncmFwaF9zZXRfYXR0cmlidXRlX3RhYmxlKCZpZ3JhcGhfY2F0dHJpYnV0ZV90YWJsZSk7CgogICAgLy8gY29uc3RydWN0IHZhcmlhdGlvbiBncmFwaAogICAgaWdyYXBoX3QgdmFyaWF0aW9uX2dyYXBoOwogICAgaW50IG51bV92YXJpYW50czsKCiAgICByZWFkX2VkZ2VfZmlsZShlZGdlX2ZpbGVfbmFtZSwgJnZhcmlhdGlvbl9ncmFwaCwgJm51bV92YXJpYW50cyk7CgogICAgY291dCA8PCAiXG49PT09PT09PT09PT09IFZhcmlhdGlvbiBHcmFwaCBDb25zdHJ1Y3RlZCA9PT09PT09PT09PT09XG4iIDw8IGVuZGw7CiAgICAvL2NvdXQgPDwgIkNvbnN0cnVjdGlvbiB0aW1lOiAiIDw8IGR1cmF0aW9uLmNvdW50KCkgPDwgIiBtaWxsaXNlY29uZHNcbiIgPDxlbmRsOwogICAgY291dCA8PCAiTnVtYmVyIG9mIHZhcmlhbnRzOiAiIDw8IG51bV92YXJpYW50cyA8PCBlbmRsOwogICAgY291dCA8PCAiTnVtYmVyIG9mIHZlcnRpY2VzOiAiIDw8IGlncmFwaF92Y291bnQoJnZhcmlhdGlvbl9ncmFwaCkgPDwgZW5kbDsKICAgIGNvdXQgPDwgIk51bWJlciBvZiBlZGdlczogIiA8PCBpZ3JhcGhfZWNvdW50KCZ2YXJpYXRpb25fZ3JhcGgpIDw8IGVuZGw7CgogICAgY291dCA8PCAiXG5SZWFkaW5nIHBvc19zdWJzdHJpbmcgZmlsZS4uLlxuIiA8PCBlbmRsOwogICAgLy8gcmVhZCBsb2NhdGlvbnMgYW5kIHN0cmluZ3MKICAgIHZlY3RvcjxpbnQ+IHBvc2l0aW9uczsKICAgIHZlY3RvcjxzdHJpbmc+IHN1YnN0cmluZ3M7CgogICAgcmVhZF9wb3Nfc3Vic3RyaW5nX2ZpbGUocG9zX3N1YnN0cmluZ19maWxlX25hbWUsIHBvc2l0aW9ucywgc3Vic3RyaW5ncyk7CiAgICAKICAgIGludCBOID0gcG9zaXRpb25zLnNpemUoKTsKICAgIAogICAgY291dCA8PCAiXG5Db25zdHJ1Y3RpbmcgYWxpZ25tZW50IGdyYXBocy4uLlxuIiA8PCBlbmRsOwogICAgdmVjdG9yPHZlY3RvcjxpbnQ+Kj4gYWxpZ25tZW50X2dyYXBoX3RvX3ZhcmlhbnRzID0gdmVjdG9yPHZlY3RvcjxpbnQ+Kj4oTik7CgoKICAgIHZlY3RvcjxpZ3JhcGhfdCo+IGFsaWdubWVudF9ncmFwaHM7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKXsgCiAgICAgICAgYWxpZ25tZW50X2dyYXBocy5wdXNoX2JhY2sobmV3IGlncmFwaF90KTsgCiAgICB9CgogICAgI3ByYWdtYSBvbXAgcGFyYWxsZWwgZm9yCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKXsgICAgIAogICAgICAgIGlmKFZFUkJPU0UpewogICAgICAgICAgICBjb3V0IDw8ICJDb25zdHJ1Y3RpbmcgYWxpZ25tZW50IGdyYXBocyBmb3IgcG9zaXRpb246ICIgPDwgcG9zaXRpb25zW2ldIDw8IGVuZGw7CiAgICAgICAgfWVsc2UgaWYgKCFWRVJCT1NFICYmIGkgJSBQUklOVF9GQUNUT1IgPT0gMCl7CiAgICAgICAgICAgIGNvdXQgPDwgIkNvbnN0cnVjdGluZyBhbGlnbm1lbnQgZ3JhcGg6ICIgPDwgaSA8PCAiIChwcmludHMgbW9kICIgPDwgUFJJTlRfRkFDVE9SIDw8ICIpIiA8PCBlbmRsOwogICAgICAgIH0KCiAgICAgICAgaWdyYXBoX3QgYWxpZ25tZW50X2dyYXBoOwogICAgICAgIGNyZWF0ZV9hbGlnbm1lbnRfZ3JhcGgoJnZhcmlhdGlvbl9ncmFwaCwgcG9zaXRpb25zW2ldLCBzdWJzdHJpbmdzW2ldLCBhbHBoYSwgZGVsdGEsICZhbGlnbm1lbnRfZ3JhcGgpOwoKICAgICAgICAvLyBvYnRhaW4gc2V0IG9mIHZhcmlhbnRzCiAgICAgICAgYWxpZ25tZW50X2dyYXBoX3RvX3ZhcmlhbnRzW2ldID0gbmV3IHZlY3RvcjxpbnQ+OwogICAgICAgIHVub3JkZXJlZF9zZXQ8aW50PiB2YXJpYW50czsKICAgICAgICBnZXRfdmFyaWFudHMoJmFsaWdubWVudF9ncmFwaCwgdmFyaWFudHMpOwoKICAgICAgICBmb3IoaW50IHY6IHZhcmlhbnRzKXsKICAgICAgICAgICAgYWxpZ25tZW50X2dyYXBoX3RvX3ZhcmlhbnRzW2ldLT5wdXNoX2JhY2sodik7CiAgICAgICAgfQoKICAgICAgICBpZ3JhcGhfY2F0dHJpYnV0ZV9HQU5fc2V0KCZhbGlnbm1lbnRfZ3JhcGgsICJwb3NpdGlvbiIsIHBvc2l0aW9uc1tpXSk7CiAgICAgICAgaWdyYXBoX2NhdHRyaWJ1dGVfR0FTX3NldCgmYWxpZ25tZW50X2dyYXBoLCAic3Vic3RyaW5nIiwgc3Vic3RyaW5nc1tpXS5jX3N0cigpKTsKICAgICAgICAKICAgICAgICBpZih1c2VfZmlsZXMgPT0gMSl7CiAgICAgICAgICAgIHN0cmluZyBmaWxlX25hbWUgPSBzY3JhdGNoX2RpcmVjdG9yeSArICJnXyIgKyB0b19zdHJpbmcoaSk7ICAgICAgICAKICAgICAgICAgICAgd3JpdGVfYWxpZ25tZW50X2dyYXBoX3RvX2ZpbGUoJmFsaWdubWVudF9ncmFwaCwgZmlsZV9uYW1lKTsKICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgaWdyYXBoX2NvcHkoYWxpZ25tZW50X2dyYXBoc1tpXSwgJmFsaWdubWVudF9ncmFwaCk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIAogICAgICAgIC8vc3VtX29mX3NpemVzICs9IGlncmFwaF9lY291bnQoJmFsaWdubWVudF9ncmFwaCk7CgogICAgICAgIGlncmFwaF9kZXN0cm95KCZhbGlnbm1lbnRfZ3JhcGgpOwogICAgfQoKICAgIC8vY291dCA8PCAiYXZlcmFnZSBhbGlnbm1lbnQgZ3JhcGggc2l6ZTogIiA8PCAoZmxvYXQpc3VtX29mX3NpemVzLyhmbG9hdClOIDw8IGVuZGw7CiAgICAKICAgIAogICAgcG9zaXRpb25zLmNsZWFyKCk7CiAgICBwb3NpdGlvbnMuc2hyaW5rX3RvX2ZpdCgpOwogICAgc3Vic3RyaW5ncy5jbGVhcigpOwogICAgc3Vic3RyaW5ncy5zaHJpbmtfdG9fZml0KCk7CgogICAgaWdyYXBoX2Rlc3Ryb3koJnZhcmlhdGlvbl9ncmFwaCk7CiAgICBjb3V0IDw8ICJcbj09PT09PT09PT09PT0gQWxpZ25tZW50IEdyYXBocyBDb25zdHJ1Y3RlZCA9PT09PT09PT09PT09XG4iIDw8IGVuZGw7CgogICAgY291dCA8PCAiQW5hbHl6aW5nIGFsaWdubWVudCBncmFwaCBzZXQuLi4iIDw8IGVuZGw7CgogICAgdmVjdG9yPGludD4gZ2xvYmFsX3ZhcmlhYmxlX3RvX2NvbXBvbmVudDsKICAgIHZlY3RvcjxpbnQ+IHN1YklMUF90b19jb21wb25lbnQ7CiAgICB2ZWN0b3I8aW50PiBnbG9iYWxfdmFyaWFibGVfdG9fbG9jYWxfaWR4OwogICAgdmVjdG9yPGludD4gY29tcG9uZW50X3RvX3ZhcmlhbnRfY291bnQ7CiAgICB2ZWN0b3I8dmVjdG9yPGludD4+IGNvbXBvbmVudF90b19zdWJJTFBzOwogICAgaW50IG51bV9jb21wb25lbnRzOwogICAgYW5hbHl6ZV9hbGlnbm1lbnRfZ3JhcGhfc2V0KG51bV92YXJpYW50cywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHMsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdsb2JhbF92YXJpYWJsZV90b19jb21wb25lbnQsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN1YklMUF90b19jb21wb25lbnQsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdsb2JhbF92YXJpYWJsZV90b19sb2NhbF9pZHgsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbXBvbmVudF90b192YXJpYW50X2NvdW50LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbXBvbmVudF90b19zdWJJTFBzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICZudW1fY29tcG9uZW50cyk7CgogICAgYWxpZ25tZW50X2dyYXBoX3RvX3ZhcmlhbnRzLmNsZWFyKCk7CiAgICBhbGlnbm1lbnRfZ3JhcGhfdG9fdmFyaWFudHMuc2hyaW5rX3RvX2ZpdCgpOwoKICAgIGNvdXQgPDwgIlxuPT09PT09PT09PT09PSBBbGlnbm1lbnQgR3JhcGhzIEFuYWx5emVkID09PT09PT09PT09PT1cbiIgPDwgZW5kbDsKICAgIGNvdXQgPDwgIm51bWJlciBvZiBjb21wb25lbnRzOiAiIDw8IG51bV9jb21wb25lbnRzIDw8IGVuZGw7CgogICAgLy8gd2UgbmVlZCB0byBpbnZlcnQgdGhlIG1hcCBmcm9tIHNlcGFyYXRlIElMUHMKICAgIG1hcDxwYWlyPGludCwgaW50PiwgaW50PiBjb21wb25lbnRfaW5kZXhfcGFpcl90b192YXJpYW50OwogICAgZm9yKGludCBpID0gMDsgaSA8IG51bV92YXJpYW50czsgaSsrKXsKICAgICAgICAKICAgICAgICBhdXRvIHAgPSBtYWtlX3BhaXIoZ2xvYmFsX3ZhcmlhYmxlX3RvX2NvbXBvbmVudFtpXSwgZ2xvYmFsX3ZhcmlhYmxlX3RvX2xvY2FsX2lkeFtpXSk7CgogICAgICAgIGlmKGNvbXBvbmVudF9pbmRleF9wYWlyX3RvX3ZhcmlhbnQuZmluZChwKSA9PSBjb21wb25lbnRfaW5kZXhfcGFpcl90b192YXJpYW50LmVuZCgpKXsKICAgICAgICAgICAgY29tcG9uZW50X2luZGV4X3BhaXJfdG9fdmFyaWFudFtwXSA9IGk7CiAgICAgICAgfQogICAgfQoKICAgIAogICAgY291dCA8PCAiXG5Db25zdHJ1Y3RpbmcgSUxQIG1vZGVscyBmcm9tIGFsaWdubWVudCBncmFwaHMuLi5cbiIgPDwgZW5kbDsKICAgIAogICAgdmVjdG9yPGludD4gc29sdXRpb24gPSB2ZWN0b3I8aW50PihudW1fdmFyaWFudHMsIDEpOwoKICAgIGJvb2wgc29tZV9JTFBfdGltZWRfb3V0ID0gZmFsc2U7CgogICAgI3ByYWdtYSBvbXAgcGFyYWxsZWwgZm9yCiAgICBmb3IoaW50IGNvbXBvbmVudCA9IDA7IGNvbXBvbmVudCA8IG51bV9jb21wb25lbnRzOyBjb21wb25lbnQrKyl7CiAgICAgICAgCiAgICAgICAgaWYoY29tcG9uZW50ICUgUFJJTlRfRkFDVE9SID09IDApewogICAgICAgICAgICBjb3V0IDw8ICJTb2x2aW5nIElMUF8iIDw8IGNvbXBvbmVudCA8PCAiIG91dCBvZiAiIDw8ICBudW1fY29tcG9uZW50cyA8PCAiIChwcmludHMgbW9kICIgPDwgUFJJTlRfRkFDVE9SIDw8ICIpIiA8PGVuZGw7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8vY291dCA8PCAiU29sdmluZyBJTFBfIiA8PCBjb21wb25lbnQgPDwgIiBvdXQgb2YgIiA8PCAgbnVtX2NvbXBvbmVudHMgPDwgZW5kbDsKCgogICAgICAgIC8vY291dCA8PCAiY29tcG9uZW50OiAiIDw8IGNvbXBvbmVudCA8PCBlbmRsOyAKICAgICAgICBpZihjb21wb25lbnRfdG9fc3ViSUxQc1tjb21wb25lbnRdLnNpemUoKSA+IDApewoKICAgICAgICAgICAgR1JCTW9kZWwgbW9kZWwgPSBHUkJNb2RlbChlbnYpOwoKICAgICAgICAgICAgY29uc3RydWN0X0lMUHMoY29tcG9uZW50LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgY29tcG9uZW50X3RvX3N1YklMUHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBnbG9iYWxfdmFyaWFibGVfdG9fbG9jYWxfaWR4LCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbXBvbmVudF90b192YXJpYW50X2NvdW50LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgbW9kZWwsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkZWx0YSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNjcmF0Y2hfZGlyZWN0b3J5LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgYWxpZ25tZW50X2dyYXBocywKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHVzZV9maWxlcwogICAgICAgICAgICAgICAgICAgICAgICAgICAgKTsKICAgICAgICAgICAgLy9jb3V0IDw8ICJcbj09PT09PT09PT09PT0gSUxQIG1vZGVsICI8PCBjb21wb25lbnQgPDwgIiBjb25zdHJ1Y3RlZCA9PT09PT09PT09PT09XG4iIDw8IGVuZGw7CiAgICAgICAgICAgIAogICAgICAgICAgICAKICAgICAgICAgICAgbW9kZWwuZ2V0RW52KCkuc2V0KEdSQl9Eb3VibGVQYXJhbV9UaW1lTGltaXQsIElMUF9USU1FX0xJTUlUKTsKICAgICAgICAgICAgYXV0byBzdGFydCA9IGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKTsKICAgICAgICAgICAgbW9kZWwub3B0aW1pemUoKTsKICAgICAgICAgICAgYXV0byBzdG9wID0gY2hyb25vOjpzdGVhZHlfY2xvY2s6Om5vdygpOwogICAgICAgICAgICBhdXRvIGR1cmF0aW9uID0gZHVyYXRpb25fY2FzdDxjaHJvbm86OnNlY29uZHM+KHN0b3AgLSBzdGFydCk7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZihkdXJhdGlvbi5jb3VudCgpID4gLjk1ICogSUxQX1RJTUVfTElNSVQpewogICAgICAgICAgICAgICAgY291dCA8PCAiSUxQIHdhcyB0aW1lZCBvdXQiIDw8IGVuZGw7CiAgICAgICAgICAgICAgICBzb21lX0lMUF90aW1lZF9vdXQgPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIC8vaWYoVkVSQk9TRSl7CiAgICAgICAgICAgIC8vICAgIGNvdXQgPDwgInRpbWU6ICIgPDwgZHVyYXRpb24uY291bnQoKSA8PCAiIG1pbGxpc2Vjb25kc1xuIiA8PGVuZGw7CiAgICAgICAgICAgIC8vfQogICAgICAgICAgICAKICAgICAgICAgICAgLy9jb3V0IDw8ICJcbj09PT09PT09PT09PT0gSUxQIG1vZGVscyBzb2x2ZWQgPT09PT09PT09PT09PVxuIiA8PCBlbmRsOwoKICAgICAgICAgICAgR1JCVmFyKiB2YXJzID0gTlVMTDsKICAgICAgICAgICAgdmFycyA9IG1vZGVsLmdldFZhcnMoKTsKICAgICAgICAgICAgLy9jb3V0IDw8ICJJTFBfIiA8PCBjb21wb25lbnQgPDwgIiBsb2NhbCBhc3NpZ25tZW50czogIiA8PCBlbmRsOwogICAgICAgICAgICAvL2NvdXQgPDwgInZhcmlhYmxlIGNvdW50OiAiIDw8IGNvbXBvbmVudF90b192YXJpYW50X2NvdW50W2NvbXBvbmVudF0gPDwgZW5kbDsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBjb21wb25lbnRfdG9fdmFyaWFudF9jb3VudFtjb21wb25lbnRdOyBqKyspIHsKICAgICAgICAgICAgICAgIC8vY291dCA8PCB2YXJzW2pdLmdldChHUkJfU3RyaW5nQXR0cl9WYXJOYW1lKSA8PCAiID0gIiA8PCB2YXJzW2pdLmdldChHUkJfRG91YmxlQXR0cl9YKSA8PCBlbmRsOwogICAgICAgICAgICAgICAgc29sdXRpb25bY29tcG9uZW50X2luZGV4X3BhaXJfdG9fdmFyaWFudFttYWtlX3BhaXIoY29tcG9uZW50LCBqKV1dID0gdmFyc1tqXS5nZXQoR1JCX0RvdWJsZUF0dHJfWCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgfQogICAgICAgIAogICAgaW50IHN1bSA9IDA7CiAgICBjb3V0IDw8ICJcbkZpbmFsIGFzc2lnbm1lbnQ6ICIgPDwgZW5kbDsKCgogICAgc3RyaW5nIHNvbF9maWxlX25hbWUgPSBzb2xfZGlyZWN0b3J5ICsgIklMUF9zb2xfIiArIHRvX3N0cmluZyhhbHBoYSkgKyAiXyIgKyB0b19zdHJpbmcoZGVsdGEpICsgIl8iICsgdG9fc3RyaW5nKE4pOwogICAgb2ZzdHJlYW0gb3V0X2ZpbGUoc29sX2ZpbGVfbmFtZSk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgc29sdXRpb24uc2l6ZSgpOyBpKyspewogICAgICAgIGNvdXQgPDwgInhfIiA8PCBpIDw8ICIgPSAiIDw8IHNvbHV0aW9uW2ldIDw8IGVuZGw7CiAgICAgICAgb3V0X2ZpbGUgPDwgc29sdXRpb25baV0gPDwgZW5kbDsKICAgICAgICBzdW0gKz0gc29sdXRpb25baV07CiAgICB9CiAgICBvdXRfZmlsZS5jbG9zZSgpOwogICAgY291dCA8PCAiXG5OdW1iZXIgb2YgdmFyaWFudHMgZGVsZXRlZDogIiA8PCBzdW0gPDwgIiBvdXQgb2YgIiA8PCBudW1fdmFyaWFudHMgPDxlbmRsOwogICAgaWYoc29tZV9JTFBfdGltZWRfb3V0KXsKICAgICAgICBjb3V0IDw8ICJTb21lIElMUCB3YXMgdGltZWQtb3V0LCBzb2x1dGlvbiBtYXkgYmUgc3ViLW9wdGltYWwiIDw8IGVuZGw7CiAgICB9ZWxzZXsKICAgICAgICBjb3V0IDw8ICJObyBJTFBzIHdlcmUgdGltZWQtb3V0LCBzb2x1dGlvbiBpcyBvcHRpbWFsIiA8PCBlbmRsOwogICAgfQogICAgCgp9