// Stress test

from os import system as cmd

cmd("g++ slow.cpp -std=c++17 -oslow")
cmd("g++ wrong.cpp -std=c++17 -owrong")
print("Compiled")

for i in range(10000):
    if i % 10 == 0:
        print(i)
    cmd("python3 gen.py > test.txt")
    cmd("./slow < test.txt > slow.txt")
    cmd("./wrong < test.txt > wrong.txt")
    if open("slow.txt").read().rstrip().split() != open("wrong.txt").read().rstrip().split():
        exit(0)




// Pragmas Collection

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")

// Fast Alloc

const int MAX_MEM = 1e8;
int mpos = 0;
char mem[MAX_MEM];
inline void * operator new ( size_t n ) {
char *res = mem + mpos;
mpos += n;
assert(mpos <= MAX_MEM);
return (void *)res;
}
inline void operator delete ( void * ) { }


// Policy based treap

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
s.insert(x);
s.erase(x);
s.count(x);
s.find_by_order(k); // k-й по величине элемент в множестве
s.order_of_key(x); // сколько элементов в множестве меньше x


// Policy based hashtable

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef gp_hash_table<int, int, hash<int>, equal_to<int>, direct_mod_range_hashing<int>, linear_probe_fn<>,
                      hash_standard_resize_policy<hash_prime_size_policy, hash_load_check_resize_trigger<true>, true>>
    gp;

// Bitset

bitset<N> a;
for (int i = a._Find_first(); i != a.size(); i = a._Find_next(i)) {
    cout << i << endl;
}

//  Bit Gauss

int basis[d];
int sz;

void insertVector(int mask) {
    for (int i = 0; i < d; i++) {
        if ((mask & 1 << i) == 0) continue;
        if (!basis[i]) {
            basis[i] = mask;
            ++sz;
            return;
        }

        mask ^= basis[i];
    }
}

// Fedya the Potter

// sum(i=0..n-1) (a+b*i) div m
ll solve(ll n, ll a, ll b, ll m) {
    if (b == 0) return n * (a / m);
    if (a >= m) return n * (a / m) + solve(n, a % m, b, m);
    if (b >= m) return n * (n - 1) / 2 * (b / m) + solve(n, a, b % m, m);
    return solve((a + b * n) / m, (a + b * n) % m, m, b);
}

int CRT(int a1, int m1, int a2, int m2) {
    return (a1 - a2 % m1 + m1) * (ll)rev(m2, m1) % m1 * m2 + a2;
}

// ExtGcd

int gcd (int a, int b, int & x, int & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
// Suffix array and stuff


vector<int> suffix_array(string s){
    int n = len(s);
    vector<int> cl(n); forn (i, n) cl[i] = s[i];
    for (int gap = 1;; gap *= 2) {
        vector<pair<int, int>> nw(n); forn (i, n) nw[i] = make_pair(cl[i], cl[(i + gap) % n]);
        auto old = nw; stable_sort(all(nw)); nw.resize(unique(all(nw)) - nw.begin());
        forn (i, n)  cl[i] = lower_bound(all(nw), old[i]) - nw.begin();
        if (len(nw) == n) break;
    }
    vector<int> sa(n); forn (i, n) sa[cl[i]] = i;
    return sa;
}

struct D {
    int x, y, z;
    bool operator<(const D& a) const { return x < a.x || x == a.x && y < a.y; }
} d[1 << 21];
int j, k, c[(1 << 19) + 7], b[100], a[100], i, n;
char s[(1 << 19) + 7];
int main() {
    scanf("%s", s);
    n = strlen(s);
    s[n++] = 47;
    R(i, n) a[s[i] - 47]++;
    b[0] = 1;
    R(i, 100) b[i] = b[i - 1] + (a[i] > 0);
    R(i, n) c[i] = b[s[i] - 47];
    for (k = 0; (1 << k) < n; k++) {
        R(i, n) d[i] = (D){ c[i], c[i + (1 << k)], i };
        std::stable_sort(d, d + n);
        j = c[d[0].z] = 1;
        R(i, n - 1) { c[d[i + 1].z] = d[i] < d[i + 1] ? ++j : j; }
        if (j == n)
            break;
    }
    printf("%d ", n - 1);
    R(i, n - 1) printf("%d ", d[i + 1].z );
}


  void BuildLCP( int n, T *s ) { // O(N), works only for s with no nontrivial period
    int lcp = 0;
    forn(i, n) {
      int j = p2[i];
      if (--lcp < 0)
        lcp = 0;
      if (j != n - 1)
        while (lcp < n && s[(p[j] + lcp) % n] == s[(p[j + 1] + lcp) % n])
          lcp++;
      len[j] = lcp;
    }



// SetCht online



bool QUERY;
struct Line {
    mutable T a, b, p;
    T Eval(T x) const { return a * x + b; }
    bool operator<(const Line& o) const {
        return QUERY ? p < o.p : a < o.a;
    }
};

struct LineContainer : multiset<Line> {
    // for doubles, use kInf = 1/.0, div(a, b) = a / b
    const T kInf = numeric_limits<T>::max();
    T div(T a, T b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = kInf; return false; }
        if (x->a == y->a) x->p = x->b > y->b ? kInf : -kInf;
        else x->p = div(y->b - x->b, x->a - y->a);
        return x->p >= y->p;
    }
    void InsertLine(T a, T b) {
        auto nx = insert({a, b, 0}), it = nx++, pv = it;
        while (isect(it, nx)) nx = erase(nx);
        if (pv != begin() && isect(--pv, it)) isect(pv, it = erase(it));
        while ((it = pv) != begin() && (--pv)->p >= it->p)
            isect(pv, erase(it));
    }
    T EvalMax(T x) {
        assert(!empty());
        QUERY = 1; auto it = lower_bound({0,0,x}); QUERY = 0;
        return it->Eval(x);
    }
};
// Treap



struct node {
    node *left, *right;
    int val;
    int pri;
    int sz;
    int min_val;
    bool rev;

    node(int nval){
        left = right = nullptr;
        val = nval;
        min_val = val;
        pri = rnd();
        rev = false;
        sz = 1;
    }
};

int get_sz(node* v){
    return (v == nullptr ? 0 : v->sz);
}
const int inf = (int) 1e9 + 7;
int get_mval(node*v){
    return v == nullptr ? inf : v->min_val;
}
void push(node* v){
    if (v == nullptr) return;
    if (v->rev){
        swap(v->left, v->right);
        if (v->left != nullptr) v->left->rev ^= 1;
        if (v->right != nullptr) v->right->rev ^= 1;
        v->rev = false;
    }
}


void upd(node* v){
    if (v == nullptr) return;
    push(v);
    v->sz = 1 + get_sz(v->left) + get_sz(v->right);
    v->min_val = min(v->val, min(get_mval(v->left), get_mval(v->right)));
}


node* merge(node* A, node* B){
    if (A == nullptr || B == nullptr)
        return A == nullptr ? B : A;
    push(A); push(B);
    if (A->pri > B->pri){
        A->right = merge(A->right, B);
        upd(A);
        return A;
    }
    B->left = merge(A, B->left);
    upd(B);
    return B;
}


pair<node*, node*> split(node* v, int sz){
    if (v == nullptr){
        return {nullptr, nullptr};
    }
    push(v);
    if (sz <= get_sz(v->left)){
        auto splitted = split(v->left, sz);
        v->left = splitted.second;
        upd(v);
        return {splitted.first, v};
    }
    auto splitted = split(v->right, sz - get_sz(v->left) - 1);
    v->right = splitted.first;
    upd(v);
    return {v, splitted.second};
}

node* push_back(node* tree, int val){
    tree = merge(tree, new node(val));
    return tree;
}

node* reverse(node* tree, int l, int r){ // [l, r], 0-indexing
    auto splitted1 = split(tree, l);
    auto splitted2 = split(splitted1.second, r - l + 1);
    if (splitted2.first != nullptr){
        splitted2.first->rev ^= 1;
        push(splitted2.first);
    }
    return merge(splitted1.first, merge(splitted2.first, splitted2.second));
}

void print_tree(node* v){
    if (v == nullptr)
        return;
    print_tree(v->left);
    cout << v->val << ' ';
    print_tree(v->right);
}

pair<node*, int> get_min(node* tree, int l, int r){
    auto splitted1 = split(tree, l);
    auto splitted2 = split(splitted1.second, r - l + 1);
    int ans = get_mval(splitted2.first);
    // print_tree(splitted2.first); cout << endl;
    return {merge(splitted1.first, merge(splitted2.first, splitted2.second)), ans};
}









struct FFTSolver {
  using Complex = complex<double>;
  const double kPi = 4.0 * atan(1.0);
  vector<int> rev;

  int __lg(int n) { return n == 1 ? 0 : 1 + __lg(n / 2); }

  void compute_rev(int n, int lg) {
    rev.resize(n); rev[0] = 0;
    for (int i = 1; i < n; ++i) {
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
    }
  }

  vector<Complex> fft(vector<Complex> V, bool invert) {
    int n = V.size(), lg = __lg(n);
    if ((int)rev.size() != n) compute_rev(n, lg);

    for (int i = 0; i < n; ++i) {
      if (i < rev[i])
        swap(V[i], V[rev[i]]);
    }

    for (int step = 2; step <= n; step *= 2) {
      const double ang = 2 * kPi / step;
      Complex eps(cos(ang), sin(ang));
      if (invert) eps = conj(eps);

      for (int i = 0; i < n; i += step) {
        Complex w = 1;
        for (int a = i, b = i+step/2; b < i+step; ++a, ++b) {
          Complex aux = w * V[b];
          V[b] = V[a] - aux;
          V[a] = V[a] + aux;
          w *= eps;
        }
      }
    }

    return V;
  }

  vector<Complex> transform(vector<Complex> V) {
    int n = V.size();
    vector<Complex> ret(n);
    Complex div_x = Complex(0, 1) * (4.0 * n);

    for (int i = 0; i < n; ++i) {
      int j = (n - i) % n;
      ret[i] = (V[i] + conj(V[j]))
        * (V[i] - conj(V[j])) / div_x;
    }

    return ret;
  }

  vector<int> Multiply(vector<int> A, vector<int> B) {
    int n = A.size() + B.size() - 1;
    vector<int> ret(n);
    while (n != (n & -n)) ++n;

    A.resize(n); B.resize(n);
    vector<Complex> V(n);
    for (int i = 0; i < n; ++i) {
      V[i] = Complex(A[i], B[i]);
    }

    V = fft(move(V), false);
    V = transform(move(V));
    V = fft(move(V), true);

    for (int i = 0; i < (int)ret.size(); ++i)
      ret[i] = round(real(V[i]));
    return ret;
  }
};




// Bridges

void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] > tin[v])
                IS_BRIDGE(v,to);
        }
    }
}

void find_bridges() {
    timer = 0;
    for (int i=0; i<n; ++i)
        used[i] = false;
    for (int i=0; i<n; ++i)
        if (!used[i])
            dfs (i);
}

// DCP offline


class DynamicConnectivity {
private:
    struct Query {
        int type, v, w, otherTime;
    };

    int V, curTime = 0, cnt;
    vector<Query> queries;
    vector<int> ans;
    vector<int> presentEdges;

    DSU ds;


    void solve(int l, int r) {
        if (l >= r) {
            if (l == r && queries[r].type == 0) ans.push_back(ds.get());
            return;
        }
        int m = l + (r - l) / 2;
        int cur = ds.curver;
        for (int i = m + 1; i <= r; i++) if (queries[i].otherTime < l) ds.add(queries[i].v, queries[i].w);
        solve(l, m);
        while (ds.curver > cur) ds.rollback();
        for (int i = l; i <= m; i++) if (queries[i].otherTime > r) ds.add(queries[i].v, queries[i].w);
        solve(m + 1, r);
        while (ds.curver > cur) ds.rollback();
    }

public:
    DynamicConnectivity(int V): V(V), curTime(0), cnt(V), presentEdges(V) {}

    void addEdge(int v, int w, int id) {
        presentEdges[id] = curTime++;
        queries.push_back({1, v, w, INT_MAX});
    }

    void removeEdge(int v, int w, int id) {
        int insTime = presentEdges[id];
        queries.push_back({-1, v, w, insTime});
        queries[insTime].otherTime = curTime++;
        presentEdges[id] = -100;
    }

    void query() {
        queries.push_back({0, -1, -1, curTime++});
    }

    vector<int> solve() {
        ds.build();
        solve(0, curTime - 1);
        return ans;
    }
};

// Aho-Corasick

template <const int maxV, const int E>
struct AhoCorasic {
  struct Vertex {
    int next[E], p, dep, ch, suf, end;
  };

  int vn;
  Vertex a[maxV];
  int qst, qen, q[maxV];

  int newV( int P, int D, int K ) {
    assert(vn < maxV);
    Vertex &v = a[vn];
    v.dep = D, v.ch = K, v.p = P, v.end = 0;
    zero(v.next);
    return vn++;
  }

  AhoCorasic() {
    vn = 0, newV(-1, 0, -1);
  }

  void add( const char *s ) {
    int v = 0;
    while (*s) {
      int ch = *s++ - 'a', &x = a[v].next[ch];
      if (!x)
        x = newV(v, a[v].dep + 1, ch);
      v = x;
    }
    a[v].end = 1;
  }

  void build() {
    qst = qen = 0;
    q[qen++] = 0;
    while (qst < qen) {
      int v = q[qst++];
      Vertex &V = a[v];
      V.suf = (V.dep <= 1 ? 0 : a[a[V.p].suf].next[V.ch]);
      forn(i, 26)
        if (V.next[i])
          q[qen++] = V.next[i];
        else
          V.next[i] = a[V.suf].next[i];
      V.end |= a[V.suf].end;
    }
  }
};

AhoCorasic<(int)1e5, 26> m;


// Tree Compression


vector<int> CompressTree(vector<int> v, LCA& lca,
                         vector<int>& link) {
  auto cmp = [&](int a, int b) {
    return lca.enter[a] < lca.enter[b];
  };
  sort(v.begin(), v.end(), cmp);
  v.erase(unique(v.begin(), v.end()), v.end());

  for (int i = (int)v.size() - 1; i > 0; --i)
    v.push_back(lca.Query(v[i - 1], v[i]));

  sort(v.begin(), v.end(), cmp);
  v.erase(unique(v.begin(), v.end()), v.end());

  for (int i = 0; i < (int)v.size(); ++i)
    link[v[i]] = (i == 0 ? -1 : lca.Query(v[i - 1], v[i]));
  return v;
}

vector<int> g[MAXN];
bool used[MAXN];
int timer, tin[MAXN], fup[MAXN];

void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    int children = 0;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] >= tin[v] && p != -1)
                IS_CUTPOINT(v);
            ++children;
        }
    }
    if (p == -1 && children > 1)
        IS_CUTPOINT(v);
}




struct Dinic {
  struct Edge { int to, cap, flow, nxt; };

  vector<Edge> edges;
  vector<int> graph, at, dist;
  int src = 0, dest = 1;

  Dinic(int n) : graph(n, -1), dist(n, -1) {}

  void add_edge(int from, int to, int cap) {
    edges.push_back(Edge {to, cap, 0, graph[from]});
    graph[from] = edges.size() - 1;
  }
  void AddEdge(int from, int to, int cap) {
    add_edge(from, to, cap);
    add_edge(to, from, 0);
  }

  bool bfs() {
    queue<int> q;
    fill(dist.begin(), dist.end(), -1);
    dist[src] = 0; q.push(src);

    while (!q.empty()) {
      int node = q.front(); q.pop();
      for (int i = graph[node]; i >= 0; i = edges[i].nxt) {
        const auto &e = edges[i];
        if (dist[e.to] == -1 && e.flow < e.cap) {
          dist[e.to] = dist[node] + 1;
          q.push(e.to);
        }
      }
    }

    return dist[dest] != -1;
  }

  int dfs(int node, int flow) {
    if (flow == 0) return 0;
    if (node == dest) return flow;

    while (at[node] != -1) {
      int eid = at[node]; const auto &e = edges[eid];

      if (dist[e.to] == dist[node] + 1) {
        if (int ret = dfs(e.to, min(flow, e.cap - e.flow))) {
          edges[ eid ].flow += ret;
          edges[eid^1].flow -= ret;
          return ret;
        }
      }

      at[node] = e.nxt;
    }
    return 0;
  }

  int Compute(int src, int dest) {
    this->src = src; this->dest = dest; int ret = 0;
    while (bfs()) {
      at = graph;
      while (int flow = dfs(src, 2e9))
        ret += flow;
    }
    return ret;
  }
};



// Centroid

vector<int> good;
vector<vector<int>> g;
string city_l;
vector<int> ans;


const int MAXN = (int) 2e5 + 7;
int level[MAXN];
int parent[MAXN];

const static int maxn = 4e6;
int root_masks[maxn], cur_mask[maxn];
int root_masks_clear[maxn], root_masks_cur = 0;
int cur_mask_clear[maxn], cur_mask_cur = 0;

void dfs_root_masks(int v, int mask, int p){
    mask = mask ^ ((1ll << (city_l[v] - 'a')));
    root_masks[mask]++;
    root_masks_clear[root_masks_cur++] = mask;
    for (auto u : g[v])
        if (u != p && level[u] == -1)
            dfs_root_masks(u, mask, v);
}



void dfs_cur_mask(int v, int mask, int p){
    mask = mask ^ ((1ll << (city_l[v] - 'a')));
    cur_mask[mask]++;
    cur_mask_clear[cur_mask_cur++] = mask;
    for (auto u : g[v])
        if (u != p && level[u] == -1)
            dfs_cur_mask(u, mask, v);
}

int dfs_calc(int v, int center, int mask, int p) {
    mask = mask ^ ((1ll << (city_l[v] - 'a')));
    int res = 0;
    for (auto i : good){
        res += (root_masks[mask ^ i] - cur_mask[mask ^ i  ^ (1ll << (city_l[center] - 'a'))]);
    }
    for (auto u : g[v]){
        if (u != p && level[u] == -1)
            res += dfs_calc(u, center, mask, v);
    }

    ans[v] += res;
    return res;
}


int dfs_(int v, int cur_mask = 0, int p = -1){
    cur_mask = cur_mask ^ (1ll << (city_l[v] - 'a'));
    int cur = 0;
    if (count(all(good), cur_mask))
        ++cur;
    for (auto u : g[v])
        if (u != p && level[u] == -1)
            cur += dfs_(u, cur_mask, v);
    return cur;
}

void process(int center){
    vector<int> sons;
    for (auto u : g[center]){
        if (level[u] == -1)
            sons.push_back(u);
    }

    while (root_masks_cur > 0){ root_masks[root_masks_clear[--root_masks_cur]] = 0;}


    dfs_root_masks(center, 0, -1);
    int to_add = 0;
    forn (u, len(sons)){

        while (cur_mask_cur > 0){ cur_mask[cur_mask_clear[--cur_mask_cur]] = 0;}

        dfs_cur_mask(sons[u], 0, center);
        to_add += dfs_calc(sons[u], center, 0, center);
    }
    ans[center] += (to_add + dfs_(center)) / 2 + 1;
}

int dfs(int v, int size, int &center, int p = -1) {
    int sum = 1;
    for (int x : g[v])
        if (level[x] == -1 && x != p)
            sum += dfs(x, size, center, v);
    if (center == -1 && (2 * sum >= size || p == -1))
        center = v;
    return sum;
}

void build(int v, int size, int depth, int last) {
    int center = -1;
    dfs(v, size, center);
    process(center);
    level[center] = depth;
    parent[center] = last;
    for (int x : g[center])
        if (level[x] == -1)
            build(x, size / 2, depth + 1, center);
};


// SCC

vector < vector<int> > g, gr;
vector<char> used;
vector<int> order, component;

void dfs1 (int v) {
    used[v] = true;
    for (size_t i=0; i<g[v].size(); ++i)
        if (!used[ g[v][i] ])
            dfs1 (g[v][i]);
    order.push_back (v);
}

void dfs2 (int v) {
    used[v] = true;
    component.push_back (v);
    for (size_t i=0; i<gr[v].size(); ++i)
        if (!used[ gr[v][i] ])
            dfs2 (gr[v][i]);
}

int main() {
    int n;
    ... чтение n ...
    for (;;) {
        int a, b;
        ... чтение очередного ребра (a,b) ...
        g[a].push_back (b);
        gr[b].push_back (a);
    }

    used.assign (n, false);
    for (int i=0; i<n; ++i)
        if (!used[i])
            dfs1 (i);
    used.assign (n, false);
    for (int i=0; i<n; ++i) {
        int v = order[n-1-i];
        if (!used[v]) {
            dfs2 (v);
            ... вывод очередной component ...
            component.clear();
        }
    }
}



// SegTree


const int inf = (int) 1e9 + 7;
struct node {
    node *left, *right;
    int l, r;
    int max_val;
    int add;

    static int allocated; static char* buf; void* operator new(size_t) { return buf + (allocated++ * sizeof(node));}
};

int node::allocated = 0;
char* node::buf = new char[(int) 1e8];


node* build(int l, int r){
    node* v = new node(); v->l = l; v->r = r; v->max_val = v->add = 0;
    if (l == r){
        v->left = v->right = nullptr;
        return v;
    }
    int m = (l + r) / 2;
    v->left = build(l, m);
    v->right = build(m + 1, r);
    return v;
}

int plus1(node* v, int l, int r, int val){
    if (l <= v-> l && v->r <= r){
        v->add += val;
        return v->max_val + v->add;
    }
    if (v->l > r || l > v->r){
        return v->max_val + v->add;
    }
    v->max_val = max(plus1(v->left, l, r, val), plus1(v->right, l, r, val));
    return v->max_val + v->add;
}

int get(node* v, int l, int r){
    if (l <= v-> l && v->r <= r){
        return v->max_val + v->add;
    }
    if (v->l > r || l > v->r){
        return -inf;
    }
    return max(get(v->left, l, r), get(v->right, l, r)) + v->add;
}


typedef int ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype cross(point a, point b) {
    return (conj(a) * b).y();
}

vector<point> hull, vecs;

void add_line(ftype k, ftype b) {
    point nw = {k, b};
    while(!vecs.empty() && dot(vecs.back(), nw - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
    }
    if(!hull.empty()) {
        vecs.push_back(1i * (nw - hull.back()));
    }
    hull.push_back(nw);
}

int get(ftype x) {
    point query = {x, 1};
    auto it = lower_bound(vecs.begin(), vecs.end(), query, [](point a, point b) {
        return cross(a, b) > 0;
    });
    return dot(query, hull[it - vecs.begin()]);
}




mt19937 rnd(2007);
namespace GeneralMatchingCheat {
    int n;
    vector<vector<int>> g;
    vector<int> mt;
    vector<bool> used;


    bool dfs(int v) {
        used[v] = true;
        shuffle(all(g[v]), rnd);
        for (auto u : g[v]) {
            if (mt[u] == -1) {
                mt[v] = u;
                mt[u] = v;
                return true;
            }
            int to = mt[u];
            mt[v] = u;
            mt[u] = v;
            mt[to] = -1;
            if (!used[to] && dfs(to)) {
                return true;
            } else {
                mt[v] = -1;
                mt[u] = to;
                mt[to] = u;
            }
        }
        return false;
    }

    vector<pair<int, int>> solve(int _n, vector<pair<int, int>> edges) {
        n = _n; g.assign(n, vector<int>(0));
        for (auto e : edges){
            g[e.first].push_back(e.second);
            g[e.second].push_back(e.first);
        }
        mt.assign(n, -1);
        forn (qwe, 50) {
            vector<int> a;
            forn (i, n) if (mt[i] == -1) a.push_back(i);
            if (len(a) == 0)
                break;
            shuffle(all(a), rnd);
            used.assign(n, false);
            for (auto i : a) {
                if (mt[i] == -1) {
                    dfs(i);
                }
            }
        }

        vector<pair<int, int>> ans;
        forn (i, n){
            if (mt[i] > i)
                ans.push_back({i, mt[i]});
        }
        return ans;
    }
}


vector<int> z_function (string s) {
    int n = (int) s.length();
    vector<int> z (n);
    for (int i=1, l=0, r=0; i<n; ++i) {
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            ++z[i];
        if (i+z[i]-1 > r)
            l = i,  r = i+z[i]-1;
    }
    return z;
}


vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}



vector<pt> convex_hull(vector<pt> pts) {
    vector<pt> res;
    sort(pts.begin(), pts.end(), [](pt a, pt b) -> bool { return a.x != b.x ? a.x < b.x : a.y < b.y; });
    pts.resize(unique(all(pts)) - pts.begin());
    sort(pts.begin() + 1, pts.end(), [&](pt a, pt b) -> bool {
        if (((a - pts[0]) % (b - pts[0])) != 0) return ((a - pts[0]) % (b - pts[0])) > 0;
        return (a - pts[0]).sz() < (b - pts[0]).sz();
    });
    for (pt u : pts) {
        while (len(res) >= 2 && ((u - res[len(res) - 2]) % (res[len(res) - 1] - res[len(res) - 2])) >= 0)
            res.pop_back();
        res.push_back(u);
    }
    return res;
}




bool try_kuhn (int v) {
    if (used[v])  return false;
    used[v] = true;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (mt[to] == -1 || try_kuhn (mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

for (int m=0; m<(1<<n); ++m)
    for (int s=m; s; s=(s-1)&m)


for (int k = 0; k < n; k++)
        for (int mask = 0; mask < (1 << n); mask++)
            if ((mask >> k) & 1)
                a[mask] += a[mask ^ (1 << k)];




// MinCost


using namespace std;
const int N = 401;
struct edge {
    int to, cap, val, rev;
};
vector<edge> G[N];
int d[N], flow[N], pre[N][2];
bool v[N];
queue<int> Q;
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, w, f;
        scanf("%d%d%d%d", &u, &v, &w, &f);
        G[u].push_back({ v, w, f, G[v].size() });
        G[v].push_back({ u, 0, -f, G[u].size() - 1 });
    }
    int ans0 = 0, ans1 = 0;
    for (;;) {
        for (int i = 1; i <= n; ++i) d[i] = 2147483647;
        memset(flow, -1, sizeof flow);
        memset(v, 0, sizeof v);
        d[1] = 0;
        flow[1] = 2147483647;
        v[1] = 1;
        Q.push(1);
        memset(pre, -1, sizeof pre);
        for (; !Q.empty();) {
            int x = Q.front();
            Q.pop();
            v[x] = 0;
            for (int i = 0; i < G[x].size(); ++i) {
                edge e = G[x][i];
                if (e.cap && d[x] + e.val < d[e.to]) {
                    d[e.to] = d[x] + e.val;
                    flow[e.to] = flow[x] < e.cap ? flow[x] : e.cap;
                    pre[e.to][0] = x;
                    pre[e.to][1] = i;
                    if (!v[e.to])
                        v[e.to] = 1, Q.push(e.to);
                }
            }
        }
        if (flow[n] == -1)
            break;
        ans0 += flow[n];
        ans1 += d[n] * flow[n];
        for (int i = n; pre[i][0] != -1; i = pre[i][0]) {
            G[pre[i][0]][pre[i][1]].cap -= flow[n];
            G[i][G[pre[i][0]][pre[i][1]].rev].cap += flow[n];
        }
    }
    printf("%d %d", ans0, ans1);


// Some useless geometry

struct pt {
    int x, y;
};

struct ang {
    int a, b;
};

bool operator < (const ang & p, const ang & q) {
    if (p.b == 0 && q.b == 0)
        return p.a < q.a;
    return p.a * 1ll * q.b < p.b * 1ll * q.a;
}

long long sq (pt & a, pt & b, pt & c) {
    return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
}

int main() {

    int n;
    cin >> n;
    vector<pt> p (n);
    int zero_id = 0;
    for (int i=0; i<n; ++i) {
        scanf ("%d%d", &p[i].x, &p[i].y);
        if (p[i].x < p[zero_id].x || p[i].x == p[zero_id].x && p[i].y < p[zero_id].y)
            zero_id = i;
    }
    pt zero = p[zero_id];
    rotate (p.begin(), p.begin()+zero_id, p.end());
    p.erase (p.begin());
    --n;

    vector<ang> a (n);
    for (int i=0; i<n; ++i) {
        a[i].a = p[i].y - zero.y;
        a[i].b = p[i].x - zero.x;
        if (a[i].a == 0)
            a[i].b = a[i].b < 0 ? -1 : 1;
    }

    for (;;) {
        pt q; // очередной запрос
        bool in = false;
        if (q.x >= zero.x)
            if (q.x == zero.x && q.y == zero.y)
                in = true;
            else {
                ang my = { q.y-zero.y, q.x-zero.x };
                if (my.a == 0)
                    my.b = my.b < 0 ? -1 : 1;
                vector<ang>::iterator it = upper_bound (a.begin(), a.end(), my);
                if (it == a.end() && my.a == a[n-1].a && my.b == a[n-1].b)
                    it = a.end()-1;
                if (it != a.end() && it != a.begin()) {
                    int p1 = int (it - a.begin());
                    if (sq (p[p1], p[p1-1], q) <= 0)
                        in = true;
                }
            }
        puts (in ? "INSIDE" : "OUTSIDE");
    }

}