#include "minecraft.h"
#include <vector>

/**
____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <random>
#include <algorithm>

#define maxn 200005
#define maxlog 21
#define PB push_back
#define X first
#define Y second
#define control cout<<"passed"<<endl;

typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, ll> pil;
typedef std::pair<ll, int> pli;
typedef long double ld;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")


const ll mod = 1e9 + 7;
const ll INF = 4e18;
const double eps = 1e-12;

void solvep(int l , int r , int k , std::vector <int>& ret)
{
    if (k == 0)
        return;

    if (l == r)
    {
        for (int i = 0; i < k; i++)
            ret.PB(l);
        return;
    }

    int mid = (l + r) / 2;
    int le = find_portals(l , mid);
    if (le > 0)
        solvep(l , mid , le , ret);

    int ri = k - le;
    if (ri > 0)
        solvep(mid + 1 , r , ri , ret);
}


std::vector<int> portals(int n, int k)
{
    std::vector <int> ret;
    solvep(1 , n , k , ret);
    return ret;
}

std::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};
}

std::pair<int, int> find_end_portal(int l)
{
    int lx = 1 , rx = l , ly = 1 , ry = l;

    while (lx <= rx && ly <= ry)
    {
        int midx = (lx + rx) / 2 , midy = (ly + ry) / 2;

        std::string pom = throw_eye({midx , midy});

        if (pom == "NONE")
            return {midx , midy};

        if (pom == "E" || pom == "NE" || pom == "SE")
            lx = midx + 1;
        else if (pom == "W" || pom == "NW" || pom == "SW")
            rx = midx - 1;
        else
        {
            lx = midx;
            rx = midx;
        }

        if (pom == "N" || pom == "NE" || pom == "NW")
            ly = midy + 1;
        else if (pom == "S" || pom == "SE" || pom == "SW")
            ry = midy - 1;
        else
        {
            ly = midy;
            ry = midy;
        }
    }

    return {lx , ly};
}