#include <cstdio>

/***
 * Unsigned
 */

inline unsigned long long readULong()
{
  int c = getc(stdin);
  unsigned long long x = 0;
  while (c <= 32)
    c = getc(stdin);
  while ('0' <= c && c <= '9')
    x = x * 10 + c - '0', c = getc(stdin);
  return x;
}

inline unsigned int readUInt()
{
  int c = getc(stdin);
  unsigned int x = 0;
  while (c <= 32)
    c = getc(stdin);
  while ('0' <= c && c <= '9')
    x = x * 10 + c - '0', c = getc(stdin);
  return x;
}

inline void writeULong( unsigned long long x )
{
  char s[30];
  int n = 0;
  while (x || !n)
    s[n++] = '0' + x % 10, x /= 10;
  while (n--)
    putc(s[n], stdout);
}

inline void writeUInt( unsigned int x )
{
  char s[15];
  int n = 0;
  while (x || !n)
    s[n++] = '0' + x % 10, x /= 10;
  while (n--)
    putc(s[n], stdout);
}

/***
 * Signed
 */

inline int readInt()
{
  int s = 1, x = 0, c = getc(stdin);
  while (c <= 32)
    c = getc(stdin);
  if (c == '-')
    s = -1, c = getc(stdin);
  while ('0' <= c && c <= '9')
    x = x * 10 + c - '0', c = getc(stdin);
  return x * s;
}

inline void writeInt( int x )
{
  if (x < 0)
    putc('-', stdout), x = -x;

  char s[20];
  int n = 0;
  while (x || !n)
    s[n++] = '0' + x % 10, x /= 10;
  while (n--)
    putc(s[n], stdout);
}

/***
 * Word
 */

inline void readWord( char *s )
{
  int c = getc(stdin);
  while (c <= 32)
    c = getc(stdin);
  while (c > 32)
    *s++ = c, c = getc(stdin);
  *s = 0;
}

inline void writeWord( char *s )
{
  while (*s)
    putchar(*s++);
}