akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>

#include <algorithm>

using namespace std;

#define NMAX 600
#define BMAX (NMAX * 3 + 6)

typedef long long i64;

static int n, m;
static char map[NMAX + 10][NMAX + 10];
static int pre[3 * NMAX + 10][3 * NMAX + 10];

#define S(i, j) pre[NMAX + (i)][NMAX + (j)]


void show() {
    for (int i = 1; i <= n; i++)
        printf("%s\n", map[i] + 1);
    puts("");
}

void rotate() {
    static char buf[NMAX + 10][NMAX + 10];
    memcpy(buf, map, sizeof(buf));
    memset(map, 0, sizeof(map));
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++)
        map[i][j] = buf[n - j + 1][i];
    swap(n, m);
    // show();
}

i64 eval() {
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        S(i, j) = map[i][j] == '#';
    for (int i = 0; i <= BMAX; i++) for (int j = 1; i >= j; j++)
        pre[i - j][j] += pre[i - j + 1][j - 1];

    i64 r = 0;
    for (int i = 1; i <= n + m; i++)
        for (int j = 0; i - j >= 1; j++) if (map[i - j][j + 1] == '#')
        for (int k = j + 1; i - k >= 1; k++) if (map[i - k][k + 1] == '#') {
            int d = (k - j) << 1;
            r += S(i - j - d, j + 1) - S(i - k, k - d + 1);
        }
    return r;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", map[i] + 1);

    i64 ans = eval();
    rotate();
    ans += eval();
    rotate();
    ans += eval();
    rotate();
    ans += eval();
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 13824
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
int main(){
  int n;
  ll ans = 0;
  cin>>n;
  vector<ll> a(n);
  for(int i=0; i<n; i++){
    cin>>a.at(i);
    ans = ans^a.at(i);
  }
  for(int i=0; i<n; i++){
    cout<<(ans^a.at(i))<<" ";
  }
  cout<<endl;
//    cout << fixed << setprecision(10);
}


Measured memory_bytes: 4772
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

inline int read() {
  int f = 1;
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    f = (ch == '-') ? -1 : 1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}

const int N = 1e6 + 5;
const int P = 1e9 + 7;

inline int mul(int a, int b) {
  return (long long) a * b % P;
}
inline int sub(int a, int b) {
  return a - b < 0 ? a - b + P : a - b;
}
inline int add(int a, int b) {
  return a + b >= P ? a + b - P : a + b;
}
inline int modexp(int a, int x) {
  int ret = 1;
  while (x) {
    if (x & 1) {
      ret = mul(ret, a);
    }
    a = mul(a, a);
    x >>= 1;
  }
  return ret;
}

int n;
int fac[N];
int inv[N];

inline int calc(int m, int n) {
  int k = 2 * m - n;
  if (k >= 0 && m - k >= 0) {
    return mul(fac[m], mul(inv[k], inv[m - k]));
  } else {
    return 0;
  }
}

inline int C(int n, int m) {
  if (n < 0 || m < 0 || n < m) {
    return 0;
  }
  return mul(fac[n], mul(inv[m], inv[n - m]));
}

int main() {
  n = read();
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = mul(fac[i - 1], i);
  }
  inv[n] = modexp(fac[n], P - 2);
  for (int i = n - 1; i >= 0; --i) {
    inv[i] = mul(inv[i + 1], i + 1);
  }
  int ans = mul(fac[n - 1], n);
  for (int i = (n + 1) / 2; i < n; ++i) {
    ans = sub(ans, mul(fac[n - i - 1], mul(C(i - 1, n - i - 1), fac[i])));
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <stdio.h>
typedef long long ll;
using namespace std;

int main(void){
    int N, K;
    cin >> N >> K;
    ll sum = 0;
    vector<ll> H;
    ll tmp;
    for(int i = 0; i < N; i++) {
        cin >>tmp;
        sum +=tmp;
        H.push_back(tmp);
    }
    
    if(K >= N) {
        cout << 0 << endl;
        return 0;
    }
    
    if(K==0) {
        cout << sum << endl;
        return 0;
    }
    
    sort(H.begin(), H.end(), greater<ll>());
    
    ll ans = 0;
    for(int i = 0; i < N; i++){
        if(i <= K-1) continue;
        else {
            ans += H[i];
        }
    }
    
    cout << ans << endl;
    
    
}


Measured memory_bytes: 2420
#include<stdio.h>
#include<stdlib.h>

typedef long long int int64;

void run(void){
  int n;
  scanf("%d",&n);
  int *a=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  const int mod=1000000007;
  int *inv=(int *)malloc(sizeof(int)*(n+1));
  int *invSum=(int *)malloc(sizeof(int)*(n+1));
  int fact=1;
  inv[1]=invSum[1]=1;
  for(i=2;i<=n;i++){
    inv[i]=mod-(int64)(mod/i)*inv[mod%i]%mod;
    invSum[i]=(inv[i]+invSum[i-1])%mod;
    fact=(int64)fact*i%mod;
  }
  int ans=0;
  for(i=0;i<n;i++) ans=(ans+(int64)a[i]*(invSum[n-i]+invSum[i+1]-1))%mod;
  ans=(int64)ans*fact%mod;
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>
int a[1111],b[1111],c[1111],d[1111],p[1111],i,j,x,y,z;
main(){
  for(;scanf("%d%d%d",a,b,c)&&(*a+=*b+*c);){
    for(i=0,scanf("%d",p);i++<*p;scanf("%d%d%d%d",a+i,b+i,c+i,d+i),p[i]=2);
    for(;--i;)
      for(j=0;j++<*p;d[j]?p[a[j]]=p[b[j]]=p[c[j]]=1:(x=p[a[j]]&1)&(y=p[b[j]]&1)?p[c[j]]=0:x&(z=p[c[j]])?p[b[j]]=0:y&z?p[a[j]]=0:0);
    for(;i<*a;printf("%d\n",p[++i]));
  }return 0;
}

Measured memory_bytes: 620
#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

#define COMBI_SIZE 3750

int combi[COMBI_SIZE][5];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

void precalc() {
    int s = 0;
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            if (j == i) continue;
            for (int k = 1; k <= 6; k++) {
                if (k == j) continue;
                for (int l = 1; l <= 6; l++) {
                    if (l == k) continue;
                    for (int m = 1; m <= 6; m++) {
                        if (m == l) continue;
                        combi[s][0] = i;
                        combi[s][1] = j;
                        combi[s][2] = k;
                        combi[s][3] = l;
                        combi[s][4] = m;
                        s++;
                    }
                }
            }
        }
    }
}

int h, w;

void update(int tile[][8], int base, int color, int x, int y) {
    tile[y][x] = color;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
            continue;
        }
        if (tile[ny][nx] == base) {
            update(tile, base, color, nx, ny);
        }
    }
}

void count(int tile[][8], int color, int x, int y, int *cnt) {
    (*cnt)++;
    tile[y][x] = -1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
            continue;
        }
        if (tile[ny][nx] == color) {
            count(tile, color, nx, ny, cnt);
        }
    }
}

int simulation(int s, int tile[][8]) {
    int temp[8][8];
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            temp[i][j] = tile[i][j];
        }
    }
    for (int i = 0; i < 5; i++) {
        update(temp, temp[0][0], combi[s][i], 0, 0);
    }
    
    int cnt = 0;
    count(temp, combi[s][4], 0, 0, &cnt);
    return cnt;
}

int main() {
    precalc();

    while (1) {
        int c;
        int tile[8][8];
        cin >> h >> w >> c;
        if (h == 0) {
            break;
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> tile[i][j];
            }
        }

        int maxv = 0;
        for (int i = 0; i < COMBI_SIZE; i++) {
            if (combi[i][0] == tile[0][0] || combi[i][4] != c) {
                continue;
            }
            maxv = max(maxv, simulation(i, tile));
        }
        cout << maxv << endl;
    }

    return 0;
}

Measured memory_bytes: 1232
import sys

def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    return sum(w for (w, _, _), _ in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n-1)))

V, E = map(int, input().split())
edges = [(w, s, t) for s, t, w in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))


Measured memory_bytes: 24012
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  V<> a(n);
  iota(begin(a), end(a), 0);
  for (int i = 0; i < m; ++i) {
    int x, y;
    char _;
    cin >> x >> _ >> y, --x, --y;
    swap(a[x], a[y]);
  }
  for (int i = 0; i < n; ++i) {
    cout << a[i] + 1 << '\n';
  }
}


Measured memory_bytes: 3032
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    ab = [list(map(int, input().split())) for i in range(n - 1)]
    # ab = sorted(ab, key=lambda x: x[1])
    # ab = sorted(ab, key=lambda x: x[0])
    e = [[] for i in range(n + 1)]
    ansl = {}
    for i in range(n-1):
        a, b = ab[i]
        e[a].append(b)
        ansl[(a,b)] = 0

    d = defaultdict(int)
    for i in range(n-1):
        a, b = ab[i]
        d[a] += 1
        d[b] += 1
    ans = 0
    for i in d.keys():
        ans = max(ans, d[i])
    print(ans)

    #ansl = 
    #ansl = [0 for i in range(n+1)]
    col = [-1 for i in range(n+1)]
    def f(v, c):
        col[v] = 1
        t = 1
        for i in e[v]:
            if col[i] == -1:
                if t == c:
                    t+=1
                ansl[(v,i)] = t
                #ansl[i] = t
                f(i, t)
                t+=1
    f(1,0)
    #print(*ansl)
    # for i in range(2,len(ansl)):
    #     print(ansl[i])
    for i in range(n - 1):
        a, b = ab[i]
        print(ansl[(a,b)])



    

    

    


if __name__ == '__main__':
    main()


Measured memory_bytes: 159572
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll N,Y;
  cin>>N>>Y;
  for(ll i=0;i<=N;i++){
    for(ll j=0;j<=N;j++){
      if(i+j<=N){
        ll k=N-i-j;
        if(10000*i+5000*j+1000*k==Y){cout<<i<<" "<<j<<" "<<k<<endl;return 0;}
      }
    }
  }
  cout<<"-1 -1 -1"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

const int MOD=998244353;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	double L;cin>>L;
	printf("%.12lf\n",L*L*L/27);
}

Measured memory_bytes: 256
//
// Created by yutaka on 19/05/24.
//
#include <iostream>

using namespace std;

int main()
{
    int N;
    int K;

    cin >> N >> K;

    double sum = 0.0;
    for(int i=1; i<=N; ++i)
    {
        double tmp = 1.0/N;
        int now = i;
        while(now < K)
        {
            tmp *= 0.5;
            now *= 2;
        }
        sum += tmp;
    }

    printf("%.12f\n", sum);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iomanip>

#include <map>
#include <set>
#include <queue>
#include <stack>

#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdbl vector<double>
#define vstr vector<string>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	ll a[n];
	rep(i,n) cin >> a[i];

	//plus when even
	ll ans_plus = 0;
	ll sum = 0;
	rep(i,n){
		sum += a[i];
		if(i % 2 == 0){
			if(sum <= 0) {
				ans_plus += 1 - sum;
				sum += 1 - sum;
			}
		}else{
			if(sum >= 0){
				ans_plus += sum + 1;
				sum -= sum + 1;
			}
		}
	}

	//minus when even
	ll ans_minus = 0;
	sum = 0;
	rep(i,n){
		sum += a[i];
		if(i % 2 == 1){
			if(sum <= 0) {
				ans_minus += 1 - sum;
				sum += 1 - sum;
			}
		}else{
			if(sum >= 0){
				ans_minus += sum + 1;
				sum -= sum + 1;
			}
		}
	}

	cout << min(ans_plus,ans_minus) << endl;	
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int x, y, z;
	cin >> x >> y >> z;

	swap(x, y);
	swap(x, z);

	cout << x << " " << y << " " << z << "\n";
}


Measured memory_bytes: 384
#include <cstdio>
#include <algorithm>

int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main()
{
	int k;
	scanf("%d", &k);
	printf("%d\n", a[k - 1]);
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,a[100100],dp[100][10];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1),reverse(a+1,a+n+1);
	for(int i=1;i<=n;++i)if(i+1>a[i+1]){
		int ans=1;
		for(int j=i+1;a[j]==i;j++)ans^=1;
		ans&=(a[i]-i+1)&1;
		if(!ans)puts("First");
		else puts("Second");
		break;
	}
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    if(n%1000)
        cout<<1000-(n%1000);
    else
        cout<<0;
    return 0;
}


Measured memory_bytes: 3552
# C - Remainder Minimization 2019
import numpy as np

l, r = map(int, input().split())

ans = 2019
for i in range(l,r):
    for j in range(i+1, r+1):
        ans = min(ans, (i*j)%2019)
        if ans==0:
            break
    else:
        continue
    break

print(ans)

Measured memory_bytes: 12468
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    cout << N + N * N  + N *  N * N  << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;

struct hand {
  int ib;
  int jb;
  int ia;
  int ja;
};

int main() {
  int h, w;
  cin >> h >> w;
  h++;
  w++;
  int g[h][w];
  for ( int i = 1; i < h; i++ ) {
    for ( int j = 1; j < w; j++ ) {
      cin >> g[i][j];
    }
  }

  vector<hand> me;
  for ( int i = 1; i < h; i++ ) {
    if ( i%2 == 1 ) {
      for ( int j = 1; j < w; j++ ) {
        if ( i == h-1 && j == w-1 ) { break; }
        if ( g[i][j]%2 == 1 ) {
          hand t;
          t.ib = i;
          t.jb = j;
          if ( j != w-1 ) {
            t.ia = i;
            t.ja = j+1;
          } else {
            t.ia = i+1;
            t.ja = j;
          }
          g[t.ia][t.ja]++;
          me.push_back(t);
        }
      }
    } else {
      for ( int j = w-1; j >= 1; j-- ) {
        if ( i == h-1 && j == 1 ) { break; }
        if ( g[i][j]%2 == 1 ) {
          hand t;
          t.ib = i;
          t.jb = j;
          if ( j != 1 ) {
            t.ia = i;
            t.ja = j-1;
          } else {
            t.ia = i+1;
            t.ja = j;
          }
          g[t.ia][t.ja]++;
          me.push_back(t);
        }
      }
    }
  }

  cout << me.size() << endl;
  for ( int i = 0; i < me.size(); i++ ) {
    cout << me[i].ib << ' ' << me[i].jb << ' ' << me[i].ia << ' ' << me[i].ja << endl;
  }
  return 0;
}


Measured memory_bytes: 5232
#include <bits/stdc++.h>
using namespace std;
#define int long long
using P = pair<int, int>;
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
constexpr int INF = 1234567890;
constexpr int MOD = 1000000000 + 7;
// constexpr int MOD = 998244353;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int fact(int n) { return n > 1 ? n * fact(n - 1) % MOD : 1; }
int modinv(int a)
{
    int b = MOD, u = 1, v = 0;
    while (b)
    {
        int t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= MOD;
    if (u < 0)
        u += MOD;
    return u;
}
constexpr int modpow(int a, int n)
{
    int rtn = 1;
    while (n > 0)
    {
        if (n & 1)
            rtn = rtn * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return rtn;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(10);

    int m1, d1, m2, d2;
    cin >> m1 >> d1 >> m2 >> d2;
    cout << (m1 != m2 ? 1 : 0) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 998244353
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
int cnt[114514];
int ka[214514],inv[214514];
void setkaijo(int n){
	ka[0]=1;
	for(int i=1;i<=n;i++){
		ka[i] = ka[i-1] * i;
		ka[i] %= inf;
	}
}
int modpow(int x,int k){
	// x ^ k mod inf
	int res = 1;
	while(k>0){
		if(k%2)res = (res*x)%inf;
		x = (x*x)%inf;
		k >>=1;
	}
	return res;
}
void setinv(int n){
	for(int i=0;i<=n;i++){
		inv[i] = modpow(ka[i],(ll)inf-2);
	}
}
int comb(int n,int k){
	if( k<0 || n<0 || k>n)return 0;
	if(k==0 || k==n)return 1;
	int res = (ka[n] * inv[k]) % inf;
	res = (res*inv[n-k]) % inf;
	return res;
}
signed main(){
	int n;
	cin>>n;
	setkaijo(210000);
	setinv(210000);
	int ans = 1;
	vector<int> a;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		a.pb(x);
		cnt[x]++;
	}
	if( a[0] != 0 ){
		cout<<0<<endl;
		return 0;
	}
	if( cnt[0] > 1 ){
		cout<<0<<endl;
		return 0;
	}
	sort(a.begin(), a.end());
	int ma = a[a.size()-1];
	for(int i=1;i<=ma;i++){
		ans *= modpow( cnt[i-1],cnt[i] );
		ans %= inf;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5496
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>
#include <bitset>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main()
{
    string S;
    cin >> S;

    bool ok = true;

    for (int i = 0; i < S.size(); i++) {
        if (i % 2 == 1) {
            ok = ok && !(S[i] == 'R');
        } else {
            ok = ok && !(S[i] == 'L');
        }
    }

    if (ok) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
int main(int argc, char const *argv[]) {
    int K;
    std::cin >> K;
    if (K % 2 == 0) {
        std::cout << K * K / 4 << '\n';
    } else {
        std::cout << K / 2 * (K / 2 + 1) << '\n';
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    long long arr[n+1];
    arr[0]=2;arr[1]=1;
    for(int i=2;i<=n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    cout<<arr[n];

    return 0;
   }

Measured memory_bytes: 3604
#include <stdio.h>
#include <string.h>

int main(){
    char    s[11] = {0};
    char    t[11] = {0};
    char    u[11] = {0};
    int     n, a, b;

    scanf("%s %s", s, t);
    scanf("%d %d", &a, &b);
    scanf("%s", u);

    if( strcmp(s, u)==0 ){
        printf("%d %d\n", a-1, b);
    }
    else if( strcmp(t, u)==0 ){
        printf("%d %d\n", a, b-1);
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll N;
ll T[1001],A[1001];
int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> T[i] >> A[i];
	}

	ll Tp=1, Ap=1;
	ll n = 1;//比と最小値の倍率
	for(int i=0;i<N;i++){
		ll tmpT = Tp/T[i];ll tmpA = Ap/A[i];
		if(Tp%T[i] != 0){
			tmpT ++;
		}
		if(Ap%A[i] != 0){
			tmpA ++;
		}
		n = max(tmpT,tmpA);
		Tp = T[i]*n;Ap = A[i]*n;
	}
	cout << Tp + Ap << endl;
	// int ans=T[0]*double + A[0]*double;
	// for(int i=1;i<N;i++){
	// 	if(T[i]>T[i-1] && A[i]>A[i-1]) {
	// 		Tp +=T[i] - T[i-1];
	// 		Ap +=A[i] - A[i-1];
	// 		ans=Tp*double + Ap*double;
	// 	}
	// 	//even case
	// 	else if(T[i] == 1 && A[i] == 1){
	// 		Tp = max(Tp,Ap);Ap = max(Tp,Ap);
	// 		ans = Ap * 2;
	// 	}else if()
	// }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(src,dst)    for(int i=src; i<dst;  i++)
#define rep2(src,dst)   for(int j=src; j<dst;  j++)
#define INF 1000000000000 //1e+12
#define MOD 10000007 //1e9+7
#define PI  acos(-1)
#define ll long long
template<typename T> inline void ChMin(T* a, T* b) {if(*a>*b) *a=*b;}
template<typename T> inline void ChMax(T* a, T* b) {if(*a<*b) *a=*b;}
template<typename T> inline int  DivUp(T a, T b)   {return ((a+b-1)/b);}

int main(){
    int n;       cin >> n;
    string s, t, ans; cin >> s >> t;

    rep(0,n){
        ans += s[i];
        ans += t[i];
    }
    cout << ans << endl;
    return 0;
}
/*

*/


Measured memory_bytes: 3548
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
vector<ll> v;
void dfs(int k, ll x){
	v.push_back(x);
	if(k>=9) return;
	int a=x%10;
	if(a){
		dfs(k+1, x*10+a-1);
	}
	dfs(k+1, x*10+a);
	if(a<9){
		dfs(k+1, x*10+a+1);
	}
}
int main()
{
	for(int i=1; i<=9; i++) dfs(0, i);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int k; cin>>k;
	//rep(i,1000)cout<<v[i]<<endl;
  cout<<v[k-1]<<endl;

	return 0;
}

Measured memory_bytes: 2420
#include <iostream>
using namespace std;

int main() {
	int S, h, m, s;
	cin >> S;

	h = S / 3600;
	m = (S - h * 3600)/60;
	s = S % 60;
	cout << h << ":" << m << ":" << s << endl;

	return 0;
}


Measured memory_bytes: 3100
#include<stdio.h>
#include<stdlib.h>


int main(void){
    int n,i,count=0;
    int p[50];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&p[i]);
    }
    for(i=1;i<n-1;i++){
        if((p[i-1]<p[i] && p[i]<p[i+1]) || (p[i-1]>p[i] && p[i]>p[i+1])){
            count += 1;
        }
    }
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.immutable._
import scala.io.StdIn.readLine

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}

object Main {
  def solve(sc: => Scanner): Unit = {
    val N, X = sc.nextInt
    val A = Array.fill(N)(sc.nextInt)
    println(A.size + (X - A.sum) / A.min)
  }

  def gcd(i: Long, j: Long): Long = {
    if (i < j) (gcd(j, i)) else (if (j == 0) (i) else (gcd(j, i % j)))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

Measured memory_bytes: 27476
#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;

int distance(pii a, pii b)
{
	return abs(a.fi-b.fi)+abs(a.se-b.se);
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;

	vector<pii> students(n), checkpoints(m);

	for(int i = 0; i < n; i++)
		cin >> students[i].fi >> students[i].se;

	for(int i = 0; i < m; i++)
		cin >> checkpoints[i].fi >> checkpoints[i].se;

	for(int i = 0; i < n; i++)
	{
		int mn = INT_MAX, index = INT_MAX;
		for(int j = 0; j < m; j++)
		{
			int aux = distance(students[i], checkpoints[j]);
			if(aux < mn)
			{
				index = j;
				mn = aux;
			}
		}

		cout << index+1 << endl;
	}
	return 0;	
}

Measured memory_bytes: 256
n, k, s = map(int, input().split())
n_new = n
res = 0

if n - k + 1 > s:
    n_new = s + k -1
    res = n - n_new
else:
    pass

# print(res)
# print(n_new)

ones = n_new - k
big = s - ones

kijun = [big]

for _ in range(ones):
    kijun.append(1)

ans = []
hanpuku = -(- n_new // len(kijun))
for i in range(hanpuku):
    for x in kijun:
        ans.append(str(x))

for i in range(len(ans)-n_new):
    ans.pop(-1)

for j in range(res):
    ans.append(str(s+1))

# print(kijun)
print(' '.join(ans))

Measured memory_bytes: 16172
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<cctype>
#include<stack>
#define ld long double
#define ll long long int
#define ull unsigned long long int
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long INF=1LL<<60;
//set<int>::iterator it;

static const int MAX = 200000;

int main(void){
  int h,a;
  cin>>h>>a;
  int ans;
  ans = h/a;
  if(h % a == 0)
    cout<<h/a<<endl;
  else
  {
    cout<<h/a+1<<endl;
  }
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int a[MAXN], n;
int v[MAXN][3];

int c[MAXN];
inline int lowbit(int i)
{ return i&(-i); }
inline void modify(int pos, int dt)
{
	for (; pos <= n; pos += lowbit(pos))
		c[pos] += dt;
}
inline int query(int pos)
{
	int ans = 0;
	for (; pos; pos -= lowbit(pos))
		ans += c[pos];
	return ans;
}
inline int query(int x, int y)
{ return query(y)-query(x-1); }

int d[MAXN], cnt[MAXN];

void solve()
{
	for (int j = 1; j <= n; j += 2) {
		cnt[j] = query(abs(a[j])+1, n);
		d[(abs(a[j])+1)>>1] ^= 1;
		modify(abs(a[j]), 1);
	}
	memset(c, 0, sizeof c);
	for (int j = (n&1)?n:n-1; j >= 1; j -= 2) {
		int c = query(abs(a[j])-1);
		d[((j+1)>>1)+c] ^= 1;
		if ((c+cnt[j])&1) a[j] = -a[j];
		modify(abs(a[j]), 1);
	}
	for (int j = 1; j <= n; j++) d[j] ^= d[j-1];
	for (int j = 2; j <= n; j += 2)
		if (d[j>>1])
			a[j] = -a[j];
	memset(c, 0, sizeof c), memset(d, 0, sizeof d), memset(cnt, 0, sizeof cnt);
	for (int j = 2; j <= n; j += 2) {
		cnt[j] = query(abs(a[j])+1, n);
		d[(abs(a[j])>>1)+1] ^= 1;
		modify(abs(a[j]), 1);
	}
	memset(c, 0, sizeof c);
	for (int j = (n&1)?n-1:n; j >= 1; j -= 2) {
		int c = query(abs(a[j])-1);
		d[(j>>1)+c+1] ^= 1;
		modify(abs(a[j]), 1);
		if ((c+cnt[j])&1) a[j] = -a[j];
	}
	for (int j = 1; j <= n; j++) d[j] ^= d[j-1];
	for (int j = 1; j <= n; j += 2)
		if (d[(abs(a[j])+1)>>1])
			a[j] = -a[j];
	int odd = 0, even = 0;
	for (int j = 1; j <= n; j += 2)
		odd ^= (a[j] < 0);
	for (int j = 2; j <= n; j += 2)
		even ^= (a[j] < 0);
	if ((odd&1) || (even&1)) puts("No");
	else puts("Yes");
}

inline int judge(int a[3])
{
	int small = min(a[0], a[2]), big = max(a[0], a[2]);
	if (a[1]-small != 1 || big-a[1] != 1 || small%3 != 1) return 0;
	return (small/3+1)*(a[0]==small?1:-1);
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < 3; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &v[j][i]);
	for (int j = 1; j <= n; j++) {
	        a[j] = judge(v[j]);
		if (a[j] == 0) {
			puts("No");
			return 0;
		}
		if ((abs(a[j])^j)&1) {
			puts("No");
			return 0;
		}
	}
	solve();
	return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;

long mod = 1e9 + 7;

long powmod(long x, long n){
  long ret = 1;
  while(n > 0){
    if(n&1) ret *= x, ret %= mod, n -= 1;
    else x *= x, x %= mod, n >>= 1;
  }
  return ret;
}

vector<long> fact;
vector<long> revfact;

void setfact(int n){
  fact.resize(n+1); revfact.resize(n+1);
  fact[0] = 1;
  rep(i, n) fact[i+1] = fact[i] * (i+1) % mod;
  
  revfact[n] = powmod(fact[n], mod-2);
  for(int i=n-1; i>=0; i--) revfact[i] = revfact[i+1] * (i+1) % mod;
}

long getC(int n, int r){
  return fact[n] * revfact[r] % mod * revfact[n-r] % mod;
}

int main(){
  int n; cin >> n;
  int a[n+1];
  vector<int> id[n];
  rep(i, n+1){
    cin >> a[i];
    id[a[i]-1].push_back(i);
  }
  int l, r;
  rep(i, n)if(id[i].size()==2) l = id[i][0], r = id[i][1];
  setfact(n+1);
  rep(i, n+1){
    long p = getC(n+1, i+1);
    if(l+n-r >= i) p = (p - getC(l+n-r, i) + mod) % mod;
    cout << p << endl;
  }
}

Measured memory_bytes: 8576
#include <iostream>
#include <vector>
#include <unordered_set>

int main()
{
  std::string s, t;
  std::cin >> s >> t;

  t.erase(t.end() - 1);
  if (s == t)
  {
    std::cout << "Yes" << std::endl;
  }
  else
  {
    std::cout << "No" << std::endl;
  }
  
  
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    LL H, W;
    cin >> H >> W;
    LL N = max<LL>(H, W);
    LL M = min<LL>(H, W);
    if(M == 1) {
        cout << 1 << endl;
        return 0;
    }
    LL res = ((N + 1)/2)*((M + 1)/2) + (N/2)*(M/2);
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type intHeap []int

func (h intHeap) Len() int           { return len(h) }
func (h intHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h intHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *intHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *intHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(r, &n)
	fmt.Fscan(r, &m)

	// heap
	ih := &intHeap{}
	heap.Init(ih)

	var a int
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &a)
		heap.Push(ih, a)
	}

	// 割引券を値段の高い順に適用する
	for m > 0 {
		// 最も高い値段を取り出す
		price := heap.Pop(ih).(int)
		// 半額クーポンを適用
		heap.Push(ih, price/2)
		m--
	}

	ans := 0
	for ih.Len() > 0 {
		ans += heap.Pop(ih).(int)
	}

	fmt.Println(ans)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


Measured memory_bytes: 5504
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

# sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S, W):
    return 'safe' if S > W else 'unsafe'


def main():
    S, W = read_int_n()
    print(slv(S, W))


if __name__ == '__main__':
    main()


Measured memory_bytes: 76912
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
int main(){
  ll n,k;
  cin>>n>>k;
  ll cu=0;
  ll ni=0;
  if(k%2==0){
    FORR(i,1,n){
      if(i%k==0){
        cu++;
      }
      if(i%k==k/2){
        ni++;
      }
    }
    COUT(cu*cu*cu+ni*ni*ni);
  }
  else{
    FORR(i,1,n){
      if(i%k==0){
        cu++;
      }
    }
    COUT(cu*cu*cu);
  }
}

  

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    int n = in(), m = in();
    vint v1(n, 0), v2(n, 0);
    rep(i, m)
    {
        int a = in(), b = in();
        --a;
        --b;
        if (a == 0)
            v1[b] = 1;
        if (b == n - 1)
            v2[a] = 1;
    }
    rep(i, n)
    {
        if (v1[i] == 1 && v2[i] == 1)
        {
            puts("POSSIBLE");
            return;
        }
    }
    IMP;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<cmath>
using namespace std;
const double r3=sqrt(3);
const double pi=2.0*acos(0.0);
inline double rad(double r){return r/180.*pi;}
int main()
{
  while(true){
    int n;
    scanf("%d",&n);
    if(n == 0)break;
    double theta,A;
    if( n % 3 == 0 ){ 
      A=1/(6.0*(1/tan(rad(180./n))+r3));
      A*=2*n;
    }else{
      A=1/(6.0*(1/tan(rad(60./n))+r3));
      A*=6*n;
    }
    printf("%.11lf\n",A);
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    
    if (s == u) a -= 1;
    else b -= 1;
    
    cout << a << " " << b <<endl;

    return 0;
}
    

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	char c[100][100];
	bool f;
	while(scanf("%s",c[0])!=EOF){
		f=true;
		for(int i=1;i<8;i++)scanf("%s",c[i]);
		for(int i=0;i<8&&f;i++)for(int j=0;j<8&&f;j++){
			if(c[i][j]=='1'){
				f=false;
				if(c[i][j+1]=='1'){
					if(c[i][j+2]=='1')printf("C\n");
					else if(c[i+1][j]=='1'){
						if(c[i+1][j+1]=='1')printf("A\n");
						else printf("G\n");
					}
					else printf("E\n");
				}
				else if(c[i+2][j]=='1')printf("B\n");
				else if(c[i+2][j+1]=='1')printf("F\n");
				else printf("D\n");
			}
		}
	}
}

Measured memory_bytes: 2620
#include <stdio.h>
#include<math.h>


int main() {
    int n, sum=0,p;
    scanf("%d", &n);
    p=n;
    while(n!=0){
        sum=sum+n%10;
        n=n/10;

    }
    if(p%sum==0){
        printf("Yes\n");

    }
    else
        printf("No\n");



    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <limits>
using namespace std;

int main() {
  int N;
  cin>>N;
  long A[N];
  long sum=0;
  long min=10*10*10*10*10*10*10*10*10;
  int mainasu=0;
  for(int i=0;i<N;i++){
    cin>>A[i];
    if(abs(A[i])<min)min=abs(A[i]);
    
    //中の負の数
    if(i!=0&&i!=N-1){
      if(A[i]<0) mainasu++;
    }
    
    sum+=abs(A[i]);
  }
  long ans=0;
  if(A[0]<0 && A[N-1]<0){
    if(mainasu==0)ans =sum;
    else if(mainasu%2==1) ans=sum -2*min;
    else ans = sum;
  }else if(A[0]>=0 && A[N-1]>=0){
    if(mainasu%2==1) ans=sum -2*min;
    else ans = sum;
  }else{
    if(mainasu%2==0) ans=sum -2*min;
    else ans = sum;
  }

  cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <iomanip>
#include <queue>
#define inp(X) cin >> X
#define out(X) cout << X << endl
#define out16(X) cout << setprecision(16) << X << endl
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
using namespace std;

typedef long long int ll;
#define MOD 1000000007
#define INF 1000000001

ll gcd(ll x, ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}

bool bfs(vector<vector<int>> to, vector<int> &dist, int sv)
{
	queue<int> q;
	q.push(sv);
	dist[sv]=0;
	while(!q.empty()){
		int now = q.front(); q.pop();
		for(auto v : to[now]){
			if(dist[v]!=-1) continue;
			dist[v] = dist[now]+1;
			q.push(v);
		}
	}
}

int main(void) {
	int n,m; cin >> n >> m;
	vector<vector<int>> to(n);
	rep(i,m){
		int s,t; cin >> s >> t;
		s--;t--;
		to[s].push_back(t);
	}
	vector<double> dp(n,0);
	for(int sv=n-2; sv>=0; sv--){
		double sum = 0.0;
		for( int v : to[sv] ) sum += dp[v];
		sum /= to[sv].size();
		dp[sv] = sum+1.0;
	}
	double ans = dp[0];
	vector<double> dp2(n,0);	
	for(int nv=0; nv<n; nv++){
		for(int sv=n-2; sv>=0; sv--){		
			double sum = 0.0;
			int del_v = -1; double max_e=0;
			for( int v : to[sv] ){
				if( to[sv].size()==1 || sv!=nv ) break;
				if(max_e<dp[v]){
					max_e = dp[v];
					del_v = v;
				}
			}
			for( int v : to[sv] ){
				if(v==del_v) continue;
				sum += dp2[v];
			}
			double minu = ( to[sv].size()==1 || sv!=nv ) ? 0 : 1.0;
			sum /= (to[sv].size()-minu);
			dp2[sv] = sum+1.0;
		}
//		cout << "nv = " << nv << " : dp2[0] = " << dp2[0] << endl;
		ans = min(ans,dp2[0]);
	}
	out16(ans);
}




Measured memory_bytes: 1408
#include<iostream>
#include<string>
using namespace std;

long long dp[100100][4];
int INF = 1e9 + 7;

/*
dp[i][j]の状態
i番目まで見たとき,jは何通りあるか。
jは()(A)(AB)(ABC)
*/

int main() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0;i < n;i++)for (int j = 0;j < 4;j++)dp[i][j] = 0;
	dp[0][0] = 1;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < 4;j++) {
			dp[i + 1][j] += dp[i][j];
			 if(s[i]=='?')dp[i+1][j]*=3;
		}
		if (s[i] == 'A' || s[i] == '?') {
			dp[i + 1][1] += dp[i][0];
		}
		if (s[i] == 'B' || s[i] == '?') {
			dp[i + 1][2] += dp[i][1];
		}
		if (s[i] == 'C' || s[i] == '?') {
			dp[i + 1][3] += dp[i][2];
		}
		for (int j = 0;j < 4;j++)dp[i + 1][j] %= INF;
	}
	cout << dp[n][3] << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define in insert
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n , m;
    cin >> n >> m;
        int c;

        cin >> c;
    int b[m];
    forn(i, m) cin >> b[i];
    int cnt = 0;
    int a[m];
    forn(i, n){
        int s = 0;
        for(int j = 0; j < m; j++) {
            cin >> a[j];
            s += a[j]*b[j];
        }
        s+=c;
        if(s > 0) cnt++;
        
    }
    cout << cnt;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin >>s>>t;
  int ans=0;
  for(int i=0;i<3;i++){
    if(s.at(i)==t.at(i)){
      ans++;
    }
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 256
use std::fmt;
use std::io::stdin;
use std::io::BufRead;
use std::str;
use std::str::FromStr;
use std::vec::Vec;
use std::cmp;

fn main() {
    let stdin = stdin();
    let mut scan = InputScanner::new(stdin.lock(),256);

    let n:usize = scan.next();
    let w:usize = scan.next();

    let vw:Vec<(usize,usize)> = (0..n).map(|_| (scan.next(),scan.next())).collect();

    let mut dp:Vec<usize> = (0..(w+1)).map(|_| 0).collect();

    for i in 0..n {
        for w in vw[i].1..(w+1) {
            dp[w] = cmp::max(dp[w],dp[w-vw[i].1] + vw[i].0);
        }
    }

    println!("{}",dp[w]);
}
struct InputScanner<R: BufRead> {
	reader: R,
	buf: Vec<u8>, // Should never be empty
	pos: usize,   // Should never be out of bounds as long as the input ends with '\n'
}
impl<R: BufRead> InputScanner<R> {
	fn new(reader: R, capacity: usize) -> Self {
		InputScanner {
			reader: reader,
			buf: Vec::with_capacity(capacity),
			pos: 0,
		}
	}

	#[inline]
	fn next<T: FromStr>(&mut self) -> T
	where
		T::Err: fmt::Debug,
	{
		if self.buf.is_empty() {
			self._read_next_line();
		}
		let mut start = None;
		loop {
			match (self.buf[self.pos], start.is_some()) {
				(b' ', true) | (b'\n', true) | (b'\r', true) => break,
				(_, true) | (b' ', false) => self.pos += 1,
				(b'\n', false) | (b'\r', false) => self._read_next_line(),
				(_, false) => start = Some(self.pos),
			}
		}
		let target = &self.buf[start.unwrap()..self.pos];
		unsafe { str::from_utf8_unchecked(target) }.parse().unwrap()
	}

	#[inline]
	fn _read_next_line(&mut self) {
		self.pos = 0;
		self.buf.clear();
		if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 {
			panic!("Reached EOF");
		}
	}
}




Measured memory_bytes: 5032
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for (int i=a; i<b; i++)
#define M00(i, a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _<< " _ " <<

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

int main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ld pi = acos(-1);
	ld r;
	cin >> r;
	cout << r * 2.0 * pi << endl;
}


Measured memory_bytes: 3792
#include <iostream>

using namespace std;

int GCD (int x, int y) {
    if (y==0) return x;
    return GCD(y,x%y);
}

int main () {
    int N;
    
    int ans;
    
    cin >> N;
    
    N-=2;
    
    int x, y;
    
    cin >> x >> y;
    
    ans = GCD(x,  y);
    
    for (int i=0; i<N; i++) {
        int A;
        cin >> A;
        ans = GCD(ans, A);
    }
    
    cout << ans;
    
    return 0;
}


Measured memory_bytes: 256