akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <map> // pair
using namespace std;

typedef long long ll;
#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n)   for(int i=(int)0; i<(int)n; i++)
#define llrep(i,n)   for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n) for(int i=(int)m; i<(int)n; i++)
#define all(var)     (var).begin(), (var).end()
#define prt(var)     cout << var << endl
#define prt_dbl(i,var) cout<<fixed<<setprecision(i)<<var<<endl;
template <typename Val,typename Number>
//use ll or int for gcd
Val gcd(Val a, Val b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
//count vector and return pair (count,vector item)
template <typename Val,typename Number>
void count_vector(vector<Val>* A,vector<pair<Number,Val>>*R){
  sort(A->begin(),A->end());
  int count = 1;
  rep(i,A->size()){
    if(i<A->size()-1){
      if(A->at(i)==A->at(i+1))count++;
      else{
        R->push_back(make_pair(count,A->at(i)));
        count = 1;
      }
    }else{
      R->push_back(make_pair(count,A->at(i)));
      count = 1;
    }
  }
}

//---------------------------------------------------------------

int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int>>A(N);
  string ans ="IMPOSSIBLE";
  rep(i,M){
    int a,b;
    cin>>a>>b;
    A.at(a-1).push_back(b);
  }

  if(A.at(0).size()>0){
    rep(i,A.at(0).size()){
      int to = A.at(0).at(i);
      if(A.at(to-1).size()>0){
        rep(j,A.at(to-1).size()){
          if(A.at(to-1).at(j)==N){
            ans = "POSSIBLE";
            break;
          }
        }
      }
    }
  }

  cout<<ans<<endl;




}


Measured memory_bytes: 8576
// AOJ 2058: Moduic Squares
// 2017.11.6 bal4u@uu

#include <stdio.h>
#include <string.h>
#define TM 0
#if TM
#include <time.h>
#endif

int a[10];
int mk[11];

int check()
{
	int k = (a[0]+a[1]+a[2]) % a[9];
	return  (a[3]+a[4]+a[5]) % a[9] == k &&
            (a[6]+a[7]+a[8]) % a[9] == k &&
            (a[0]+a[3]+a[6]) % a[9] == k &&
            (a[1]+a[4]+a[7]) % a[9] == k &&
            (a[2]+a[5]+a[8]) % a[9] == k &&
            (a[0]+a[4]+a[8]) % a[9] == k &&
            (a[2]+a[4]+a[6]) % a[9] == k;
}

int rec(int i)
{
	int j, r;

	if (i == 10) return check();
	if (a[i]) return rec(i+1);

	for (r = 0, j = 1; j <= 10; j++) {
		if (mk[j]) continue;
		a[i] = j;
		mk[j] = 1;
		r += rec(i+1);
		mk[j] = 0;
		a[i] = 0;
	}
	return r;
}

int main()
{
	int i, v, s;
#if TM
	clock_t start, end;
	start = clock();
#endif
	while (1) {
		memset(mk, 0, sizeof(mk));
		for (s = 0, i = 0; i < 10; i++) {
			scanf("%d", &v); if (v < 0) goto done;
			a[i] = v, mk[v] = 1, s += v;
		}
		if (s == 0) puts("365896");
		else printf("%d\n", rec(0));
	}
done:;
#if TM
	end = clock();
	printf("time %lf\n", (double)(end-start)/CLOCKS_PER_SEC);
#endif
	return 0;
}

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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = INT64_MAX;
const int INF = INT_MAX;

inline int sqr(int x) { return (x * x); }
inline void printd(double x) { printf("%.10lf\n", x); }
inline void upsort(VI& x) { sort((x).begin(), (x).end()); }
inline void downsort(VI& x) { sort((x).begin(), (x).end(), greater<int>()); }
inline int absdiff(int a, int b) { return (a - b)*(1|((a - b)>>(8*sizeof(int))));}
int gcd(int a, int b) { // 最大公約数
	if (a < b) return gcd(b, a);
	int r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
inline int lcm(int a, int b) { return a * b / gcd(a, b); } // 最小公倍数

signed main()
{
	double R;
	cin >> R;

	printd(2.0 * PI * R);
	
	return 0;
}

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


void solve(std::string S){
  long long N = S.size();
  vector<vector<long long>> dp(N, vector<long long>(2));
  dp[0][0] = 1;

  if(N >= 2) {
    if (S[0] != S[1]) {
      dp[1][0] = 2;
    }
    else {
      dp[1][1] = 1;
    }
  }
  if(N >= 3) {
    if (S[1] != S[2]) {
      dp[2][0] = max(dp[1][0], dp[1][1]) + 1;
    }
    else {
      dp[2][0] = 2;
    }
  }

  for(long long i = 3; i < N; i++) {
    if(S[i] != S[i-1]) {
      dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + 1;
    }
    else {
      dp[i][1] = max(dp[i-3][0], dp[i-3][1]) + 2;
    }
  }

  cout << *max_element(dp[N-1].begin(), dp[N-1].end()) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
  std::cin >> S;
    solve(S);
    return 0;
}


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

int main()
{
    string S, T; cin >> S >> T;
    ll len = S.length();
    string s = S;
    rep(i,len) {

        if (T == s) {
            cout << "Yes" << endl;
            exit(0);
        }
        char last = s[len-1];
        rep(j,len) {
            s[len-1-j] = s[len-2-j];
        }
        s[0] = last;
//        cout << s << endl;

    }
    cout << "No" << endl;

    

}


Measured memory_bytes: 3636
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func calc(a, date int) (count int) {
	for i := 0; (i*a + 1) <= date; i++ {
		count++
	}
	return count
}

func main() {
	n, _ := strconv.Atoi(nextLine())
	dx := strings.Split(nextLine(), " ")
	d, _ := strconv.Atoi(dx[0])
	x, _ := strconv.Atoi(dx[1])

	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(nextLine())
	}

	var sum int
	for i := 0; i < n; i++ {
		sum += calc(a[i], d)
	}

	fmt.Println(sum + x)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp> 
//using boost::multiprecision::cpp_int;
using namespace std;
#define ll long long int
#define F first
#define S second
//#define endl "\n"
//#define nl cout<<endl;
#define pb push_back
#define ull unsigned long long 
#define f(i,a,b) for(ll i=a;i<b;i++)
#define Knucklehead ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define mod 100000007
#define mat vector<vector<ll>>
mat cn(ll n, ll m){return vector< vector<ll> >(n, vector<ll>(m));}
bool compare(char &s1,char &s2){return s1 > s2;} 
bool sortmahstyle(const pair<ll,ll> &a,  const pair<ll,ll> &b) 
{ 
    if(a.second > b.second )
        return true;
    if( a.second==b.second && a.first > b.second )
       return true;
    return false;
}
bool cmp(int n, pair<int, int> const& p)
{
    return (p.first < n);
}
//me
ll const mod = 1e9+7;//998244353;
ll const inf = 1e18;
ll const maxn = 1e5+1;


void solve()
{    
     
     ll n,m; cin >> n>> m;

     ll gates[n+2];
     fill(gates, gates+n+2, 0);
     f(i,0,m){
          ll L, R; cin >> L >> R;
          gates[L]+=1;
          gates[R+1]+=-1;
     }    
     f(i,1,n+2)
          gates[i]+=gates[i-1];
     ll ans = 0;
     f(i,1,n+1)
          if(gates[i]==m)
               ans++;
     cout << ans << endl;

}

int main() {
Knucklehead 
//*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
/**/ 
        
          ll t;
          /**/t=1;
          /*/cin>>t;/**/
          f(testcases,0,t){
               //cout << "Case #" <<testcases+1<<": ";
               solve();
          }
 
 
    return 0;
}

Measured memory_bytes: 4440
#!/usr/bin/env python3.4

# abc126_a

def main():
    # input
    n, k = [int(s) for s in input().split()]
    s = input()
    # get ans
    k = k-1
    ans = s[:k] + s[k].lower() + s[k+1:]
    # output
    print(ans)

if __name__ == '__main__':
    main()



Measured memory_bytes: 2940
import math
N,M=list(map(int, input().strip().split()))
i=1
ylist1=[]
ylist2=[]
for i in range(1,int(math.sqrt(M))+1):
    if M%i==0:
        ylist1.append(i)
        ylist2.append(M//i)
ylist=ylist2+ylist1[::-1]
nm=M//N
for i in ylist:
    if i<=nm:
        break
print(i)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  char s;
  cin >> a >> s >> b; 
  // ここにプログラムを追記
  if(s == '+'){
    cout << (a + b) << endl;
  }
  else if(s == '-'){
    cout << (a - b) << endl;
  }
}

Measured memory_bytes: 256
import sys

drops = [None,
         [(0,0),(-1,0),(1,0),(0,-1),(0,1)],
         [(0,0),(-1,0),(1,0),(0,-1),(0,1),(-1,1),(-1,-1),(1,-1),(1,1)],
         [(0,0),(-1,0),(1,0),(0,-1),(0,1),(-1,1),(-1,-1),(1,-1),(1,1),(-2,0),(2,0),(0,-2),(0,2)]]

B = [[0 for j in xrange(10)] for i in xrange(10)]

for line in sys.stdin:
    x, y, s = map(int, line.rstrip().split(','))
    for dx, dy in drops[s]:
        nx, ny = x+dx, y+dy
        if (0 <= nx <= 9 and 0 <= ny <= 9):
            B[ny][nx] += 1

emp, m = 0, 0
for i in xrange(10):
    for j in xrange(10):
        if B[i][j] == 0:
            emp += 1
        m = max(m, B[i][j])
print emp
print m

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

int f(int X) {
    int digit = 0;

    while(1) {
        digit += X % 10;
        X /= 10;
        if(X == 0) {
            break;
        }
    }

    return digit;
}

int main() {
    int N;
    cin >> N;
    
    if(N % f(N) == 0) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int b[100];

int main()
{
    int n;
    cin >> n;
    rep(i, n - 1)
    {
        cin >> b[i];
    }

    int s = b[0] + b[n - 2];
    rep(i, n - 2)
    {
        //cout << min(b[i], b[i + 1]) << endl;
        s += min(b[i], b[i + 1]);
    }
    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int W, H;
    int x, y, r;
    cin >> W >> H >> x >> y >> r;
    if(W >= x+r && H >= y+r && x-r >= 0 && y-r >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3116
N = int(input())
a = list(map(int, input().split()))

rates = [400, 800, 1200, 1600, 2000, 2400, 2800, 3200]
l = [0] * 8
tmp = 0
for i in range(N):
    for j in range(8):
        if a[i] < rates[j]:
            l[j] = 1
            break
    else:
        tmp += 1

print(max(sum(l), 1), sum(l)+tmp)


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

int main() {
  int64_t Ln, Ln_1, temp;
  int32_t N;
  
  cin >> N;
  
  Ln_1 = 2;
  Ln   = 1;
  
  for (int i = 2; i <= N; i++) {
    temp = Ln;
    Ln += Ln_1;
    Ln_1 = temp;
  }
  
  cout << Ln << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct KDTree{
  class Node{
  public:
    int location;
    int p,l,r;
    Node(){}
  };
  class Point{
  public:
    int id,x,y;
    Point(){}
    Point(int id,int x,int y): id(id),x(x),y(y){}
    bool operator<(const Point &p)const{
      return id<p.id;
    }
    void print(){
      printf("%d\n",id);
    }
  };
  
  static const int NIL = -1;

  int N;
  vector<Point> P;
  vector<Node> T;
  int np;

  KDTree(){}
  KDTree(int N){init(N);}

  void init(int N_){
    N=N_;
    P.clear();
    T.clear();
    P.resize(N);
    T.resize(N);
  }
  
  static bool lessX(const Point &p1,const Point &p2){return p1.x<p2.x;}
  static bool lessY(const Point &p1,const Point &p2){return p1.y<p2.y;}
  
  int makeKDTree(int l,int r,int depth){
    if(!(l<r)) return NIL;
    int mid=(l+r)/2;
    int t = np++;
    if(depth%2==0){
      sort(P.begin()+l,P.begin()+r,lessX);
    }else{
      sort(P.begin()+l,P.begin()+r,lessY);
    }
    T[t].location=mid;
    T[t].l=makeKDTree(l,mid,depth+1);
    T[t].r=makeKDTree(mid+1,r,depth+1);
    return t;
  }
  
  void find(int v,int sx,int tx,int sy,int ty,int depth,vector<Point> &ans){
    int x=P[T[v].location].x;
    int y=P[T[v].location].y;
    if(sx<=x&&x<=tx&&sy<=y&&y<=ty){
      ans.push_back(P[T[v].location]);
    }
    if(depth%2==0){
      if(T[v].l!=NIL){
	if(sx<=x) find(T[v].l,sx,tx,sy,ty,depth+1,ans);
      }
      if(T[v].r!=NIL){
	if(x<=tx) find(T[v].r,sx,tx,sy,ty,depth+1,ans);
      }
    }else{
      if(T[v].l!=NIL){
	if(sy<=y) find(T[v].l,sx,tx,sy,ty,depth+1,ans);
      }
      if(T[v].r!=NIL){
	if(y<=ty) find(T[v].r,sx,tx,sy,ty,depth+1,ans);
      }
    }
  } 
};
//END CUT HERE

signed main(){
  int x,y;
  int N;
  scanf("%d",&N);
  KDTree kd(N);
  for(int i=0;i<N;i++) {
    scanf("%d %d",&x,&y);
    kd.P[i]=KDTree::Point(i,x,y);
    kd.T[i].l = kd.T[i].r = kd.T[i].p = kd.NIL;
  }
  kd.np=0;
  int root=kd.makeKDTree(0,N,0);

  int q;
  scanf("%d",&q);
  int sx,tx,sy,ty;
  vector<KDTree::Point> ans;
  for(int i=0;i<q;i++){
    scanf("%d %d %d %d",&sx,&tx,&sy,&ty);
    ans.clear();
    kd.find(root,sx,tx,sy,ty,0,ans);
    sort(ans.begin(),ans.end());
    for(int j=0;j<(int)ans.size();j++){
      ans[j].print();
    }
    printf("\n");
  }
  
  return 0;
}

/*
verified on 2017/07/13
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_C&lang=jp
*/

Measured memory_bytes: 16236
import numpy as np
n = int(input())
s = np.array(list(map(int, input().split())), dtype='int64')
count = 0
sidx = 0

ls = [s]
count = 0
while len(ls) != 0:
    l = ls.pop()
    mins = min(l)
    l -= mins
    count += mins
    tmpl = np.array([], dtype='int64')
    for i in l:
        if i == 0:
            if len(tmpl) != 0:
                ls.append(tmpl)
            tmpl = np.array([], dtype='int64')
        else:
            tmpl = np.append(tmpl, i)
    else:
        if len(tmpl) != 0:
            ls.append(tmpl)

print(int(count))

Measured memory_bytes: 12500
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	int N;
	cin >> N;
	set<int>A;
	int p;
	for(int i=0;i<N;i++){
		cin >> p;
		if(A.count(p))A.erase(p);
		else A.insert(p);
	}
	cout<<A.size()<<endl;
	return 0;
}
	

Measured memory_bytes: 4864
import heapq

N=int(input())
A=list(map(int,input().split()))

dataf=[]
datab=[]

q=A[0:N]
heapq.heapify(q)
s=sum(q)
dataf.append(s)
for i in range(N,2*N):
    test=A[i]
    m=heapq.heappop(q)
    if test>m:
        s+=test-m
        dataf.append(s)
        heapq.heappush(q,test)
    else:
        dataf.append(s)
        heapq.heappush(q,m)

for i in range(0,3*N):
    A[i]*=-1

q=A[2*N:3*N]
heapq.heapify(q)
s=sum(q)
datab.append(s)
for x in range(N+1,2*N+1):
    i=3*N-x
    test=A[i]
    m=heapq.heappop(q)
    if test>m:
        s+=test-m
        datab.append(s)
        heapq.heappush(q,test)
    else:
        datab.append(s)
        heapq.heappush(q,m)

datab=datab[::-1]

print(max(dataf[i]+datab[i] for i in range(0,len(dataf))))


Measured memory_bytes: 122640
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include <utility>

using namespace std;

class Edge {
	unsigned long long to;
	unsigned long long cost;
public:
	Edge() :to(ULLONG_MAX), cost(ULLONG_MAX) {}
	Edge(unsigned long long t, unsigned long long c) {
		to = t;
		cost = c;
	}
	unsigned long long To() { return to; }
	unsigned long long Cost() { return cost; }
};

class Node {
	unsigned long long node_no;
	unsigned long long min_cost;
	bool done;
	vector<Edge> to_cost;
public:
	Node() :node_no(ULLONG_MAX), min_cost(ULLONG_MAX), done(false) {}
	void push_edge(unsigned long long t, unsigned long long c) {
		to_cost.push_back(Edge(t, c));
	}

	void set_no(unsigned long long n) { node_no = n; }
	unsigned long long get_no() { return node_no; }

	void set_cost(unsigned long long c) { min_cost = c; }
	unsigned long long Min_cost() { return min_cost; }

	void set_done() { done = true; }
	bool is_Done() { return done; }

	vector<Edge>::size_type count_Edge() { return to_cost.size(); }
	Edge Return_Edge(vector<Edge>::size_type i) {
		return to_cost[i];
	}

	//昇順に並べたいので　<　に　>　を返す
	friend bool operator<(const Node& a, const Node& b) {
		return a.min_cost > b.min_cost;
	}
};

int main() {

	unsigned long long N, M;
	cin >> N >> M;
	vector<Node> NodeA;
	for (unsigned long long i = 0; i < N; i++) {
		NodeA.push_back(Node());
		NodeA[i].set_no(i);
		if (i != 0) {
			NodeA[i].push_edge(i - 1ULL, 0ULL);
		}
	}

	for (unsigned long long i = 0; i < M; i++) {
		unsigned long long L, R, C;
		cin >> L >> R >> C;
		NodeA[L - 1].push_edge(R - 1, C);
	}

	NodeA[0].set_cost(0ULL);

	//search_listは昇順にする
	//pair.firstはコスト　pair.secondはコストを更新した頂点No
	priority_queue<pair<unsigned long long, unsigned long long>, vector<pair<unsigned long long, unsigned long long>>, greater<pair<unsigned long long, unsigned long long>>> search_list;
	search_list.push(make_pair(0ULL, 0ULL));

	while (search_list.empty() == false) {
		Node tmp = NodeA[search_list.top().second];

		//完了フラグをセット
		NodeA[search_list.top().second].set_done();
		search_list.pop();

		vector<Edge>::size_type max_count = tmp.count_Edge();
		for (vector<Edge>::size_type i = 0; i < max_count; i++) {
			unsigned long long to = tmp.Return_Edge(i).To();
			unsigned long long cost = tmp.Return_Edge(i).Cost();
			if (NodeA[to].is_Done() == false) {
				if (NodeA[to].Min_cost() > tmp.Min_cost() + cost) {
					NodeA[to].set_cost(tmp.Min_cost() + cost);
					search_list.push(make_pair(NodeA[to].Min_cost(), to));
				}
			}

		}

	}

	
	if (NodeA[N - 1].Min_cost() == ULLONG_MAX) {
		cout << -1;
		return 0;
	}

	cout << NodeA[N - 1].Min_cost();


	return 0;
}

Measured memory_bytes: 13228
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>

typedef long long ll;
#define fi first
#define se second

using namespace std;

int N;
ll a[312345];
ll ans = 0;
int idx;

int main(){
  
  int i;
  
  cin>>N;
  
  for( i = 0; i < 3*N; i++ ){
    scanf("%d", a+i);
  }
  
  sort( a, a+(3*N) );
  
  reverse( a, a+(3*N) );
  
  for( i = 0; i < N; i++ ){
    idx = (2*i) + 1;
    ans += a[idx];
  }
  
  cout<<ans<<endl;
  
  
  
  return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << " = " << (x) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl


using namespace std;
using ll = long long;


int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;

    int t = (c + b - 1) / b;
    int s = (a + d - 1) / d;

    Yes(t <= s);
}


Measured memory_bytes: 3592
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const int MOD = 1000000007;
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; }

void draw(int h, int w){
    string baseEven;
    string baseOdd;

    rep(i, w){
        if(i&1){
            baseEven += '.';
            baseOdd += '#';
        }else{
            baseEven += '#';
            baseOdd += '.';
        }
    }
    rep(i, h){
        if(i&1) cout << baseOdd << endl;
        else cout << baseEven << endl;
    }
    cout << endl;
}

int main() {
    while(true){
        int h, w;
        cin >> h >> w;
        if(h==0 && w==0) break;
        draw(h, w);
    }
    return 0;
}


Measured memory_bytes: 3148
#include <bits/stdc++.h>
#include <chrono>
#include <regex>
using namespace std;
#define len(_x) (sizeof((_x)) / sizeof(_x)[0])
#define ll long long
#define fastIO  ios_base::sync_with_stdio(false); cin.tie(0); 
#define Ichar(_x) char _x;scanf("%c",&_x);
#define Iint(_x) int _x;scanf("%d",&_x); 
#define Ill(_x)  ll _x;scanf("%lld",&_x);
#define inc(a,b,x)(x)>a && (x)<b	
#define incE(a,b,x)(x)>=a && (x)<=b	
#define fileIO 	freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);


ll modo(ll a)
{
	return a % (int)(1e9+7);
}



int arr[100000];
int main()
{
	Ill(n);
	ll sum=0;
	arr[0] = 0;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &arr[i]);
	}
	arr[n + 1] = 0;
	for (int i = 0; i <= n; ++i)
	{
		sum += abs(arr[i + 1] - arr[i]);
	}
	for (int i = 1; i <= n; ++i)
	{
		ll dif = abs(arr[i] - arr[i - 1]) + abs(arr[i + 1] - arr[i]) - abs(arr[i + 1] - arr[i - 1]);
		printf("%d\n", sum - dif);

	}




}





Measured memory_bytes: 1664
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
	double n,k;
	cin >> n >> k;
	double ans=0;
	for(int i=1;i<=n;i++){
		double cnt=ceil(log2(k/i));
		if(k>i)ans+=(double)1/pow(2,cnt);
	}
	ans/=n;
	if(n-k>=0)ans+=(n-k+1)/n;
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}


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

namespace ITP1_4_C
{
	class Program
	{
		class SimpleCalc
		{
			private int a = 0;
			private char op = '?';
			private int b = 0;

			public SimpleCalc(string[] args)
			{
				a = int.Parse(args[0]);
				op = args[1][0];
				b = int.Parse(args[2]);
			}

			public int Calc()
			{
				int ans = 0;

				switch(op) {
				case '+':
					ans = a + b;
					break;
				case '-':
					ans = a - b;
					break;
				case '*':
					ans = a * b;
					break;
				case '/':
					ans = a / b;
					break;
				}

				return ans;
			}
		}

		static void Main(string[] args)
		{
			List<SimpleCalc> cs = new List<SimpleCalc>();

			while(true) {
				string[] vs = Console.ReadLine().Split(' ');

				if(vs[1] == "?") {
					break;
				}

				cs.Add(new SimpleCalc(vs));
			}

			foreach(SimpleCalc c in cs) {
				Console.WriteLine(c.Calc());
			}
		}
	}
}



Measured memory_bytes: 17936
#include <bits/stdc++.h>
using namespace std;
#define LOCAL
#pragma region Macros
typedef long long ll;
#define ALL(x) (x).begin(),(x).end()
const long long MOD=1e9+7;
// const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const map<T,U> &m){
    os << '{';
    for (auto itr=m.begin();itr!=m.end();++itr){
        os << '(' << itr->first << ',' << itr->second << ')';
        if (++itr!=m.end()) os << ',';
        --itr;
    }
    os << '}';
    return os;
}
template<typename T>
ostream &operator<<(ostream &os,const set<T> &s){
    os << '{';
    for (auto itr=s.begin();itr!=s.end();++itr){
        os << *itr;
        if (++itr!=s.end()) os << ',';
        --itr;
    }
    os << '}';
    return os;
}

void debug_out(){cerr << '\n';}
template<class Head,class... Tail>
void debug_out(Head&& head,Tail&&... tail){
    cerr << head;
    if (sizeof...(Tail)>0) cerr << ", ";
    debug_out(move(tail)...);
}
#ifdef LOCAL
#define debug(...) cerr << " ";\
cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\
cerr << " ";\
debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<typename T> T gcd(T x,T y){return y!=0?gcd(y,x%y):x;}
template<typename T> T lcm(T x,T y){return x/gcd(x,y)*y;}

template<class T1,class T2> inline bool chmin(T1 &a,T2 b){
    if (a>b){a=b; return true;} return false;
}
template<class T1,class T2> inline bool chmax(T1 &a,T2 b){
    if (a<b){a=b; return true;} return false;
}
#pragma endregion

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int ans=0;
    for (int i=0;i<N;++i){
        int a; cin >> a;
        if (!(i&1)&&a&1) ++ans;
    }
    cout << ans << '\n';
}

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

int main(){
    ll n, k , s; cin >> n >> k >> s;
    
    int rem = s+1;
    if (rem > 1000000000) rem = 1;
    for (int i = 0; i < k; i++) 
        cout << s << " ";
    for (int i = k; i < n; i++) 
        cout << rem << " ";
    cout << endl;
    return 0;
}

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

void go();
int main() {
#ifdef tokitsukaze
    freopen("TEST.txt", "r", stdin);
#endif
    go();
    return 0;
}

/*********************************  head  *********************************/


int n,m;

void go() {
    cin>>n>>m;
    if(m*2<n){
        printf("%d\n",n-2*m);
    }else{
        puts("0");
    }
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * n

def solve(idx):
    if idx == 0:
        return 0
    if idx == 1:
        return abs(h[0] - h[1])
    if dp[idx] is not None:
        return dp[idx]

    # dp[idx - 1] + abs(h[idx - 1] - h[idx])
    # dp[idx - 2] + abs(h[idx - 2] - h[idx])
    # ...
    # dp[idx - k] + abs(h[idx - k] - h[idx])

    ans = 10**10
    for i in range(1, k+1):
        if idx - i < 0:
            break
        prev = None
        if dp[idx - i] is not None:
            prev = dp[idx - i]
        else:
            prev = solve(idx - i)
        temp = prev + abs(h[idx - i] - h[idx])
        ans = min(ans, temp)

    dp[idx] = ans
    return ans

print(solve(n-1))

Measured memory_bytes: 176352
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int h,w;
	cin>>h>>w;
	int a[11][11]={};
	int cnt=0;
	FORQ(i,1,h){
		string s;
		cin>>s;
		FORQ(j,1,w){
			if(s[j-1]=='#')a[i][j]=1;
			cnt+=a[i][j];
		}
	}
	FOR(i,0,(1<<20)){
		int x=1,y=1,c=0;
		FOR(j,0,20){
			if((i>>j)&1){//r
				if(a[x][y+1]){
					c++;
					y++;
				}
			}else{//d
				if(a[x+1][y]){
					c++;
					x++;
				}
			}
		}
		//if(x==h&&y==w)cout<<i<<" x:"<<x<<" y:"<<y<<" c"<<c<<endl;
		if(x==h&&y==w&&cnt==c+1){
			cout<<"Possible";
			return 0;
		}
	}
	cout<<"Impossible";
    return 0;
}


Measured memory_bytes: 632
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = sum(B)

tmp = A[0]
for a in A[1:]:
    if a == tmp+1:
        ans += C[a-2]
    tmp = a

print(ans)

Measured memory_bytes: 8972
#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
bitset<maxn>S[maxn];
int n,m,x[100100],y[100100],dead[maxn];
int main()
{
//	freopen("c.in","r",stdin);
//	freopen("c.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)S[i][i]=1;
	for(int i=m;i>=1;i--)
	{
		int X=x[i],Y=y[i];
		for(int now=1;now<=n;now++)
		{
			if(S[now][X]&&S[now][Y]){
				dead[now]=1;
			}
			else if(S[now][X]&&!S[now][Y]){
				S[now][Y]=1;
			}
			else if(!S[now][X]&&S[now][Y]){
				S[now][X]=1;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	if(!dead[i])
		for(int j=i+1;j<=n;j++)
		{
			if(dead[j])continue;
			if((S[i]&S[j]).none())ans++;
		}
	cout<<ans;
}
 

Measured memory_bytes: 1152
/*input
9 9
*/

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

int main() {
    int a, b;
    cin >> a >> b;
    if (a <= 9 && b <= 9) {
        cout << a*b << endl;
    }
    else {
        cout << -1 << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <cmath>

using namespace std;

int main(){
	int n;
	double x[100] = {0},y[100] = {0},p_1 = 0,p_2 = 0,p_3 = 0,p_infinity = -1;
	scanf("%d",&n);
	for(int i = 0; i < n; i++) scanf("%lf",&x[i]);
	for(int i = 0; i < n; i++) scanf("%lf",&y[i]);

	for(int i = 0; i < n; i++){
		p_1 += abs(x[i] - y[i]);
		p_2 += (x[i] - y[i])*(x[i] - y[i]);
		p_3 += abs((x[i] - y[i])*(x[i] - y[i])*(x[i] - y[i]));
		p_infinity = (p_infinity >= abs(x[i] - y[i]))? p_infinity:abs(x[i] - y[i]);
 	}
	printf("%.6lf\n",p_1);
	printf("%.6lf\n",sqrt(p_2));
	printf("%.6f\n",cbrt(p_3));
	printf("%.6lf\n",p_infinity);

}



Measured memory_bytes: 2876
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;
int main(){
	int a,b,c,d,e;
	int k;
		cin>>a>>b>>c>>d>>e>>k;
	int count=0;
	if((b-a)>k)
		count++;
	if((c-a)>k)
		count++;
	if((d-a)>k)
		count++;
	if((e-a)>k)
		count++;
	if((c-b)>k)
		count++;
	if((d-b)>k)
		count++;
	if((e-b)>k)
		count++;
	if((d-c)>k)
		count++;
	if((e-c)>k)
		count++;
 
	if((e-d)>k)
	count++;
if(count==0){
	cout<<"Yay!"<<endl;
}
else{
	cout<<":("<<endl;

}
	return 0;
}
	


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;

const ll mod = 1000000007;

ll func(ll a) {
	ll res = 1;
	for (ll i = 1; i <= a; i++) {
		res *= i ;
		res = res % mod;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, m;
	cin >> n >> m;
	if (abs(n - m) >= 2) cout << 0 << endl;
	else if (abs(n - m) == 1) {
		ll ans = func(n) * func(m) % mod;
		cout << ans << endl;
	}
	else if (abs(n - m) == 0) {
		ll ans = 2 * func(n) * func(m) % mod;
		cout << ans << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

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

    cout << r * r << endl;

    return 0;
}

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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define endl '\n'

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 998244353;

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

  ll n, k;
  cin >> n >> k;
  vector<ll> h(n);
  REP(i, n) cin >> h[i];

  vector<ll> dp(n, LLINF);
  dp[0] = 0;
  REP(i, n) {
    REP(j, k) {
      if(i+j+1 < n) chmin(dp[i+j+1], dp[i] + abs(h[i] - h[i+j+1]));
    }
  }
  cout << dp[n-1] << endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double EPS = 1e-7;
const long long mod = 1e9 + 7;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define X real()
#define Y imag()
#define cross(a,b) (conj(a)*(b)).imag()
#define dot(a,b) (conj(a)*(b)).real()
#define dist(a,b) ( pow(a.X - b.X, 2) + pow( a.Y - b.Y, 2 ) )
typedef tuple <int, int, int> line;
typedef complex <double> point;
typedef vector <point> polygon;
long long n, arr[100000][3], ans[100000][3];
int main()
{
    Hello
    cin >> n;
    for(int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            cin >> arr[i][j];
    ans[0][0] = arr[0][0];
    ans[0][1] = arr[0][1];
    ans[0][2] = arr[0][2];

    for (int i = 1; i < n; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            ll maxx = 0;
            for (int k = 0; k < 3; k++)
            {
                if(k == j)
                    continue;
                maxx = max( maxx, arr[i][j] + ans[i - 1][k] );
            }
            ans[i][j] += maxx;
        }
    }
    cout << max( max( ans[n - 1][0], ans[n - 1][1] ), ans[n - 1][2] );
    return 0;
}



Measured memory_bytes: 4992
#include <stdio.h>
int f0(int p0,int p1) {
  if(p1) {
    f0((int)((double)(p0)*1.05+999.9)/1000*1000,p1-1);
  } else {
    return p0;
  }
}
int main(void) {
  int n;
  scanf("%d",&n);
  printf("%d\n",f0(100000,n));
  return 0;
}

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

int f(vector<int> v,int n,vector<int> &dp)
{
    dp[0]=0;
    dp[1]=abs(v[1]-v[0]);
    for (int i=2;i<n;i++)
        dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]) ,dp[i-2]+abs(v[i]-v[i-2]) );
    return dp[n-1];
}

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> dp(n+1,0);
    for (int i=0;i<n;i++)
        cin >> v[i];
    cout << f(v,n,dp);
}


Measured memory_bytes: 1408
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    int n, h, w;
    cin >> n >> h >> w;
    cout << ((n - h + 1) * (n - w + 1)) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct FenwickTreeMax {
    vector<int> bit;
    int n;
    const int INF = (int)1e9;

    FenwickTreeMax(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTreeMax(vector<int> a) : FenwickTreeMax(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            update(i, a[i]);
    }

    int getmax(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret = max(ret, bit[r]);
        return ret;
    }

    void update(int idx, int val) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] = max(bit[idx], val);
    }
};
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int n;
  cin >> n;
  vector<array<int,2>> h(n);
  int idx=0;
  for(auto &e: h) cin >> e[0];
  for(auto &e: h) cin >> e[1];
  // sort(h.begin(),h.end());
  auto ft = FenwickTreeMax(n);
  for(int i=0;i<n;i++) {
    int val = ft.getmax(h[i][0]-1);
    // cerr << "Max for " << h[i][0] << " = " << val << '\n';
    ft.update(h[i][0]-1,val+h[i][1]);
  }
  cout << ft.getmax(n-1);
  return 0;
}

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

int main(){
    ll n,x,m;
    cin >> n >> x >> m;
    ll f;
    f=x%m;
    ll k=0;
    ll a;
    a=f;
    vector <ll> c1(m,0),c2(m,0);
    c1[f]=1;
    ll ans=x;

    int cc=0;
    int r=0,r2;
    while(r==0){
        a=(a*a)%m;
        ++k;
        ans+=a;

        if(k==(n-1)){
            cc=1;
            break;
        }
        if(c1[a]==0){
            ++c1[a];
        }
        else{
            r=1;
            r2=a;
            ans-=a;
        }
    }

    if(cc==0){
    ll aa;
    ll ans2=aa;
    ll ru=1;
    aa=r2;
    ll rw=aa;
    
    aa=(aa*aa)%m;
    
    while(aa!=r2){
        rw+=aa;
        aa=(aa*aa)%m;
        
        
        ++ru;
    }

    //cout << ans << endl;
    //cout << k << " " << rw << endl;

    ans+=((n-k)/ru)*rw;

    aa=r2;
    rep(i,(n-k)%ru){
        ans+=aa;
        aa=(aa*aa)%m;
    }
    }



    cout << ans << endl;
    
    

    return 0;
}

Measured memory_bytes: 4780
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main(){
    int A, B;
    int ans = 0;
    cin >> A;
    cin >> B;
    //int C = B - A;
    for(int i = A; i <= B; i++){
        string S = to_string(i);
        if(S[0] == S[4] && S[1] == S[3]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

template<class T>
struct Vec2
{
	Vec2(){}
	Vec2(T _x, T _y) : x(_x), y(_y) {}

	Vec2 operator+(const Vec2& rhs) const { return Vec2(x + rhs.x, y + rhs.y); }
	Vec2 operator-(const Vec2& rhs) const { return Vec2(x - rhs.x, y - rhs.y); }
	Vec2 operator*(T s) const { return Vec2(x*s, y*s); }
	Vec2 operator/(T s) const { return Vec2(x/s, y/s); }
	T dot(const Vec2& rhs) const { return x*rhs.x + y*rhs.y; }
	T cross(const Vec2& rhs) const { return x*rhs.y - y*rhs.x; }
	T sqlength() const { return x*x + y*y; }
	double length() const { return sqrt(sqlength()); }
	bool operator<(const Vec2& rhs) const
	{
		if (x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}

	T x;
	T y;
};

template<class T>
T cross(const Vec2<T> &O, const Vec2<T> &A, const Vec2<T> &B)
{
	return (A - O).cross(B - O);
}

template<class T>
bool IsIntSegments(const Vec2<T>& A1, const Vec2<T>& A2, const Vec2<T>& B1, const Vec2<T>& B2)
{
	return (cross(A1, A2, B1)*cross(A1, A2, B2) < 0 && cross(B1, B2, A1)*cross(B1, B2, A2) < 0);
}

template<class T>
bool IsPointOnSegment(const Vec2<T>& P, const Vec2<T>& S, const Vec2<T>& E)
{
	Vec2<T> dir = E - S;
	if ((P - S).cross(dir) != 0) {
		return false;
	}
	T prd = (P - S).dot(dir);
	if (prd < 0) {
		return false;
	}
	return prd <= dir.dot(dir);
}

int main()
{
	typedef Vec2<long long> Vec;
	Vec P[3];
	cin >> P[0].x >> P[0].y;
	cin >> P[1].x >> P[1].y;

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> P[2].x >> P[2].y;

		Vec d1 = P[1] - P[0];
		Vec d2 = P[2] - P[0];
		if (d1.cross(d2) > 0) {
			puts("COUNTER_CLOCKWISE");
		}
		else if (d1.cross(d2) < 0) {
			puts("CLOCKWISE");
		}
		else if (d1.dot(d2) < 0) {
			puts("ONLINE_BACK");
		}
		else if (d1.dot(d1) < d2.dot(d2)) {
			puts("ONLINE_FRONT");
		}
		else {
			puts("ON_SEGMENT");
		}
	}
	return 0;
}


Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;
 
#define Pr(f,...) fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

const int N=1e5+50; 

int ans,n,m,p[N],prt[N]; 
int find(int x){ return prt[x]==x?x:prt[x]=find(prt[x]); }
set<int> s[N],loc[N]; 

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	//freopen("dat.in","r",stdin); 
	//freopen("my.out","w",stdout); 
#endif
	scanf("%d%d",&n,&m); 
	rep(i,1,n)scanf("%d",p+i); 
	rep(i,1,n)prt[i]=i;
	rep(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v); 
		prt[find(u)]=find(v);
	}
	rep(i,1,n){
		s[find(i)].insert(p[i]); 
		loc[find(i)].insert(i); 
	}
	rep(i,1,n){
		if(find(i)==i){
			for(auto x:loc[i]){
				if(s[i].count(x))++ans;
			}
		}
	}
	printf("%d\n", ans);
	return 0; 
}

Measured memory_bytes: 19840
use std::io::Read;
use std::cmp::min;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let h: Vec<i64> = (0..n).map(|_| it.next().unwrap().parse().unwrap()).collect();
    let mut z = h.clone();
    z.push(0);
    z.sort();
    z.dedup();
    let inf = std::i64::MAX / 10;
    let mut dp = vec![vec![inf; z.len()]; m + 1];
    dp[0][0] = 0;
    for &a in h.iter() {
        let x = z.binary_search(&a).unwrap();
        let mut next = vec![vec![inf; z.len()]; m + 1];
        for i in 0..(m + 1) {
            let mut way = vec![];
            for j in 0..z.len() {
                way.push((dp[i][j] - z[j], j));
            }
            way.sort_by_key(|p| p.0);
            way.reverse();
            let mut local = inf;
            for j in (0..z.len()).rev() {
                local = min(local, dp[i][j]);
                if j == x {
                    next[i][j] = min(next[i][j], local);
                } else if i < m {
                    next[i + 1][j] = min(next[i + 1][j], local);
                }
                while let Some((v, k)) = way.pop() {
                    if k <= j {
                        way.push((v, k));
                        break;
                    }
                }
                let p = *way.last().unwrap();
                if j == x {
                    next[i][j] = min(next[i][j], p.0 + z[j]);
                } else if i < m {
                    next[i + 1][j] = min(next[i + 1][j], p.0 + z[j]);
                }
            }
        }
        dp = next;
    }
    let mut ans = inf;
    for i in 0..(m + 1) {
        for j in 0..z.len() {
            ans = min(ans, dp[i][j]);
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

int main(){
  int N, rate;
  cin >> N;
  vector<int> rateCnt(9,0);
  for(int i = 0; i < N; i++){
    cin >> rate;
    if(rate <= 399) rateCnt[0]++;
    else if(rate <= 799) rateCnt[1]++;
    else if(rate <= 1199) rateCnt[2]++;
    else if(rate <= 1599) rateCnt[3]++;
    else if(rate <= 1999) rateCnt[4]++;
    else if(rate <= 2399) rateCnt[5]++;
    else if(rate <= 2799) rateCnt[6]++;
    else if(rate <= 3199) rateCnt[7]++;
    else rateCnt[8]++;
  }
  int minTypes = 0, maxTypes = 0;
  for(int i = 0; i < 8; i++){
    if(rateCnt[i] > 0){
      minTypes ++;
      maxTypes ++;
    }
  }
  if(minTypes == 0 && rateCnt[8] > 0) minTypes++;
  maxTypes += rateCnt[8];
  cout << minTypes << ' '<< maxTypes << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long ans = 0;

    if(n == 1){ans = 1;}
    else if(n == 2){ans = 3;}
    else{
      long a = 2;
      long b = 1;
      long c = 3;
      for(int i = 0; i < n-2; i++){
        a = b;
        b = c;
        c = a + b;
        ans = a + b;
      }
    }

      System.out.println(ans);

  }
}

/*
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String blank = sc.nextLine();
String s = sc.nextLine();
System.out.println();
System.exit(0)
*/


Measured memory_bytes: 24276
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<long int>a(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i);
  }
  int ans;
  int count=0;
  int flag=0;
  for(long int k=0;k<10000;k++){
    for(int i=0;i<N;i++){
      if(a.at(i)%2==0){
        a.at(i)=a.at(i)/2;
        count+=1;
      }
      else{
        flag=1;
      }

    }
    if(flag==1){
        break;
    }
    else{
        int unko=0;
    }
  }
  ans=count/N;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  string S,T;
  cin >> S >> T;

  for(int i=0;i<sz(S);i++){
    if(S.at(i)!=T.at(i)){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;

  return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<cmath>
using namespace std;
int f[100005][10],x,n;
int main()
{
	cin >> n;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=3;j++){
			cin>>x;
			if (i==1){
				f[1][j]=x;
			}
			f[i][j]=x+max(f[i-1][j+1>3?j-2:j+1],f[i-1][j+2>3?j-1:j+2]);
		} 	
	}
	cout << max(f[n][1],max(f[n][2],f[n][3]));
	return 0;
}

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

int main() {
  int N,L;
  cin>>N>>L;
  vector<string>s(N);
  for(int i=0;i<N;i++){
    cin>>s.at(i);
  }
  sort(s.begin(),s.end());
  for(int i=0;i<N;i++){
    cout<<s.at(i);
  }
  cout<<endl;
}

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

const int N = 100005, M = int(1e9) + 7;

int n, c[26], r = 1;
char s[N];

int main(){
	scanf("%d%s", &n, s);
	for(int i = 0; i < n; i++) c[s[i] - 'a']++;
	for(int i = 0; i < 26; i++) r = 1LL * r * (c[i] + 1) % M;
	printf("%d\n", (r + M - 1) % M);
}

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

int main(){
  int N;
  cin >> N;
  bool flag=true;
  vector <int> t(N),x(N),y(N);
  for(int i=0;i<N;i++){
    cin >> t.at(i) >> x.at(i) >> y.at(i);
  }
  for(int i=0;i<N;i++){
    if((abs(x.at(i))+abs(y.at(i))>t.at(i))||((x.at(i)+y.at(i))%2!=t.at(i)%2)){
      flag=false;
      break;
    }
  }
  if(flag){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
def dfs(nums, length, min_lim):
    ans = 0
    if length == n:
        score_ret = 0
        for a,b,c,d in req:
            if nums[b] - nums[a] == c:
                score_ret += d
        return score_ret
    
    else:
        for nu in range(min_lim, m+1):
            new_nums = nums + [nu]
            score = dfs(new_nums, length+1, nu)
            ans = max(ans, score)
    return ans

n,m,q = map(int,input().split())
req = [list(map(int,input().split())) for _ in range(q)]
ans = dfs([-1], 0, 1)
print(ans)

Measured memory_bytes: 9072
def bubble_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        for j in reversed(range(i + 1, n)):
            if a_list[j - 1][1] > a_list[j][1]:
                a_list[j - 1], a_list[j] = a_list[j], a_list[j - 1]
    return a_list


def selection_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        mini = i
        for j in range(i, n):
            if a_list[j][1] < a_list[mini][1]:
                mini = j
        if i != mini:
            a_list[i], a_list[mini] = a_list[mini], a_list[i]
    return a_list


n = int(input())
a_list = input().split()

bubble_sorted = bubble_sort(a_list[:])
print(' '.join(map(str, bubble_sorted)))
print('Stable')
selection_sorted = selection_sort(a_list[:])
print(' '.join(map(str, selection_sorted)))
if bubble_sorted == selection_sorted:
    print('Stable')
else:
    print('Not stable')



Measured memory_bytes: 5608