#include <stdio.h>
#include <stdarg.h>
#include <sys/time.h>

/* Input functions */
int getint() { int t; scanf("%d", &t); return t; }
int getch() { char t; scanf("%c", &t); return (int)t; }
float getfloat() { float t; scanf("%f", &t); return t; }

int getarray(int a[]) {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  return n;
}

int getfarray(float a[]) {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%f", &a[i]);
  return n;
}

/* Output functions */
void putint(int a) { printf("%d", a); }
void putch(int a) { printf("%c", (char)a); }
void putfloat(float a) { printf("%a", a); }

void putarray(int n, int a[]) {
  printf("%d:", n);
  for (int i = 0; i < n; i++) printf(" %d", a[i]);
  printf("\n");
}

void putfarray(int n, float a[]) {
  printf("%d:", n);
  for (int i = 0; i < n; i++) printf(" %a", a[i]);
  printf("\n");
}

/* Timing functions */
struct timeval _sysy_start, _sysy_end;
void starttime() { gettimeofday(&_sysy_start, NULL); }
void stoptime() {
  gettimeofday(&_sysy_end, NULL);
  int millis = (_sysy_end.tv_sec - _sysy_start.tv_sec) * 1000 +
               (_sysy_end.tv_usec - _sysy_start.tv_usec) / 1000;
  fprintf(stderr, "Timer: %d ms\n", millis);
}