CXX = g++-15
CXXFLAGS = -std=c++17 -Wall -g -pedantic
TARGET = main
SRC = $(wildcard *.cc)
OBJ = $(patsubst %.cc,%.o,$(SRC))
INPUT = input.txt
ARCH := $(shell uname -m)
PYEXE = pypy3
PY_MAIN := $(shell [ -f main.py ] && echo main.py || ls *.py 2>/dev/null | head -n 1)

ifeq ($(ARCH),arm64)
	CXXFLAGS += -DAPPLE_SILICON
endif

ifeq ($(PYTHON),1)
# If PYTHON=1, dummy rule for $(TARGET) to avoid building
$(TARGET):
	@echo "Skipping compilation for Python mode."
else
$(TARGET): $(OBJ)
	$(CXX) $(CXXFLAGS) -o $@ $^

%.o: %.cc
	$(CXX) $(CXXFLAGS) -c $< -o $@
endif

all: $(TARGET)

run: all
	@if [ "$(PYTHON)" = "1" ]; then \
		$(PYEXE) $(PY_MAIN); \
	else \
		./$(TARGET); \
	fi

test: all
	@if [ "$(PYTHON)" = "1" ]; then \
		$(PYEXE) $(PY_MAIN) < $(INPUT); \
	else \
		./$(TARGET) < $(INPUT); \
	fi

clean:
	rm -f $(TARGET) $(OBJ)

.PHONY: all run test clean

#pragma GCC optimize("O3,unroll-loops")
#if !defined(__APPLE__)
#pragma GCC target("avx,avx2,sse")
#endif
#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j;i<k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define ll long long
// Make sure no overflow problems
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define mp make_pair
#define endl '\n'
#define x first
#define y second
#define VAR(i,n) __typeof(n) i = (n)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)
#define FORDEACH(i,c) for( VAR(i,(c).rbegin()),i!=(c).rend();i++)
#define REP(i,n) FOR(i,0,n)
#define ld long double
constexpr int INF = 1000000009;
constexpr long long INFLL = (ll)INF * (ll)INF;
constexpr ld EPS = 10e-9;
using namespace std;
// ##############################################################

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  // cheers!
}

const int MX = 1000;
int tp[MX][MX];

void update(int x, int y, int v) {
  for (; x < MX; x += x & -x)
    for (int yy = y; yy < MX; yy += yy & -yy) tp[x][yy] += v;
}

int query(int x, int y) {
  int res = 0;
  for (; x > 0; x -= x & -x)
    for (int yy = y; yy > 0; yy -= yy & -yy) res += tp[x][yy];
  return res;
}

#[allow(unused_imports)]
use std::cmp::{max, min};
use std::io::{BufWriter, Write, stdin, stdout};
use std::iter;
const INF: i64 = 1e9 + 7;

#[derive(Default)]
struct Scanner {
  buffer: Vec<String>,
}

impl Scanner {
  fn next<T: std::str::FromStr>(&mut self) -> T {
    loop {
      if let Some(token) = self.buffer.pop() {
        return token.parse().ok().expect("Failed to parse");
      }
      let mut input = String::new();
      stdin().read_line(&mut input).expect("Failed to read");
      self.buffer = input.split_whitespace().rev().map(String::from).collect();
    }
  }
}

fn main() {
  //cheers!
}

from sys import stdin, stdout, setrecursionlimit
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
setrecursionlimit(100000000)
inf = 100000009
eps = 1e-9

def rmalloc(size, fill=None):
  if len(size) == 0:
    return []
  if len(size) == 1:
    return [fill] * size[0]
  a, b = size[0], size[1:]
  return [rmalloc(b, fill) for _ in range(a)]

def malloc(*args):
  return rmalloc(args, None)

def fill(arr, element):
  try:
    for i in arr:
      fill(i, element)
  except:
    for i in range(len(arr)):
      arr[i] = element

def sizeof(arr):
  try:
    return tuple([len(arr)] + list(sizeof(arr[0])))
  except:
    return tuple()

if __name__ == "__main__":
  # cheers!