
std::pair<int, int> find_end_portal(int L) {
    int lx = 1, rx = L, ly = 1, ry = L;
    while (lx < rx || ly < ry) {
        int mx = (lx + rx) / 2;
        int my = (ly + ry) / 2;
        string s = throw_eye({mx, my});
        if (s.find('E') != string::npos) {
            lx = mx + 1;
        }
        else if (s.find('W') != string::npos) {
            rx = mx - 1;
        }
        else {
            lx = rx = mx;
        }
        if (s.find('N') != string::npos) {
            ly = my + 1;
        }
        else if (s.find('S') != string::npos) {
            ry = my - 1;
        }
        else {
            ly = ry = my;
        }
    }
    return {lx, ly};
}
