// SysY 运行库实现：
// - 按实验/评测规范提供 I/O 等函数实现
// - 与编译器生成的目标代码链接，支撑运行时行为

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int getint() { int v; scanf("%d", &v); return v; }
int getch()  { return getchar(); }
void putint(int v) { printf("%d", v); }
void putch(int c)  { putchar(c); }
float getfloat() { float v; scanf("%f", &v); return v; }
void putfloat(float v) { printf("%a", v); }

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;
}
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");
}

static struct timespec _t0;
void starttime(int l) { (void)l; clock_gettime(CLOCK_MONOTONIC, &_t0); }
void stoptime(int l) {
  struct timespec t1; clock_gettime(CLOCK_MONOTONIC, &t1);
  fprintf(stderr, "Timer@%d: %ldms\n", l,
          (t1.tv_sec-_t0.tv_sec)*1000+(t1.tv_nsec-_t0.tv_nsec)/1000000);
}