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>
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline bool repr(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool repl(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  if (a < b) {
    while (a) {
      t = a;
      a = b % a;
      b = t;
    }
    return b;
  } else {
    while (b) {
      t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
struct Cg {
  __attribute__((always_inline)) inline char operator()() { return getchar(); }
};
struct Cp {
  __attribute__((always_inline)) inline void operator()(char x) { putchar(x); }
};
__attribute__((always_inline)) inline bool IS(char x) {
  return x == 10 || x == 13 || x == ' ';
}
template <typename T>
struct Fr {
  T P;
  __attribute__((always_inline)) inline Fr &operator,(int &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator int() {
    int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long long &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long long() {
    long long x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char &x) {
    for (x = P(); IS(x); x = P())
      ;
    return *this;
  }
  __attribute__((always_inline)) inline operator char() {
    char x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char *x) {
    char t = P();
    for (; IS(t); t = P())
      ;
    if (~t) {
      for (; !IS(t) && ~t; t = P()) *x++ = t;
    }
    *x++ = 0;
    return *this;
  }
  __attribute__((always_inline)) inline Fr &operator,(double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator double() {
    double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long double() {
    long double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned int &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned int() {
    unsigned int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned long long &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned long long() {
    unsigned long long x;
    *this, x;
    return x;
  }
};
Fr<Cg> in;
template <typename T>
struct Fw {
  T P;
  __attribute__((always_inline)) inline Fw &operator,(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
};
Fw<Cp> out;
const int N = 202;
int n, m, k, s[N][N];
bool e[N][N];
int pans;
int ds[N], dt[N], us[N], ut[N], cs[N][N], ct[N][N];
inline bool chk(int x, int y, int z) { return x >= z && x * k <= y; }
inline unsigned int rr() {
  static unsigned int S = 192608170;
  S ^= S << 13;
  S ^= S >> 17;
  S ^= S << 5;
  return S;
}
const int qm = 511;
int qb, qe, q[qm + 1];
bool vis[N * 2];
inline void add(int x) {
  if (!vis[x]) q[qe++ & qm] = x, vis[x] = 1;
}
inline void addfs(int x, int c) {
  if (!chk(cs[x][c], ds[x], us[x])) add(x);
}
inline void addft(int x, int c) {
  if (!chk(ct[x][c], dt[x], ut[x])) add(x + n);
}
int ni[N], mi[N], ki[N];
inline void shuffle(int *S, int n) {
  for (int i = 0, iend = 7; i < iend; i++)
    std::swap(S[rr() % n + 1], S[rr() % n + 1]);
}
inline void fixs(int x) {
  int l = us[x], r = us[x] + bool(ds[x] % k), i, j;
  shuffle(mi, m);
  for (int i_ = 1, i_end = m; i_ <= i_end; i_++)
    if (i = mi[i_], cs[x][s[x][i]] > r) {
      do j = rr() % k + 1;
      while (cs[x][j] >= r);
      cs[x][s[x][i]]--;
      cs[x][j]++;
      ct[i][s[x][i]]--;
      ct[i][j]++;
      addft(i, s[x][i]);
      addft(i, j);
      s[x][i] = j;
    }
  shuffle(ki, k);
  for (int i_ = 1, i_end = k; i_ <= i_end; i_++)
    for (i = ki[i_]; cs[x][i] < l;) {
      do j = rr() % m + 1;
      while (cs[x][s[x][j]] <= l);
      cs[x][s[x][j]]--;
      cs[x][i]++;
      ct[j][s[x][j]]--;
      ct[j][i]++;
      addft(j, s[x][j]);
      addft(j, i);
      s[x][j] = i;
    }
}
inline void fixt(int x) {
  int l = ut[x], r = ut[x] + bool(dt[x] % k), i, j;
  shuffle(ni, n);
  for (int i_ = 1, i_end = n; i_ <= i_end; i_++)
    if (i = ni[i_], ct[x][s[i][x]] > r) {
      do j = rr() % k + 1;
      while (ct[x][j] >= r);
      ct[x][s[i][x]]--;
      ct[x][j]++;
      cs[i][s[i][x]]--;
      cs[i][j]++;
      addfs(i, s[i][x]);
      addfs(i, j);
      s[i][x] = j;
    }
  shuffle(ki, k);
  for (int i_ = 1, i_end = k; i_ <= i_end; i_++)
    for (i = ki[i_]; ct[x][i] < l;) {
      do j = rr() % n + 1;
      while (ct[x][s[j][x]] <= l);
      ct[x][s[j][x]]--;
      ct[x][i]++;
      cs[j][s[j][x]]--;
      cs[j][i]++;
      addfs(j, s[j][x]);
      addfs(j, i);
      s[j][x] = i;
    }
}
void Modify(int x, int y) {
  ds[x]++, dt[y]++;
  int u = ds[x] % k;
  if (u == 0)
    pans--, us[x]++;
  else if (u == 1)
    pans++;
  u = dt[y] % k;
  if (u == 0)
    pans--, ut[y]++;
  else if (u == 1)
    pans++;
  e[x][y] = 1;
  for (int i = 1, iend = k; i <= iend; i++)
    if (chk(cs[x][i] + 1, ds[x], us[x]) && chk(ct[y][i] + 1, dt[y], ut[y])) {
      s[x][y] = i;
      cs[x][i]++, ct[y][i]++;
      return;
    }
  int gg = rr() % k + 1;
  s[x][y] = gg, cs[x][gg]++, ct[y][gg]++;
  qb = qe = 0;
  if (!chk(cs[x][s[x][y]], ds[x], us[x])) add(x);
  if (!chk(ct[y][s[x][y]], dt[y], ut[y])) add(y + n);
  while (qb < qe) {
    int x = q[qb++ & qm];
    if (x <= n)
      fixs(x);
    else
      fixt(x - n);
    vis[x] = 0;
  }
}
int main() {
  int q;
  in, n, m, q, k;
  if (k == 1) {
    out, 0, '\n';
    for (int i = 1, iend = q; i <= iend; i++) out, 1, ' ';
    out, '\n';
    return 0;
  }
  for (int i = 1, iend = n; i <= iend; i++) ni[i] = i;
  for (int i = 1, iend = m; i <= iend; i++) mi[i] = i;
  for (int i = 1, iend = k; i <= iend; i++) ki[i] = i;
  std::vector<std::pair<int, int> > e;
  for (int i = 1, iend = q; i <= iend; i++) {
    int x, y;
    in, x, y;
    Modify(x, y);
    e.push_back(std::make_pair(x, y));
  }
  out, pans, '\n';
  for (__typeof((e).end()) i = (e).begin(); i != (e).end(); ++i)
    out, s[i->first][i->second], ' ';
  out, '\n';
}