Problem: There is a developed network of flights between Berland and Beerland. All of them belong to the Berland state company BerAvia. Each flight connects some Berland city with some Beerland city. For each flight airplanes fly in both directions.

Changes are coming to Berland — the state decided to privatize BerAvia, namely, to sell out all flights to t private companies. Each of these companies wants to get the maximal number of flights, so if the Berland flights are sold unevenly, Berland can be accused of partiality. Berland Government decided to sell the flights as evenly as possible between the t companies.

The unevenness of the distribution of flights between companies is calculated as follows. For each city i (both Berland and Beerland) we'll calculate the value of 

<image> where aij is the number of flights from city i, which belong to company j. The sum of wi for all cities in both countries is called the unevenness of the distribution. The distribution with the minimal unevenness is the most even one.

Help the Berland government come up with the most even distribution plan of selling flights.

Input

The first input line contains four integers n, m, k and t (1 ≤ n, m, t ≤ 200;1 ≤ k ≤ 5000), where n, m are the numbers of cities in Berland and Beerland, correspondingly, k is the number of flights between them, and t is the number of private companies. Next k lines describe the flights, one per line, as pairs of positive integers xi, yi (1 ≤ xi ≤ n;1 ≤ yi ≤ m), where xi and yi are the indexes of cities in Berland and Beerland, correspondingly, connected by the i-th flight. There is at most one flight between any pair of cities, each flight connects cities of different countries. The cities in Berland are indexed from 1 to n, and in Beerland — from 1 to m.

Output

Print the unevenness of the sought plan on the first line. On the second line print a sequence of k integers c1, c2, ..., ck (1 ≤ ci ≤ t), where ci is the index of the company that should buy the i-th flight. Assume that the flights are indexed from 1 to k in the order they appear in the input. If there are multiple solutions, print any of them.

Examples

Input

3 5 8 2
1 4
1 3
3 3
1 2
1 1
2 1
1 5
2 2


Output

4
2 1 2 1 2 1 2 2 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
template <int SZ>
struct Dinic {
  typedef long long F;
  struct Edge {
    int to, rev;
    F flow, cap;
  };
  int N, second, t;
  vector<Edge> adj[SZ];
  typename vector<Edge>::iterator cur[SZ];
  void addEdge(int u, int v, F cap) {
    assert(cap >= 0);
    Edge a{v, (int)adj[v].size(), 0, cap}, b{u, (int)adj[u].size(), 0, 0};
    adj[u].push_back(a), adj[v].push_back(b);
  }
  int level[SZ];
  bool bfs() {
    for (int i = (0); i < (N); ++i) level[i] = -1, cur[i] = begin(adj[i]);
    queue<int> q({second});
    level[second] = 0;
    while ((int)q.size()) {
      int u = q.front();
      q.pop();
      for (auto& e : adj[u])
        if (level[e.to] < 0 && e.flow < e.cap)
          q.push(e.to), level[e.to] = level[u] + 1;
    }
    return level[t] >= 0;
  }
  F sendFlow(int v, F flow) {
    if (v == t) return flow;
    for (; cur[v] != end(adj[v]); cur[v]++) {
      Edge& e = *cur[v];
      if (level[e.to] != level[v] + 1 || e.flow == e.cap) continue;
      auto df = sendFlow(e.to, min(flow, e.cap - e.flow));
      if (df) {
        e.flow += df;
        adj[e.to][e.rev].flow -= df;
        return df;
      }
    }
    return 0;
  }
  F maxFlow(int _N, int _s, int _t) {
    N = _N, second = _s, t = _t;
    if (second == t) return -1;
    F tot = 0;
    while (bfs())
      while (auto df = sendFlow(second, numeric_limits<F>::max())) tot += df;
    return tot;
  }
};
Dinic<405> D;
int n, m, k, t, tot;
bool adj[201][201];
int ldeg[201], rdeg[201], ans[201][201];
int ret = 0;
void ae(int x, int y, int l, int r, bool flag) {
  if (flag) ret += r - l;
  D.addEdge(n + m + 1, y, r);
  D.addEdge(y, x, r - l);
  D.addEdge(x, n + m + 2, r);
  tot += r;
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  re(n, m, k, t);
  vector<pair<int, int> > ed;
  for (int i = (0); i < (k); ++i) {
    int x, y;
    re(x, y);
    ed.push_back({x, y});
    adj[x][y] = 1;
  }
  for (int i = (0); i < (t); ++i) {
    D = Dinic<405>();
    tot = 0;
    for (int a = (1); a < (n + 1); ++a) ldeg[a] = 0;
    for (int b = (1); b < (m + 1); ++b) rdeg[b] = 0;
    for (int a = (1); a < (n + 1); ++a)
      for (int b = (1); b < (m + 1); ++b)
        if (adj[a][b]) {
          ldeg[a]++, rdeg[b]++;
          D.addEdge(a, n + b, 1);
        }
    for (int a = (1); a < (n + 1); ++a)
      ae(0, a, ldeg[a] / (t - i), (ldeg[a] + t - i - 1) / (t - i), i == 0);
    for (int b = (1); b < (m + 1); ++b)
      ae(n + b, 0, rdeg[b] / (t - i), (rdeg[b] + t - i - 1) / (t - i), i == 0);
    assert(D.maxFlow(n + m + 3, n + m + 1, n + m + 2) == tot);
    for (int a = (1); a < (n + 1); ++a)
      for (auto& t : D.adj[a])
        if (n + 1 <= t.to && t.to <= n + m && t.flow) {
          adj[a][t.to - n] = 0;
          ans[a][t.to - n] = i + 1;
        }
  }
  ps(ret);
  for (auto& t : ed) pr(ans[t.first][t.second], ' ');
}