#include "minecraft.h"
#include <bits/stdc++.h>
using namespace std;

int uniK;

vector<int> portals(int n, int k) {
    return {0, 0};
}

typedef long long int LL;

pair<int, int> minimal_danger(int N, vector<pair<int, pair<int, int>>> paths,
                                   vector<int> portals, vector<int> fortresses) {
    return {1, 1};
}

pair<int, int> find_end_portal(int L) {
    int lx = 1, ly = 1, rx = L, ry = L;
    while(lx <= rx && ly <= ry) {
        if(clock() / (double)CLOCKS_PER_SEC > 0.68) return {1, 1};
       // cout << lx << " " << ly << " " << rx << " " << ry << endl;
        if(lx == rx && ly == ry) return {lx, rx};
        if(lx == rx) {
            int l1 = ly, r1 = ry, mid;
            while(l1 <= r1) {
                mid = (l1 + r1) >> 1;
                if(l1 == r1) return {lx, mid};
                string s = throw_eye({lx, mid});
                if(s == "NONE") {
                    return {lx, mid};
                }
                if(s == "W") {
                    r1 = mid - 1;
                }
                else {
                    l1 = mid + 1;
                }
            }
        }
        if(ly == ry) {
            int l1 = lx, r1 = rx, mid;
            while(l1 <= r1) {
                mid = (l1 + r1) >> 1;
                if(l1 == r1) return {mid, ly};
                string s = throw_eye({mid, ly});
                if(s == "NONE") {
                    return {mid, ly};
                }
                if(s == "S") {
                    r1 = mid - 1;
                }
                else {
                    l1 = mid + 1;
                }
            }
        }
        int midx = (lx + rx) >> 1, midy = (ly + ry) >> 1;
        string q = throw_eye({midx, midy});
        if(q == "W" || q == "NW" || q == "N") {
            ly = midy, rx = midx;
        }
        else if(q == "S" || q == "SW") {
            rx = midx, ry = midy - 1;
        }
        else if(q == "SE") {
            lx = midx + 1, ry = midy - 1;
        }
        else {
            lx = midx + 1, ly = midy;
        }
    }
}

/*

100 2
55 90
2
55 12 15
12 77 5
1
77
99
6 7

*/









