akhauriyash/Code-Regression huggingface dataset:
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,m,r,t[10]={},a,b,c,ans=INF,dist[205][205]={},cnt;
  cin >> n >> m >> r;
  for(int i=0; i<r; i++) {
    cin >> t[i];
    t[i]--;
  }
  sort(t,t+r);
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(i!=j) {
        dist[i][j]=1e18;
      }
    }
  }
  for(int i=0; i<m; i++) {
    cin >> a >> b >> c;
    a--,b--;
    dist[a][b]=dist[b][a]=c;
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      for(int k=0; k<n; k++) {
        if(i!=j&&i!=k&&j!=k) {
          dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
        }
      }
    }
  }
  do{
    cnt=0;
    for(int i=0; i<r-1; i++) {
      cnt+=dist[t[i]][t[i+1]];
    }
    ans=min(ans,cnt);
  }while(next_permutation(t,t+r));
  cout << ans << endl;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  int sum = 0;
  for (int i = 0; i < m; ++i) {
    int x;
    cin >> x;
    sum += x;
  }

  int ans = n - sum;
  if (ans < 0) {
    ans = -1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3596
#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using vi=vector<int>;
const int N = 1000006;
class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vi a(n + 1);
    for(int i = 1; i<=n; ++i) {
        scanf("%d", &a[i]);
    }
        dsu uf(n + 1);
    for(int i = 0; i < m; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        uf.unite(x, y);
    }
    int ans = 0;
    for(int i = 1; i <=n; ++i){
        if(uf.get(i) == uf.get(a[i])){
            ans++;
        }
    }
    printf("%d\n", ans);

return 0;
}













Measured memory_bytes: 1024
### constant

MAX_INT = (1 << 31) - 1

NEIGHBORS = [
  [[-1, -1], [ 0, -1], [-1,  0], [ 1,  0], [-1,  1], [ 0,  1]],
  [[ 0, -1], [ 1, -1], [-1,  0], [ 1,  0], [ 0,  1], [ 1,  1]]
]

### global variables

### subroutines

def gen_dists(x, y, m, n)
  dists = n.times.map{m.times.map{MAX_INT}}
  dists[y][x] = 0
  queue = [[x, y]]

  while ! queue.empty?
    x0, y0 = queue.shift
    d0 = dists[y0][x0] + 1

    for nxy in NEIGHBORS[y0 & 1]
      dx, dy = nxy
      x1 = x0 + dx
      y1 = y0 + dy
      if x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && dists[y1][x1] > d0
        dists[y1][x1] = d0
        queue << [x1, y1]
      end
    end
  end

  dists
end

### main

while true
  m, n = gets.strip.split(' ').map{|s| s.to_i}
  break if m == 0 && n == 0

  s = gets.strip.to_i

  min_dists = n.times.map{m.times.map{MAX_INT}}

  for i in (0...s)
    x0, y0 = gets.strip.split(' ').map{|s| s.to_i - 1}
    dists = gen_dists(x0, y0, m, n)

    for y in (0...n)
      for x in (0...m)
        min_dists[y][x] = dists[y][x] if min_dists[y][x] > dists[y][x]
      end
    end
  end
  #p min_dists

  t = gets.strip.to_i
  max_count = 0

  t.times.each do
    x0, y0 = gets.strip.split(' ').map{|s| s.to_i - 1}
    ndists = gen_dists(x0, y0, m, n)
    count = 0

    for y in (0...n)
      for x in (0...m)
        count += 1 if ndists[y][x] < min_dists[y][x]
      end
    end

    max_count = count if max_count < count
  end

  puts max_count
end

Measured memory_bytes: 6152
#!/usr/bin/env python
# coding: utf-8
#

def main(input_str):
    a, b, c = list(map(int, input_str.split(' ')))
    max_val = max([a, b, c])
    counter = 0
    for i in [a, b, c]:
        counter += max_val - i

    if 1 == counter % 2:
        counter -= 1
        print(int(counter/2 + 2))
        return
    else:
        print(int(counter/2))
        
if __name__ == '__main__':
    try:
        main(input().strip())
    except EOFError:
        pass


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y,a,b,c,xx,ans=0;
priority_queue<ll>a_,b_,c_;
int main(){	
	scanf("%lld %lld %lld %lld %lld",&x,&y,&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%lld",&xx);
		a_.push(xx); 
	}
	for(int i=0;i<b;i++){
		scanf("%lld",&xx);
		b_.push(xx); 
	}
	for(int i=0;i<c;i++){
		scanf("%lld",&xx); 
		c_.push(xx);
	}
	for(int i=0;i<x;i++){
		c_.push(a_.top());
		a_.pop();
	}
	for(int i=0;i<y;i++){
		c_.push(b_.top());
		b_.pop();
	}
	for(int i=0;i<x+y;i++){
		ans+=c_.top();
		c_.pop();
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 8048
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(getGCD(sc.nextInt(), sc.nextInt()));
    }
    
    static int getGCD(int x, int y) {
        if (x % y == 0) {
            return y;
        } else {
            return getGCD(y, x % y);
        }
    }
}


Measured memory_bytes: 26404
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

ll N, M;
ll dp[1005][1005];
char grid[1005][1005];

ll rec(int n, int m) {
	if(n == N - 1 && m == M - 1) {
		return 1;
	}
	if(grid[n][m] == '#') {
		return 0;
	}
	if(n >= N || m >= M) {
		return 0;
	}
	ll &ans = dp[n][m];
	if(ans != -1) {
		return ans;
	}
	ans = rec(n, m + 1) + rec(n + 1, m);
	return ans % MOD;

}

int main() {
	scanf("%lld %lld", &N, &M);
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> grid[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << rec(0, 0);
	
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 9216
#include<stdio.h>
 
int f[50];
 

 
  int main(){
    int i,n;
 
   scanf("%d",&n);
  
   for(i=0;i<n;i++){
     f[i]=0;
   }
  
   printf("%d\n",fbonachi(n));
  
   return 0;
 }   

 int  fbonachi(int n){
   if(n == 0 || n == 1){
     f[n] = 1;
     return f[n];
   }
   if(f[n] != 0)return f[n];
   f[n] = fbonachi(n-1) + fbonachi(n-2);
   return f[n];
 }

Measured memory_bytes: 596
fn main(){
    let mut line = String::new();
    let stdin = std::io::stdin();
    stdin.read_line(&mut line).expect("Could not read line");;
    let p : Vec<_> = line.trim().split(' ').collect();
    let n : i64 = p[0].parse().unwrap();
    let x : i64 = n * 800;
    let y : i64 = (n / 15) * 200;
    println!("{}", x - y);
}


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

int main(void){
    int ans=753;
    string S;
    cin>>S;
    for(int i=0;i<S.size()-2;i++){
        string s=S.substr(i,3);
        int num=atoi(s.c_str());
        if(abs(753-num)<ans)
            ans=abs(753-num);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  ll n;
  cin >> n;

  vector<ll> l(n);
  for (ll i = 0; i < n; i++) {
    cin >>l[i];
  }

  sort(l.begin(), l.end());

  ll lmax = l.back();
  vector<ll> sum(lmax * 2 + 1, n);

  ll cur = 0;
  for (ll i = 0; i <= lmax * 2; i++) {
    while (cur < n && l[cur] <= i) cur++;
    sum[i] = cur;
  }

  ll ans = 0;

  // a, b, c;
  for (ll a = 1; a <= lmax - 2; a++) {
    ll num_a = sum[a] - sum[a - 1];

    for (ll b = a + 1; b <= lmax - 1; b++) {
      ll num_b = sum[b] - sum[b - 1];
      ll min_c = b + 1;
      ll max_c = a + b - 1;
      ll num_c = sum[max_c] - sum[min_c - 1];

      ans += num_a * num_b * num_c;
    }
  }

  // a == b, c;
  for (ll a = 1; a <= lmax; a++) {
    ll num_a = sum[a] - sum[a - 1];
    if (num_a < 2) continue;

    ll max_c = a * 2 - 1;
    ll num_c = sum[max_c] - num_a;

    ans += num_a * (num_a - 1) / 2 * num_c;
  }  

  // a == b == c;
  for (ll a = 1; a <= lmax; a++) {
    ll num_a = sum[a] - sum[a - 1];
    if (num_a < 3) continue;
    ans += num_a * (num_a - 1) * (num_a - 2) / 6;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int iinf = 0x7fffffff;
const ll linf = ~(1LL<<63);
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<ll, int> mli;
typedef map<ll, ll> mll;
template<typename T>
inline T gcd(T a, T b) {
	if(a < 0) return gcd(-a, b);
	if(b < 0) return gcd( a,-b);
	if(a < b) return gcd(b, a);
	if(b == 0) return a;
	return gcd(b, a%b);
}

ll qpow(ll a, ll n, ll mod) {
	a %= mod;
	ll ans = 1LL;
	while(n) {
		if(n & 1) ans = (ans*a % mod);
		a = (a*a % mod);
		n >>= 1;
	}
	return ans;
}

// unsigned
ll qmul(ll a, ll b, ll mod) {
	a %= mod;
	b %= mod;
	ll ans = 0LL;
	while(b) {
		if(b & 1) ans = (ans+a) % mod;
		a = (a<<1) % mod;
		b >>= 1;
	}
	return ans;
}
inline ll rev(ll a, ll p) {
	return qpow(a, p - 2, p);
}

struct Point {
	int x, y;
};

#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define rep(x, st, en) for(int x = st; x < en; x++)
#define pb push_back
#define mp make_pair
#define dbgm(msg, var) cerr<<#msg<<" "<<#var<<" = "<<var<<endl; 
#define dbg(var) cerr<<#var<<" = "<<var<<endl;
#ifdef ALNDBG
clock_t s, e;
#endif

inline void tic() {
#ifdef ALNDBG
	s = clock();
#endif
}

inline void toc() {
#ifdef ALNDBG
	e = clock();
	cerr<<1000.0 * (e - s) / CLOCKS_PER_SEC<<" ms"<<endl;
#endif
}

// -------------------- Spliters ------------------------
const int maxn = 10100;

int main() {
	ios::sync_with_stdio(0);
	ll N, A, B;
	cin>>N>>A>>B;
	ll ans = 0;
	ll t;
	rep(i, 0, N) {
		cin>>t;
		if(t < A || B <= t) ans++;
	}
	cout<<ans<<endl;
	return 0;
}





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

int main(void) {
    int n;
    vector<int> zohe;
    cin >> n;
    zohe.resize(n);
    for (int i = 0; i < n; i++) cin >> zohe[i];
    cout << *max_element(zohe.begin(), zohe.end()) - * min_element(zohe.begin(), zohe.end()) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int main() {
  int a, b, c; cin >> a >> b >> c;
  if (a + b == c || b + c == a || a + c == b) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<string>

using namespace std;

int main(){
	int d;
	scanf("%d",&d);
	if(d == 25)
		printf("Christmas\n");
	else if(d == 24)
		printf("Christmas Eve\n");
	else if(d == 23)
		printf("Christmas Eve Eve\n");
	else if(d == 22)
		printf("Christmas Eve Eve Eve\n");
	return 0;

	
}


Measured memory_bytes: 128
#include <stdio.h>
int main()
{
	long long int n,min=9999999999999999,a,b;
	scanf("%lld",&n);
	for(long long int i=1;(i*i)<=n;i++)
	{
		if(n%i==0)
		{
			a=i-1;
			b=(n/i)-1;
			if((a+b)<min)
			{
				min=(a+b);
			}
		}
	}
	printf("%lld\n",min);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define MOD 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n; 
    map<string,int> m;
    for(int i = 0; i<n; i++){
        string x;
        cin>>x;
        m[x]++;
    }
    int mx = INT_MIN;
    for(auto e:m){
        mx = max(mx,e.second);
    }
    for(auto e: m){
        if(e.second == mx){
            cout<<e.first<<"\n";
        }
    }

}

Measured memory_bytes: 23808
#include <stdio.h>

int main()
{
  int Sum,Cake_cost,Donut_cost;
  int i=0;
  
  scanf("%d",&Sum);  
  scanf("%d",&Cake_cost);  
  scanf("%d",&Donut_cost);
  
  Sum = Sum - Cake_cost;
  Sum = Sum % Donut_cost;
  
  printf("%d\n",Sum);
 return 0; 
}

Measured memory_bytes: 128
import sys

N = int(input())
a = list()
for i in range(N):
  a.append(int(input()))

count = 0
turn_on = 1
visited = [0 for i in range(N)]
while turn_on != 2:
  if visited[turn_on - 1] == 1:
    print(-1)
    sys.exit()
  visited[turn_on - 1] = 1
  turn_on = a[turn_on - 1]
  count += 1
  
print(count)
  

Measured memory_bytes: 7896
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
 
INF = float("inf")
 
V, E = inpl()
adj = [[] for _ in range(V)]
D = [[INF]*V for _ in range(V)]
 
for _ in range(E):
    s, t, d = inpl()
    D[s][t] = d
 
for v in range(V):
    D[v][v] = 0 

def WarshallFloyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

D = WarshallFloyd(D)

for v in range(V):
    if D[v][v] < 0:
        print("NEGATIVE CYCLE")
        break
else:
    for d in range(V):
        print(" ".join(map(str, D[d])).replace("inf", "INF"))


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

int main() {
  int N, K;
  cin >> N >> K;
  int x = 1;
  
  for (int i=0; i<N; i++) {
    if (x <= K)
      x *= 2;
    else
      x += K;
  }
  
  cout <<x <<endl;
}


Measured memory_bytes: 256
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

int main(){
    init();
	ll A,B,K;cin>>A>>B>>K;
	if(A>=K){
		cout<<A-K<<" "<<B<<endl;
	}else{
		cout<<0<<" "<<max(0LL,(A+B)-K)<<endl;
	}
}

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

string res(int n) {
    if(n == 0) return "pairwise coprime";
    else if(n == 1) return "setwise coprime";
    else return "not coprime";
}

const int M = 1e6 + 5;

int main() {
    int N; cin >> N;
    vector<int64_t> A(N);
    for(auto &e : A) cin >> e;

    int64_t G = 0;
    rep(i, N) G = gcd(G, A[i]);
    if(G != 1) {
        cout << res(2) << '\n';
        return 0;
    }

    vector<int> smallestDivisor(M);
    smallestDivisor[1] = 1;
    for(int i = M - 1; i >= 2; --i) {
        smallestDivisor[i] = i;
        for(int j = i; j < M; j += i) {
            smallestDivisor[j] = i;
        }
    }

    map<int64_t, int> prime;

    for(auto a : A) {
        int x = a;
        while(smallestDivisor[x] != 1) {
            if(prime[smallestDivisor[x]]) {
                cout << res(1) << '\n';
                return 0;
            }
            x = x / smallestDivisor[x];
        }
        x = a;
        while(smallestDivisor[x] != 1) {
            prime[smallestDivisor[x]]++;
            x = x / smallestDivisor[x];
        }
    }

    for(auto &[key, val] : prime) cerr << key << " " << val << '\n';

    cout << res(0) << '\n';
    return 0;
}


Measured memory_bytes: 14800
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<assert.h>
#include<string>
#include<cstdlib>
#include<cctype>
#include<unordered_map>
#include<sstream>
#include<numeric>
#include<stack>
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1LL<<60;
constexpr int inf = 1e9;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};

// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ----------------------------------------------------------------------------
int dp[105][4][2];
int main(){
  string S;
  cin >> S;
  int N,K;
  N = S.size();
  cin >> K;
  dp[0][0][0] = 1;
  for(int i=0; i<N; i++){
    for(int j=0; j<4; j++){
      for(int k=0; k<2; k++){
        for(int d=0; d<10; d++){
          int nd = S[i] - '0';
          int nj = j;
          int nk = k;
          if(d != 0) nj++;
          if(nj > K) continue;
          if(k==0){
            if(nd < d) continue;
            if(nd > d) nk = 1;
          }
          dp[i+1][nj][nk] += dp[i][j][k];
        }
      }
    }
  }
  cout << dp[N][K][0] + dp[N][K][1] << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;


int main()
{
    int N;
    cin >> N;
    vector<int>A(N,0),B(N,0);
    A.resize(N,0);
    B.resize(N,0);
    for(int i=0;i<N;i++)
    {
        cin >> A[i];
        B[A[i]-1] = i+1;
    }
    for(int i=0;i<N;i++)
    {
        cout <<B[i];
        if(i!=N-1)cout <<" ";
    }


    return 0;

}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

template<typename T>
void trace(T *a, int s, int n) {
    for (int i=s; i<n; i++) {
	cout<<a[i]<<" ";
    }
    cout<<endl;
}



typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


int n,m;
int a[maxn];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>m;
    int tot=0;
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }
    sort(a,a+n);
    reverse(a,a+n);
    for (int i=0; i<n; i++) {
	tot+=a[i];
    }
    for (int i=0; i<m; i++) {
	if (a[i]*4*m < tot) out("No");
    }

    cout<<"Yes\n";
    return 0;
}


Measured memory_bytes: 256
(let* ((n (read))
       (d (loop for i from 1 to n collect (read)))
       (diag (reduce (lambda (acc elt) (+ acc elt)) (mapcar (lambda (x) (expt x 2)) d)))
       (sum (reduce (lambda (acc elt) (+ acc elt)) d)))
  (format t "~A~%" (/ (- (* sum sum)  diag) 2)))

Measured memory_bytes: 13412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int h, w;  cin >> h >>w;
  vector<string> g(h);

  for(int i=0; i<h; i++)  cin >> g.at(i);
  
  int li=0, lj=0; string ans="Possible";
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      if(g[i][j]=='.') continue;
      if(1<abs(li-i)+abs(lj-j)) ans = "Impossible";
      li = i, lj=j;
      //cout << li << ' ' << lj << ' ' << ans << endl;
    }
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  int b;
  int m;
  cin >> a >> b >> m;
  vector<int> s(a);
for (int i = 0; i < a; i++) {
  cin >> s.at(i);
}
  vector<int> r(b);
for (int i = 0; i < b; i++) {
  cin >> r.at(i);
}
  int mm = 1000000;
  for(int i = 0; i < m; i++){
    int x;
    int y;
    int z;
    int p;
    cin >> x >> y >> z;
    p = s.at(x-1)+r.at(y-1)-z;
    if(p < mm){
      mm = p;}
  }
  sort(s.begin(), s.end());
  sort(r.begin(), r.end());  
  int aa;
  aa =s.at(0)+r.at(0);
    if(aa < mm){
      mm =aa;
    }
  cout << mm << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define PB push_back
#define MP make_pair
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define INF (1<<28)
#define LLINF (1LL<<60)
#define MOD 1000000007
#define REP(i, n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;
typedef pair<int, int> P;

int main() {
    double l;
    cin >> l;
    cout << setprecision(100)<<pow(l / 3, 3);
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <queue>
#include <map>
#include <set>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }

void solve()
{
    int n, m; cin >> n >> m;
    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];
    vector<int> G[n];
    for(int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }


    vector<int> not_ok(n, -1);
    for(int i = 0; i < n; i++)
    {
        if(not_ok[i] == 0) continue;
        bool good = true;
        vector<int> tmp;
        
        for(int j = 0; j < G[i].size(); j++)
        {
            int v = G[i][j];
            if(h[i] <= h[v]) good = false;
            tmp.push_back(v);
        }
        if(good)
        {
            not_ok[i] = 1;
            for(int j = 0; j < tmp.size(); j++)
            {
                not_ok[tmp[j]] = 0;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(not_ok[i] == 1) ans++;
    }
    cout << ans << endl;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 9272
r_D_x2000 = input()

r = int(r_D_x2000.split(" ")[0])
D = int(r_D_x2000.split(" ")[1])
x2000 = int(r_D_x2000.split(" ")[2])

x = 0

for i in range(10):
    
    if i == 0:
        x = r * x2000 -D
        print(x)
        
    else:
        print(r * x - D)
        x = r * x - D

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using vb = vector<bool>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int h, w, m;
    cin >> h >> w >> m;
    set<pair<int, int>> g;
    vi r(h);
    vi c(w);
    int u, v;
    int rmx = 0;
    int cmx = 0;
    REP(i, m) {
        cin >> u >> v;
        u--;
        v--;
        r[u]++;
        c[v]++;
        chmax(rmx, r[u]);
        chmax(cmx, c[v]);
        g.emplace(u, v);
    }

    vi ri;
    vi ci;
    REP(i, h) if (rmx == r[i]) ri.emplace_back(i);
    REP(i, w) if (cmx == c[i]) ci.emplace_back(i);

    for (auto ridx : ri) for (auto cidx : ci) {
        if (g.count({ridx, cidx}) == 0) {
            cout << rmx + cmx << endl;
            return;
        }
    }
    cout << rmx + cmx - 1 << endl;
}


Measured memory_bytes: 23808
#include <bits/stdc++.h>
struct UnionFind {
public:
  int n;
  std::vector<int> par;
  UnionFind(int n): n(n) {
    par.resize(n, -1);
  }
  int root(int x) {
    return par[x] < 0 ? x : par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx == ry) return;
    if(par[rx] < par[ry]) {
      std::swap(x, y);
      rx = root(x), ry = root(y);
    }
    par[rx] += par[ry];
    par[ry] = rx;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -par[root(x)];
  }
};
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n, m; cin >> n >> m;
  vi p(n);
  for(int i=0;i<(n);++i) {
    cin >> p[i];
    p[i]--;
  }
  UnionFind uf(n);
  for(int i=0;i<(m);++i) {
    int a, b; cin >> a >> b;
    a--; b--;
    uf.unite(a, b);
  }
  map<int, set<int>> mp, num;
  for(int i=0;i<(n);++i) {
    mp[uf.root(i)].insert(p[i]);
    num[uf.root(i)].insert(i);
  }
  ll cnt = 0;
  for(auto &e1: mp) {
    auto it1 = e1.second.begin();
    auto it2 = num[e1.first].begin();
    while(it1 != e1.second.end() && it2 != num[e1.first].end()) {
      if(*it1 < *it2) {
        it1++;
      } else if(*it1 > *it2) {
        it2++;
      } else {
        cnt++;
        it1++;
        it2++;
      }
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 29184
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define hii cout << "hii" << endl
#define int ll
#define endl '\n'
#define all(s) s.begin(), s.end()
 
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; } 
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE
 
 
const int N = 1e6 + 5;
const int MAXN = 3e5 + 5;
const int M = 3e5;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const long double co = 0.0174533;
const int INF = 1e15;
const int LG = 21;
const long double PI = acos(-1);

int n;


void solve()
{
	int n;
	cin >> n;
	n = n % 10;
	if(n == 2 or n == 4 or n == 5 or n == 7 or n == 9) cout << "hon" << endl;
	else if(n == 0 or n == 1 or n == 6 or n == 8) cout << "pon" << endl;
	else cout << "bon" << endl;
}
 
 
int32_t main() 
{	
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	    int t = 1;
	    // cin >> t;
	while(t--)solve();
	return 0;
}

Measured memory_bytes: 3612
# coding: utf-8

N = int(input())
a = list(map(int, input().split()))
sum_a, sum_b = 0, 0

a = sorted(a, reverse=True)

for i in range(0, N, 2):
    sum_a += a[i]
for i in range(1, N, 2):
    sum_b += a[i]

diff = sum_a - sum_b
print(diff)

Measured memory_bytes: 3064
import itertools

table = {	1: '.,!? ',
			2: 'abc',
			3: 'def',
			4: 'ghi',
			5: 'jkl',
			6: 'mno',
			7: 'pqrs',
			8: 'tuv',
			9: 'wxyz' }

for i in range(int(input())):
	s = input()
	r = ''
	for k, g in itertools.groupby(s):
		if k == '0':
			continue
		k = int(k)
		i = (len(list(g)) - 1) % len(table[k])
		r += table[k][i]
	print(r)

Measured memory_bytes: 7704
local N, D, X = io.read("*n", "*n", "*n")
local A = {}
for i = 1, N do
    A[i] = io.read("*n")
end
table.sort(A)

local counter = N
for i = 1, N do
    counter = counter + (D-1)//A[i]
end
print(counter+X)

Measured memory_bytes: 256
#include <stdio.h>
using namespace std;

char S[4];

int main(){
  
  if(scanf("%s", S)==1);
  
  if(S[0]==S[1] || S[1]==S[2] || S[2]==S[3]){
    printf("Bad");
  } else {
    printf("Good");
  }
  
  return 0;
}

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

int main()
{
  int n, q;
  cin >> n >> q;

  vector<int> ans(n);
  vector<vector<int>> to(n);

  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    to[a].push_back(b);
  }

  for (int i = 0; i < q; i++) {
    int p, x;
    cin >> p >> x;
    p--;
    ans[p] += x;
  }

  for (int i = 0; i < n; i++) {
    for (const auto& e : to[i]) {
      ans[e] += ans[i];
    }
  }
  for (const auto& e : ans) {
    cout << e << endl;
  }
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 212345;
int t[MAX_N];

int main2() {
  int N = nextInt();
  int T = nextInt();
  REP(i, N) t[i] = nextInt();
  ll ans = 0;
  REP(i, N) {
    if (i + 1 < N)
      ans += min(T, t[i+1] - t[i]);
    else
      ans += T;
  }
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main(){
  int N;
  cin >> N;
  vector<i64> A(N),B(N);
  rep(i,0,N - 1){
    cin >> A[i] >> B[i];
  }
  if(A == B){
    cout << 0 << endl;
    return 0;
  }

  i64 ans = 0;
  i64 asdf = 0;
  i64 MIN = 1e18;
  i64 cnt = 0;
  rep(i,0,N - 1){
    if(A[i] <= B[i]){
      ans += B[i];
    }
    else{
      asdf += B[i];
      MIN = min(MIN , B[i]);
      cnt++;
    }
  }
  if(cnt >= 2) ans += asdf - MIN;
  cout << ans << endl;
}

Measured memory_bytes: 512
import java.util.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int countC = 0;
        int count = 0;
        
        if(str.charAt(0) == 'A' && !Character.isUpperCase(str.charAt(1))){
            //System.out.println("test");
            for(int i=2; i<str.length()-1; i++){
                if(str.charAt(i) == 'C'){
                    countC++;
                   //System.out.println("test1");
                }
                if(Character.isUpperCase(str.charAt(i))){
                    count++;
                    //System.out.println("test2");
                }
                if(countC > 1 || count >1){
                    //System.out.println("test3");
                    break;
                }
            }
        }else{
            
        }
        
        if(countC==1 && !Character.isUpperCase(str.charAt(str.length()-1))){
            System.out.println("AC");
        }else{
            System.out.println("WA");
        }
    }
}


Measured memory_bytes: 22612
N = int(input())
A = list(map(int,input().split()))

def calc(A):
  ans = 0
  s = A[0]
  if s > 0:
    flag = 1
  elif s < 0:
    flag = -1
  for i in range(1,N):
    s += A[i]
    if flag == 1 and s >= 0:
      ans += s + 1
      s = -1
    elif flag == -1 and s <= 0:
      ans += 1 - s
      s = 1
    flag *= -1
  return ans

if A[0] > 0:
  print(min(calc(A),calc([-1]+A[1:])+A[0]+1))
elif A[0] < 0:
  print(min(calc(A),calc([1]+A[1:])-A[0]+1))
else:
  print(min(calc([1]+A[1:]),calc([-1]+A[1:]))+1)


Measured memory_bytes: 63216
s=input()
cnt=0
if len(s)%2==0:
 for i in range(len(s)//2):
  if s[i]!=s[-(i+1)]:
   cnt+=1
else:
 for i in range(len(s)//2):
  if s[i]!=s[-(i+1)]:
   cnt+=1
print(cnt)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#include<stdio.h>
#include<deque>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;
 
int main()
{
   int a;
   cin >> a;
   if(a == 7 || a == 5 || a == 3)cout << "YES" << endl;
   else cout << "NO" << endl;
   return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace AtCoder_CSharp
{
    class AtCoder
    {
        static void Main(string[] args)
        {
            int N, X;

            string[] input = Console.ReadLine().Split(' ');

            N = int.Parse(input[0]);
            X = int.Parse(input[1]);

            input = Console.ReadLine().Split(' ');

            int[] L = new int[N];

            for(int i = 0; i < N; i++)
            {
                L[i] = int.Parse(input[i]);
            }

            int now = 0;

            for (int i = 1; i <= N; i++)
            {
                if (now == X)
                {
                    Console.WriteLine(i);
                    return;
                }

                else if (now > X)
                {
                    Console.WriteLine(i - 1);
                    return;
                }

                now += L[i - 1];
            }

            Console.WriteLine(N + 1);

        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
using namespace std; //std::の省略のため
using ll = long long;

int main()
{

  int x;
  cin >> x;

  if (x >= 30)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 3632
# gets.split.map(&:to_i)
# readlines.map(&:chomp!).map { |e| e.split.map(&:to_i) }
num = gets.to_i
values = gets.split.map(&:to_i)
count = 0
while values.all?(&:even?)
  count += 1
  values = values.map{|v| v/2}
end
puts count


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

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL)
// #define int long long 

using namespace std;

int32_t main()
{
	fio;
	int n,k;
	cin>>n>>k;
	unordered_map<int,vector<int> >mp;
	for(int i=0;i<k;i++)
	{
		int d;
		cin>>d;
		for(int j=0;j<d;j++)
		{
			int a;
			cin>>a;
			mp[a].push_back(d);
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(mp[i].size()==0)
		{
			cnt++;
		}
	}

	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <queue>
#include <set>

using namespace std;

typedef unsigned long long int ULL;
typedef long long LL;
typedef long double LD;

const LL inf = 1000000000000000;
const LL mod = 1000000007;

int main()
{
	LL a, b;
	cin >> a >> b;

	if (a <= 9 && b <= 9) {
		cout << a*b << endl;
	}
	else {
		cout << -1 << endl;
	}
	 
}

Measured memory_bytes: 256
from collections import Counter
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
ans = ['No'] * n
c = Counter(a)
for i in range(1, n+1):
    if c[i] > q - k:
        ans[i-1] = 'Yes'
for k in ans:
    print(k)


Measured memory_bytes: 12668
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
 
struct node {
	int id;
	vector<int> rel;
};

node* nodes;

void dfs(int start, int cur, int* h){
	if(h[cur] == -1){
		h[cur] = start;
		for(int i = 0; i < nodes[cur].rel.size(); i++){
			dfs(start, nodes[cur].rel[i], h);
		}
	}
}

int main() {
	int n, m, q;
	scanf("%d %d", &n, &m);
	 
	nodes = new node[n];
	for(int i = 0; i < n; i++){
		nodes[i].id = i;
	}
	while(m--){
		int l, r;
		scanf("%d %d", &l, &r);
		nodes[l].rel.push_back(r);
		nodes[r].rel.push_back(l);
	}
	
	int *h = new int[n];
	for(int i = 0; i < n; i++){
		h[i] = -1;
	}
	for(int i = 0; i < n; i++){
		dfs(i, i, h);
	}
	
	scanf("%d", &q);
	while(q--){
		int l, r;
		scanf("%d %d", &l, &r);
		printf("%s\n", h[l]==h[r] ? "yes" : "no");
	}
	return 0;
}

Measured memory_bytes: 12512
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);
		for(;;){
			int n=sc.nextInt();
			if(n==0)
				break;
			HashMap<Integer, Long> map=new HashMap<Integer, Long>();
			LinkedList<Integer> list=new LinkedList<Integer>();
			for(int i=0; i<n; i++){
				int id=sc.nextInt();
				long a=sc.nextInt();
				long b=sc.nextInt();
				if(!map.containsKey(id)){
					list.addLast(id);
					map.put(id, 0l);
				}
				map.put(id, map.get(id)+a*b);
			}
			boolean f=false;
			for(int id : list){
//				println("test:"+id+":"+map.get(id));
				if(map.get(id)>=1000000){
					println(id+"");
					f=true;
				}
			}
			if(!f)
				println("NA");
		}
		sc.close();
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 13000
import java.util.*;
public class Main {
	private static Scanner sc;
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		byte a = sc.nextByte();
		for (int l=0; l<a; l++){
			byte gx=sc.nextByte();
			byte gy=sc.nextByte();
			byte No [][] = new byte [gx+1][gy+1];
			byte b = sc.nextByte();
			for (int k=0; k<b; k++){
				byte x1=sc.nextByte();
				byte y1=sc.nextByte();
				byte x2=sc.nextByte();
				byte y2=sc.nextByte();
				
				if (x1 == x2) {
					No [x1][(Math.max(y1, y2))]+=1;
				}
				else {No[(Math.max(x1,x2))][y1]+=2;}			
			}
			int Total[][] = new int [gx+1][gy+1];
			Total[0][0] = 1;
			for (int i=0; i<=gx; i++){
				for (int j=0; j<=gy; j++){
					if (No[i][j] == 0){
						if (i>0 & j>0){
							Total[i][j]=Total[i-1][j]+Total[i][j-1];
						}
						else if (i>0){
							Total[i][j]=Total[i-1][j];
						}
						else if (j>0){
							Total[i][j]=Total[i][j-1];
						}
						else;
					}
					else if(No[i][j] == 1){
						if (i>0){
							Total[i][j]=Total[i-1][j];
							}
						else Total[i][j]=0;
					}
					else if(No[i][j] == 2){
						if (j>0){
						Total[i][j]=Total[i][j-1];
						}
						else Total[i][j]=0;
					}
					else {
						Total[i][j]=0;
					}
				}
			}
			if (Total[gx][gy]==0){
				System.out.println("Miserable Hokusai!");
			}
			else {System.out.println(Total[gx][gy]);
			}
		}
	}
}

Measured memory_bytes: 34036
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

S = input()
S = set(S)
if len(S) == 2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 6192
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    const string U = "U", D = "D", L = "L", R = "R";
    int sx, sy;
    cin >> sx >> sy;
    int tx, ty;
    cin >> tx >> ty;
    string s1,s2,s3,s4;

    if (sx == tx) {
        if (sy < ty) {
            FOR(i,sy,ty) s1 += U;
            s4 += U + R + R;
            FOR(i,ty-2,sy+2) s4 += D;
            s4 += L + L + U + U;
        }
        else {
            FOR(i,ty,sy) s1 += D;
            s4 += D + R + R;
            FOR(i,sy-2,ty+2) s4 += U;
            s4 += L + L + D + D;
        }
        bool rev = sy < ty;
        if (rev) swap(sy,ty);
        s2 += R;
        s3 += L;
        FOR(i,ty,sy+1) {
            s2 += U;
            s3 += D;
        }
        s2 += L;
        s3 += R;
        if (rev) {
            swap(sy,ty);
            swap(s2,s3);
        }
    } else if (sy == ty) {
        if (sx < tx) {
            FOR(i,sx,tx) s1 += L;
            s4 += L + U + U;
            FOR(i,tx-2,sx+2) s4 += R;
            s4 += D + D + L + L;
        }
        else {
            FOR(i,sx,tx) s1 += R;
            s4 += R + U + U;
            FOR(i,tx-2,sx+2) s4 += L;
            s4 += D + D + R + R;
        }
        bool rev = sx < tx;
        if (rev) swap(sx,tx);
        s2 += U;
        s3 += D;
        FOR(i,ty,sy+1) {
            s2 += R;
            s3 += L;
        }
        s2 += D;
        s3 += U;
        if (rev) {
            swap(sx,tx);
            swap(s2,s3);
        }
    } else {
        bool revx = sx > tx;
        bool revy = sy > ty;
        if (revx) swap(sx,tx);
        if (revy) swap(sy,ty);
        string s1x,s2x,s1y,s2y;
        FOR(i,sx,tx) {
            s1x += R;
            s2x += L;
        }
        FOR(i,sy,ty) {
            s1y += U;
            s2y += D;
        }
        if (revx) {
            s1 += s2x;
            s2 += s1x;
        } else {
            s1 += s1x;
            s2 += s2x;
        }
        if (revy) {
            s1 += s2y;
            s2 += s1y;
        } else {
            s1 += s1y;
            s2 += s2y;
        }
        string s3s,s3e,s4s,s4e;
        s3s = D + R;
        s3e = U + L;
        s4s = U + L;
        s4e = D + R;
        if (revx && revy) {
            s3 += U+L + s1 + D+R;
            s4 += D+R + s2 + U+L;
        } else if (revx) {
            s3 += D+L+ s1 + U+R;
            s4 += U+R+ s1 + D+L;
        } else if (revy) {
            s3 += U+R+ s1 + D+L;
            s4 += D+L+ s1 + U+R;
        } else {
            s3 += D+R + s1 + U+L;
            s4 += U+L + s2 + D+R;
        }
    }
    cout << s1 << s2 << s3 << s4 << endl;
    //cout << s1 << " " << s2 << " " << s3 << " " << s4 << endl;

    return 0;
}

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    unsigned long long n,m;
    cin>>n>>m;
    if (n>=(m/2)){
        cout<<m/2;
    }else{
        cout<<n+(m-2*n)/4<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans1 = 0
ans3 = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            ans1+=1
        elif a[i]==a[j]:
            ans3+=1
ans2 = (n*(n-1))//2 - ans1 - ans3
print((ans1*((1+k)*k)//2+ans2*(k*(k-1))//2)%(10**9+7))

Measured memory_bytes: 3188
from sys import stdin
from itertools import repeat
from heapq import heappushpop, heapify
def main():
    x, y, z = map(int, stdin.readline().split())
    n = x + y + z
    dat = map(int, stdin.read().split(), repeat(10, 3 * n))
    ans = 0
    p = []
    for i in xrange(n):
        a, b, c = dat[i*3:i*3+3]
        ans += a
        p.append((b - a, c - a))
    p.sort(reverse=True)
    q = []
    for i in xrange(y):
        ans += p[i][0]
        q.append(p[i][0] - p[i][1])
    heapify(q)
    aa = [ans] * (z + 1)
    for i in xrange(y, y + z):
        t = heappushpop(q, p[i][0] - p[i][1])
        aa[i-y+1] = -t + aa[i-y] + p[i][0]
    q = [-p[i][1] for i in xrange(y + z, n)]
    heapify(q)
    s = [0] * (z + 1)
    for i in xrange(1, z + 1):
        t = heappushpop(q, -p[y+z-i][1])
        s[i] = s[i-1] - t
    print max(aa[i] + s[z-i] for i in xrange(z + 1))
main()


Measured memory_bytes: 29856
#include <iostream>

using namespace std;


bool isDivisible3(int n) {
    return n % 3 == 0;
}

bool includes3(int n) {
    if (n % 10 == 3) {
        return true;
    } else {
        n /= 10;
        if (n) {
            return includes3(n);
        }
        return false;
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        if (isDivisible3(i) || includes3(i)) {
            cout << ' ' << i;
        }
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 1160