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

vector<int> p;

void find_portal(int l, int r, int cnt){
    if(cnt == 0)return;
    if(l == r){
        p.push_back(l); return;
    }
    int m = (l + r) / 2;
    int x = find_portals(l, m);
    int y = cnt - x;
    find_portal(l, m, x);
    find_portal(m + 1, r, y);
}

vector<int> portals(int n, int k){
    find_portal(1, n, k);
    sort(p.begin(), p.end());
    return p;
}

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

pair<int, int> find(int x, int y, int a, int b){
    if(x == a && y == b)return {x, y};
    int nx = (x + a) / 2, ny = (y + b) / 2;
    string dirr = throw_eye({nx, ny});
    if(dirr == "NE")  return find(nx + 1, ny + 1, a + 0 , b);
    if(dirr == "N")   return find(nx + 0, ny + 1, nx + 0, b);
    if(dirr == "NW")  return find(x + 0 , ny + 1, nx - 1, b);
    if(dirr == "E")   return find(nx + 1, ny + 0, a + 0 , ny);
    if(dirr == "NONE")return {nx, ny};
    if(dirr == "W")   return find(x + 0 , ny + 0, nx - 1, ny);
    if(dirr == "SE")  return find(nx + 1, y + 0 , a + 0 , ny - 1);
    if(dirr == "S")   return find(nx + 0, y + 0 , nx + 0, ny - 1);
    if(dirr == "SW")  return find(x + 0 , y + 0 , nx - 1, ny - 1);
}

pair<int, int> find_end_portal(int L) {
    return find(1, 1, L, L);
}
