akhauriyash/Code-Regression huggingface dataset:
/*input
1
1

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int a, b, c;
  cin >> a >> b >> c;
  int k;
  cin >> k;
  while (b <= a && k > 0) {
    b *= 2;
    k--;
  }  
  while (c <= b && k > 0) {
    c *= 2;
    k--;
  }

  cout << (b > a && c > b ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,s,e) for(int i=s;i<e;i++)
#define endl '\n'
int main(){
    int k,a,b;cin>>k>>a>>b;
    rep(i,a,b+1){
        if(i%k==0){
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;
}

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


int main() {
  
  int N;
  cin>>N;
  
  
  
  vector<int> B(N);
for (int i = 0; i < N-1; i++) {
  cin >> B.at(i);
}
  int sw=0;
  for (int i = 0; i < N-2; i++) {
  if(B.at(i)<=B.at(i+1)){
    sw=sw+B.at(i);
  }else{
    sw=sw+B.at(i+1);
  }
}
  sw=sw+B.at(0)+B.at(N-2);
  cout<<sw<<endl;
  
}


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

long long n, k;
long long a[200004];

long long f(long long mid){
	long long ret = 0;
	for(int i = 0; i < n; i++){
		if(a[i] == 0){
			if(mid >= 0)	ret += n-1;
			continue;
		}
		if(a[i] < 0){
			long long target = mid/a[i];
			if(target*a[i] > mid)	target++;
			int idx = lower_bound(a, a+n, target)-a;
			ret += n - idx;
			if(idx <= i)	ret -= 1;
		}
		else{
			long long target = mid/a[i];
			if(target*a[i] > mid)	target--;
			int idx = upper_bound(a, a+n, target)-a-1;
			if(idx < 0)	continue;
			ret += idx + 1;
			if(idx >= i)	ret -= 1;
		}
	}
	return ret/2;
}

int main() {
	cin>>n>>k;
	for(int i = 0; i < n; i++)	cin>>a[i];
	sort(a, a+n);
	long long lo = -1e18, hi = 1e18;
	while(lo < hi){
		long long mid = lo + (hi - lo)/2;
		if(f(mid) >= k)	hi = mid;
		else	lo = mid + 1;
	}
	cout<<lo<<endl;
	// your code goes here
	return 0;
}

Measured memory_bytes: 1792
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

var ans int

func main() {
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(stringLineScan())
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(stringLineScan())
	}
	sort.Ints(a)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i], _ = strconv.Atoi(stringLineScan())
	}
	sort.Ints(b)
	c := make([]int, n)
	for i := 0; i < n; i++ {
		c[i], _ = strconv.Atoi(stringLineScan())
	}
	sort.Ints(c)
	aidx := 0
	cidx := 0
	anum := make([]int, n)
	cnum := make([]int, n)
	for i := 0; i < n; i++ {
		for {
			if aidx == n {
				anum[i] = n
				break
			} else if a[aidx] >= b[i] {
				anum[i] = aidx
				break
			} else {
				aidx++
			}
		}
		for {
			if cidx == n {
				cnum[i] = 0
				break
			} else if c[cidx] > b[i] {
				cnum[i] = n - cidx
				break
			} else {
				cidx++
			}
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans += anum[i] * cnum[i]
	}
	fmt.Println(ans)
}


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

#define LL long long

#define FOR(INDEX, START, END) for (LL INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (LL INDEX = 0; INDEX < (COUNT); ++INDEX)

LL Select(vector<LL> const& as) {
	LL minValue = -1;
	LL minValueIndex = -1;

	REP(i, as.size()) {
		if (as[i] <= 0) {
			continue;
		}
		if (minValue < 0 || as[i] < minValue) {
			minValue = as[i];
			minValueIndex = i;
		}
	}
	return minValueIndex;
}

int main()
{
	LL N;
	cin >> N;

	vector<LL> as(N);
	REP(i, N) {
		cin >> as[i];
	}

	for (;;) {
		LL index = Select(as);

		LL value = as[index];

		LL minValue = -1;
		REP(i, N) {
			if (i == index) {
				continue;
			}

			as[i] %= value;

			if (as[i] <= 0) {
				continue;
			}

			if (minValue < 0 || as[i] < minValue) {
				minValue = as[i];
			}
		}

		if (minValue == -1) {
			cout << value << endl;
			break;
		}
	}

	return 0;
}


Measured memory_bytes: 1024
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N, M = map(int, input().split())
lamps = [list(map(lambda x:int(x)-1, input().split()))[1:]
         for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

# bit全探索(スイッチの入れ方を全探索する)
for i in range(1 << N):
    for r in range(M):  # 全てのランプがついてるかチェック
        on_sum = 0  # ランプrにおいて、onのスイッチの数
        for j in range(N):  # スイッチのj番目について
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1  # スイッチjがランプrに繋がってて、onならon_sum+=1
        if on_sum % 2 != p[r]:  # on_off check
            break  # 一つでもoffなら次のbitに
    else:
        ans += 1
print(ans)


Measured memory_bytes: 3188
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
using namespace std;

bool sameside(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) {
    if (ax == bx) {
        if ( (cx - ax) * (dx - ax) > 0 ) return true;
        else    return false;
    } else {
        double slope = (by - ay) / (bx - ax);
        double r = ay - slope * ax;
        if ( (cy - slope * cx - r) * (dy - slope * dx - r) > 0 )    return true;
        else    return false;
    }

}

int main() {

    double a, b, c, d, e, f, g, h;
    while( cin >> a >> b >> c >> d >> e >> f >> g >> h) {
        if (sameside(a, b, c, d, e, f, g, h) && sameside(c, d, e, f, a, b, g, h) && sameside(e, f, a, b, c, d, g, h) ) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

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

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }


int main(){
    LL n, m;
    cin >> n >> m;
    vector<LL> price(m);
    vector<LL> edge(m);
    for(LL i = 0; i < m; ++i){
        LL b;
        cin >> price[i] >> b;
        for(LL j = 0; j < b; ++j){
            LL c;
            cin >> c;
            edge[i] |= (1LL<<c-1);
        }
    }
    LL INF_COST = accumulate(price.begin(), price.end(), +1);
    vector<LL> dp(1LL<<n, INF_COST);
    dp[0] = 0;
    for(LL i = 0; i < m; ++i){
        for(LL j = 0; j < (1LL<<n); ++j){
            dp[j | edge[i]] = min(dp[j | edge[i]], dp[j] + price[i]);
        }
    }

    if(dp[(1LL<<n)-1] == INF_COST){
        cout << -1 << endl;
    }else{
        cout << dp[(1LL<<n)-1] << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define INF 100000000
#define _INF -100000000
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;

vvll ans;

struct node {
	bool done;
	vi to, dist;
	int id, from;
	ll d;
	bool operator<(const node & another) const {
		return !(d != another.d ? d < another.d : id < another.id);
	}
};

void bellman_ford(vector<node> nodes, int n, int start, int limit) {
	nodes[start].d = 0;
	queue<node> que;
	que.push(nodes[start]);
	int cnt = 0;
	while (que.size() && cnt<limit) {
		node focus = que.front(); que.pop();
		Loop(i, focus.to.size()) {
			if (nodes[focus.to[i]].d > focus.d + focus.dist[i]) {
				nodes[focus.to[i]].d = focus.d + focus.dist[i];
				nodes[focus.to[i]].from = focus.id;
				que.push(nodes[focus.to[i]]);
			}
		}
		cnt++;
	}
	if (cnt == limit) ans.clear();
	else {
		ans.push_back({});
		Loop(i, n) {
			ans.back().push_back(nodes[i].d);
		}
	}
}

int main() {
	int v, e; cin >> v >> e;
	vector<node> nodes(v);
	Loop(i, v) nodes[i] = { false,{},{}, i, -1, INFLL };
	Loop(i, e) {
		int s, t, d; cin >> s >> t >> d;
		nodes[s].to.push_back(t);
		nodes[s].dist.push_back(d);
	}
	Loop(i, v) {
		bellman_ford(nodes, v, i, (v + 1)*(e + 1));
		if (ans.size() == 0) {
			cout << "NEGATIVE CYCLE" << endl;
			break;
		}
	}
	if (ans.size() != 0) {
		Loop(i, ans.size()) {
			Loop(j, ans[i].size()) {
				if (j > 0) cout << " ";
				if (ans[i][j] == INFLL) cout << "INF";
				else cout << ans[i][j];
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3484
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Map = map<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
ll INF=1LL<<60;
ll MOD=1000000007;



int main(){
  ll N;
  cin >> N;
  vector<vector<ll>> A(N, vector<ll>(N-1, 0));
  for(ll i=0;i<N;i++){
   for(ll j=0;j<N-1;j++){
     cin>>A[i][j];
     A[i][j]--;
   ;}
  ;}
  //次やりたい試合
  vector<ll> mark(N,0);
  ll ans=0;
  vector<bool> ful(N,0);
  ll full=0;
  queue<ll> mati;
  for(ll i=0;i<N;i++){
    mati.push(i);
  ;}
  while(1){
    //その日試合するなら１
    vector<ll> check(N,0);
    //試合できれば
    bool s=0;
    ll n=mati.size();
    for(ll i=0;i<n;i++){
        ll x=mati.front();
        mati.pop();
      //xが試合待ちかどうか
      if(check[x]||ful[x])continue;
      ll y=A[x][mark[x]];
      if(x==y)continue;
      //yが試合待ちかどうか
      if(check[y]||ful[y])continue;
      if(A[y][mark[y]]==x){
        mark[x]++;mark[y]++;
        if(mark[x]==N-1){ful[x]=1;full++;}
        if(mark[y]==N-1){ful[y]=1;full++;}
        check[x]=1;check[y]=1;
        mati.push(x);
        mati.push(y);
        s=1;
      }
    ;}
    if(s){
      ans++;
      if(full==N)break;
    }
    //試合できない
    else {
      cout<<-1<<endl; return 0;
    }

  }


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


Measured memory_bytes: 8064
INF = float('inf')


def tc():
    n = int(input())
    a = [tuple(map(int, input().split())) for _ in range(n)]

    # dp[i][j]: max happiness on day i+1 if you do act j (a, b, c)
    dp = [[0] * 3 for _ in range(n)]
    dp[0] = a[0]

    # since from one stone you can go to many
    # try using push dp instead of pull
    for i in range(n - 1):
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + a[i + 1][0]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + a[i + 1][1]
        dp[i + 1][2] = max(dp[i][0], dp[i][1]) + a[i + 1][2]

    print(max(dp[-1]))


tc()


Measured memory_bytes: 106076
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <iterator>
#include <iomanip>
#include <climits>
using namespace std;

vector<vector<long long> > g;
vector<bool> used;
vector<long long> a;
long long ans = 0, n;

void dfs(long long v){
    used[v] = true;
    for(int to: g[v]){
        if(!used[to]){
            a[to] = a[v] + 1;
            dfs(to);
        }
    }
    if(a[v] == n) ans++;
    used[v] = false;
}

int main(){
    long long m;
    cin >> n >> m;
    g.resize(n);
    used.assign(n, false);
    a.resize(n);
    long long fr, to;
    for(int i = 0; i < m; ++i){
        cin >> fr >> to;
        fr--, to--;
        g[fr].push_back(to);
        g[to].push_back(fr);
    }
    a[0] = 1;
    dfs(0);
    cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <map>

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

long long func(long long a,long long b){
    if(a<b){
        swap(a,b);
    }
    while(1){
        long long r=a%b;
        if(r==0){
            break;
        }
        a=b;
        b=r;
    }
    return b;

}

int main() {
    long long a,b;
    cin>>a>>b;
    cout<<a*b/func(a,b);
}

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

int main() {
  int a1, a2, a3;
  cin >> a1 >> a2 >> a3;
  a1 = a1 + a2 + a3;
  if (a1 < 22)
    cout << "win" << endl;
  else
    cout << "bust" << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int MaxN = 1e5 + 5;
typedef long long LL;
int box[MaxN];
int n;
LL solve1(){
	LL sum = 0;
	LL res = 0;
	for(int i = 1; i <= n; i++){
		sum += box[i];
		if(i & 1){
			if(sum >= 0){
				res += abs(sum) + 1;
				sum = -1;
			}
		}
		else{
			if(sum <= 0){
				res += abs(sum) + 1;
				sum = 1;
			}
		}
	}
	return res;
}
LL solve2(){
	LL sum = 0;
	LL res = 0;
	for(int i = 1; i <= n; i++){
		sum += box[i];
		if(i & 1){
			if(sum <= 0){
				res += abs(sum) + 1;
				sum = 1;
			}
		}
		else{
			if(sum >= 0){
				res += abs(sum) + 1;
				sum = -1;
			}
		}
	}
	return res;
}

int main(){
	while(~scanf("%d", &n)){
		for(int i = 1; i <= n; i++) scanf("%d", &box[i]);
		LL ans = 1LL << 60;
		ans = min(ans, solve1());
		ans = min(ans, solve2());
		printf("%lld\n", ans);
	}
	return 0;
}

			


Measured memory_bytes: 512
import java.util.Scanner;
import java.util.Set; 
import java.util.TreeSet; 
import java.util.Iterator; 
import java.util.ArrayList; 

public class Main { 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int K = sc.nextInt();
    Set<String> p = new TreeSet<String>();
    for (int i =1; i<=Math.min(5,s.length()); i++ ) {
      for (int j =0; j+i<s.length()+1; j++) {
        String a = s.substring(j,j+i);
        p.add(a);
      }
    }
    Iterator it = p.iterator();
    StringBuilder sb = new StringBuilder();
    int i =1;
    while (i < K) {
      sb.append(it.next());
      i++;
    }
    System.out.println(it.next());
  }
}   

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

int main()
{
  int n;
  cin >> n;
  int cnt = 0;
  int mini = INT_MAX;
  for (int i = 0; i < n; i++) {
    int val;
    cin >> val;
    if (val < mini) {
      cnt++;
    }
    mini = min(mini, val);
  }
  cout << cnt << '\n';
  return 0;
}


Measured memory_bytes: 256
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	N, M := getInt(), getInt()
	a := make([]int, N+1)
	for i := 0; i < M; i++ {
		l, r := getInt()-1, getInt()-1
		a[l]++
		a[r+1]--
	}
	// out(a)
	for i := 0; i < N; i++ {
		a[i+1] += a[i]
	}
	// out(a)
	cnt := 0
	for i := 0; i < N; i++ {
		if a[i] == M {
			cnt++
		}
	}
	out(cnt)
}


Measured memory_bytes: 3712
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

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

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	n := int64(r.nextInt())

	fmt.Fprintln(stdout, (n-1)*n/2)
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
    //int N;
    //int A[100000]={};
    int i=0;
    //int j=0;
    //int x=0;
    //int num=0;
    //int cnt=0;
    char cpy;
    
    char str1[20]={};
    char str2[20]={};
    
    cpy=str1[20];
    
    
    gets(str1);
    gets(str2);
    
    for(i=0;i<11;i++){
        if(str1[i]!=str2[i]){
            if(str1[i]==str1[15]){
                printf("Yes");
                return 0;
            }else{
                printf("No");
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 1644
N, M, *C = map(int, open(0).read().split())
MOD = 10**9 + 7
F = [0]*(N+1)
for c in C:
    F[c-1] = 1

a = 1; b = 0
for i in range(N):
    if F[i]:
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

Measured memory_bytes: 13812
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

h,w=map(int,input().split())
a=[input() for i in range(h)]

cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            cnt+=1
if cnt!=h+w-1 or a[0][0]!="#" or a[-1][-1]!="#":
    print("Impossible")
    exit()

now=[0,0]
for i in range(h+w-2):
    if now[0]+1<h and a[now[0]+1][now[1]]=="#":
        now[0]+=1
    elif now[1]+1<w and a[now[0]][now[1]+1]=="#":
        now[1]+=1
    else:
        print("Impossible")
        exit()
print("Possible")

Measured memory_bytes: 69280
//Utkarsh-raj

#include<bits/stdc++.h>

#define ll long long int
#define vc vector
#define mod 100000000007
#define mp make_pair
#define pb push_back
#define nl cout<<endl;
#define ff first
#define ss second

using namespace std;

int n;
int arr[100010];
int dp[100010];

void solve(){
    dp[1] = abs(arr[1] - arr[0]);

    for(int i=2; i<n; i++){
        dp[i] = min(abs(arr[i] - arr[i-1]) + dp[i-1], abs(arr[i] - arr[i-2]) + dp[i-2]);
    }
    cout<<dp[n-1]<<endl;
}

int main()
{
    ifstream myFile("task.in");
    if(!myFile.fail())
    {
        assert(freopen("task.in", "r", stdin));
    }

    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    solve();

    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{	
	int a,b,c,d;
	int i,j,n,t;
	scanf("%1d%1d%1d%1d",&a,&b,&c,&d);
	int sz[4]={a,b,c,d};
	for(i=0;i<8;i++)
	{
		n=sz[0];
		t=i;
		for(j=1;j<=3;j++){
			if(t%2==0)
				n+=sz[j];
			else 
				n-=sz[j];
			t/=2;
		}
		if(n==7)
			break;
	}
	cout<<sz[0];
	for(j=1;j<=3;j++)
	{
		if(i%2==0)
			cout<<"+";
		else 
			cout<<"-";
		i/=2;
		cout<<sz[j];
	}
	cout<<"=7"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct activity
{
	int A, B, C;
};

int solve(struct activity* a, int n)
{
	int dp[n + 1][3] = {};
	dp[1][0] = a[1].A;
	dp[1][1] = a[1].B;
	dp[1][2] = a[1].C;

	for(int i=2; i<=n; ++i)
	{
		dp[i][0] = a[i].A + max(dp[i - 1][1], dp[i - 1][2]);

		dp[i][1] = a[i].B + max(dp[i - 1][0], dp[i - 1][2]);

		dp[i][2] = a[i].C + max(dp[i - 1][1], dp[i - 1][0]);
	}

	return max(dp[n][0], max(dp[n][1], dp[n][2]));
}
int32_t main()
{
	FIO;
	int n; cin >> n;

	mk(a, n + 1, activity);
	for(int i=1; i<=n; ++i)	
		cin >> a[i].A >> a[i].B >> a[i].C;

	cout << solve(a, n) << '\n';
	return 0;
}

Measured memory_bytes: 8292
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
LL n,C,x[N],t[N],sum[N],ans1[N],ans2[N],ans3[N],ans4[N];
int main(){
	scanf("%lld%lld",&n,&C);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",&x[i],&t[i]);
		sum[i]=sum[i-1]+t[i];
	}
	ans1[0]=0;
	for (int i=1;i<=n;i++){
		ans1[i]=max(ans1[i-1],sum[i]-x[i]);
		ans3[i]=max(ans3[i-1],sum[i]-x[i]*2);
	}
	ans2[n+1]=0;
	for (int i=n;i>=1;i--){
		ans2[i]=max(ans2[i+1],sum[n]-sum[i-1]-(C-x[i]));
		ans4[i]=max(ans4[i+1],sum[n]-sum[i-1]-(C-x[i])*2);
	}
	LL res=0;
	for (int i=1;i<=n+1;i++)
		res=max(res,max(ans1[i-1]+ans4[i],ans3[i-1]+ans2[i]));
	printf("%lld",res);
	return 0;
}

Measured memory_bytes: 5760
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
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;
}
const int MOD = 1000000007;
int rui(int a, int b) {
    if(b == 0) {
        return 1;
    }
    return rui(a, b - 1) * a;
}
int main() {
    int N, D, X;
    cin >> N >> D >> X;
    vector<int> a(N);
    rep(i, 0, N) { cin >> a[i]; }
    int sum = X;
    rep(i, 0, N) { sum += 1 + (D - 1) / a[i]; }
    cout << sum << endl;
}

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

using namespace std;

const int MAXN = 8000;
bool dp[MAXN + 1][MAXN + 1];

bool isPoss(vector<int> v, int offset)
{
    if (v.empty())
        return offset == 0;
    int sum = 0;
    for (int x : v)
        sum += x;
    if (sum % 2 != offset % 2)
        return false;
    for (int i = 0; i <= (sum - offset) / 2; i++)
        dp[0][i] = false;
    dp[0][0] = true;
    dp[0][v[0]] = true;
    for (int i = 1; i < (int) v.size(); i++)
    {
        dp[i][0] = true;
        for (int k = 1; k <= (sum - offset) / 2; k++)
        {
            dp[i][k] = dp[i - 1][k] || dp[i - 1][k - v[i]];
        }
    }
    return dp[(int) v.size() - 1][(sum - offset) / 2];
}

int main()
{
    string s;
    int x, y;
    cin >> s >> x >> y;
    if (s.find("T") == string::npos)
    {
        cout << ((int) s.length() == x && y == 0 ? "Yes" : "No") << endl;
    }
    else
    {
        x -= (int) s.find("T");
        s = s.substr((int) s.find("T"));
        bool LR = true;
        int ptr = 0;
        vector<int> leftRight, upDown;
        while (ptr < (int) s.length())
        {
            if (s[ptr] == 'T')
            {
                LR = !LR;
                ptr++;
            }
            else
            {
                int cnt = 0;
                while (ptr < (int) s.length() && s[ptr] == 'F')
                {
                    ptr++;
                    cnt++;
                }
                if (LR)
                    leftRight.push_back(cnt);
                else
                    upDown.push_back(cnt);
            }
        }
        cout << (isPoss(leftRight, abs(x)) && isPoss(upDown, abs(y)) ? "Yes" : "No") << endl;
    }
    return 0;
}


Measured memory_bytes: 21760
#include <iostream>
 using namespace std ;
 int main()
 {
   int A, B, c, d, e;
   cin>>A;
   cin>>B;
   c =(A + B);
   d =(A - B);
   e =(A * B);
   if (c >= e&&c >= d)
   {
   cout<<c<<endl;
   }
else   if (e >= d&&e >= c)
   {
     cout<<e<<endl;
   }
  else  if (d >= e&&d >= c) 
   {
     cout<<d<<endl;
   }
   }

Measured memory_bytes: 3596
uses
  SysUtils,
  Classes;
 
 function WhiteCheckFunc(const str : string) : Boolean;
	var 
		i : Integer;
	begin
	Result := True;
	for i := 1 to Length(str)  do
		begin
		if str[i] = '#' then
			Result := False;
		end;
	end;
 procedure subProc(const h : Integer; const w : Integer);
	var
		i, j : Integer;
		post_height : Integer;
		str : string;
		line : string;
	begin
	line := '';
	post_height := h;
	for i := 0 to h - 1 do
		begin
		ReadLn(str);
		if WhiteCheckFunc(str) then
			post_height := post_height - 1
		else
			line := line + str;
		end;
	for i := 1 to w do
		begin
		str := '';
		for j := 0 to post_height - 1 do
			str := str + line[i + j * w];
		if WhiteCheckFunc(str) then
			begin
				for j := 0 to post_height - 1 do
					line[i + j * w] := '_';
			end;
		end;
	for i  := 0 to post_height - 1 do
		begin
		for j := 1 to w do
			if not (line[j + i * w] = '_') then
				Write(line[j + i * w]);
		Write(#13#10);
		end;
	end;
  
procedure MainProc;
	var
		text : string;
		strlist : TStringList;
		heightNum : Integer;
		widthNum : Integer;
	begin
	ReadLn(text);
	strlist := TStringList.Create;
	try
		strlist.Delimiter := ' ';
		strlist.DelimitedText := text;
		heightNum := StrToInt(strlist.Strings[0]);
		widthNum := StrToInt(strlist.Strings[1]);
		finally
			FreeAndNil(strlist);
			end;
		subProc(heightNum, widthNum);
	end;
  
begin
MainProc;
end.


Measured memory_bytes: 288
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define int long long 
typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=10000005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

int f[MAXN];
main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N; cin >> N;
	int ans = 0;
	FOR(i,1,N){
		FOR(j,1,N/i){
			f[j*i]++;
		}
	}
	//FOR(i,1,N) db(f[i]);
	FOR(i,1,N) ans += i*f[i];
	cout<<ans;
}


Measured memory_bytes: 81744
from math import sqrt, pow
from operator import sub


def sub_(t):
    return abs(sub(*t))


n = input()
x = list(map(float, input().split()))
y = list(map(float, input().split()))

print(sum(map(sub_, zip(x, y))))
print(sqrt(sum(map(lambda t: sub_(t) ** 2, zip(x, y)))))
print(pow(sum(map(lambda t: sub_(t) ** 3, zip(x, y))), 1/3))
print(max(map(sub_, zip(x, y))))


Measured memory_bytes: 5780
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
int N,Q;
string S;
vector<char> T,D;
bool judge(int x){
    if(x < 0 || x >= N)return true;
    rep(i,0,Q){
        if(S[x] == T[i]){
            x += D[i] == 'R' ? 1 : -1;
        }
        if(x < 0 || x >= N)return true;
    }
    return false;
}
main(){
    cin >> N >> Q >> S;
    T.resize(Q);
    D.resize(Q);
    rep(i,0,Q){
        cin >> T[i] >> D[i];
    }
    int lok = -1, lng = N;
    while(abs(lok - lng) > 1){
        //cout << lok << "," << lng << endl;
        int mid = (lok + lng) / 2;
        if(judge(mid))lok = mid;
        else lng = mid;
    }
    int rok = N, rng = -1;
    while(abs(rok - rng) > 1){
        //cout << rok << " " << rng << endl;
        int mid = (rok + rng) / 2;
        if(judge(mid))rok = mid;
        else rng = mid;
    }
    //cout << lok << " " << rok << endl;
    cout << max(0, N - (lok + 1) - (N - rok) )<< endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD=1000000007;

vector<vector<char>> A(10,vector<char>(10,'.'));


int main() {
    int H,W;
    cin>>H>>W;
    int count=0;
    for(int i=1;i<=H;i++) {
        for (int j = 1; j <= W; j++) {
            cin >> A[i][j];
            if(A[i][j]=='#')count++;
        }
    }
    if(count==H+W-1){
        cout<<"Possible";
    }
    else{
        cout<<"Impossible";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
int x;
cin>>x;
int z=0;
for(int i=0 ;i<=2;i++){
if(x%10==7){
cout<<"Yes"<<endl;
z++;
break;
}
else{
    x/=10;
}}
if(z==0)
    cout<<"No";
return 0;
}


Measured memory_bytes: 3588
#include<set>
#include<map>
#include<stdio.h>	
using namespace std;
set<int>Se;
map<int,int>mmp;
int main()
{
	int N,K;
	int max=-1,min=100001;
	scanf("%d%d",&N,&K);
	while(N--)
	{
		int num;
		scanf("%d",&num);
		max=num>max ? num : max;
		min=num<min ? num : min;
		Se.insert(num);	
		mmp[num]++;
	}
	set<int> :: iterator it=Se.begin(); 
	if(K>max)
		printf("IMPOSSIBLE");
	else
	{
		int Size=Se.size();
		while(1)
		{
			if(mmp[K]!=0)
				break;
			set<int> :: iterator it=Se.begin(); 
			int n=*it;
			for(it++;it!=Se.end();it++)
			{
				int value=(*it)-n;
				min= min < value ? min :value;
				mmp[value]++;
				if(K%min == value %min)
				{
					mmp[K]++;
					break;
				}
				Se.insert((*it)-n);
				n=*it;
			}
			if(Size==Se.size())
				break;
			Size=Se.size();
		}
		if(mmp[K]!=0)
			printf("POSSIBLE");
		else
			printf("IMPOSSIBLE");
		printf("\n");
	}
	return 0;
}


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

int main(){
  char c[9];
  rep(i,0,9) cin>>c[i];
  cout<<c[0]<<c[4]<<c[8]<<endl;
}

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

int main(){
  int x,n;
  cin >> x >> n;
  int p[n],a[110];
  rep(i,110){
    a[i]=0;
  }
  rep(i,n){
    cin >> p[i];
    a[p[i]]++;
  }
  
  rep(i,n+10){
    if(a[x-i] == 0){
      cout << x-i << endl;
      return 0;
    }
    else if(a[x+i] == 0){
      cout << x+i << endl;
      return 0;
    }
  }
  
  return 0;
}


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

int main()
{
    int n, k; cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = 0;
    }
    while (k--) {
        int d; cin >> d;
        while (d--) {
            int x;
            cin >> x;
            a[x - 1]++;
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) cnt++;
    }
    cout << cnt;
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll n, m, k;
    cin >> n >> m >> k;
    vll a(n), b(m);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    vll sa(n + 1), sb(m + 1);
    rep(i, n) sa[i + 1] = sa[i] + a[i];
    rep(i, m) sb[i + 1] = sb[i] + b[i];
    ll ok = 0, ng = n + m + 1;
    while(ng - ok > 1) {
        ll mid = (ok + ng) / 2;
        ll mint = INFL;
        for(ll i = max(0ll, mid - m); i <= min(mid, n); i++) {
            chmin(mint, sa[i] + sb[mid - i]);
        }
        if(mint <= k) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
    return;
}

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

Measured memory_bytes: 9476
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

// *** at 2018/**/**

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

    private void solveA() {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        if (A + B < 10) {
            System.out.println(A + B);
        } else {
            System.out.println("error");
        }
    }

    private void solveB() {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        List<String> list = Arrays.asList(S.split(""));
        ArrayList<String> used = new ArrayList<>();
        for (String s : list) {
            if (used.contains(s)) {
                System.out.println("no");
                return;
            }
            used.add(s);
        }
        System.out.println("yes");
    }

    private void solveC() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }

    private void solveD() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }

    private void solveE() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }

    private void solveF() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }

}

Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
int bit[MAX];

void Add(int i,int x){
  while(i){
    bit[i]+=x;
    i-=(i&-i);
  }
}
//i=i-(i&-i)
int Get(int i){
  int res=0;
  while(i<MAX){
    res+=bit[i];
    i+=(i&-i);
  }
  return res;
}

int n,q;

int main(){
  scanf("%d %d",&n,&q);
  while(q--){
    int type;
    scanf("%d",&type);
    if(type==0){
      int l,r,x;
      scanf("%d %d %d",&l,&r,&x);
      Add(r,x);
      Add(l-1,-x);
    }else{
      int target;
      scanf("%d",&target);
      printf("%d\n",Get(target));
    }
  }
  return 0;
}

Measured memory_bytes: 3524
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int fx,a;
  string x;
  cin>>x;
  a=atoi(x.c_str());
  size_t n=x.length();
  for(int i=0;i<n;++i){
    string len=x.substr(i,1);
    fx+=atoi(len.c_str());
  }
  if(a%fx==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#bfs

S=input()
N = len(S)+1

ans = 0
a = [None]*N

prev = ">"
q=[]

#確定0を埋める．
for i in range(N-1):
    if prev==">" and S[i] == "<":
        a[i]=0
        q.append(i)
    prev = S[i]

if S[-1]==">":
    a[-1]=0
    q.append(N-1)

while len(q)!=0:
    i = q.pop()
    if i+1 < N:
        if S[i]=="<":
            if a[i+1]==None:
                a[i+1]=a[i]+1
                q.append(i+1)
            else:
                a[i+1]=max(a[i]+1,a[i+1])
    if i-1>=0:
        if S[i-1]==">":
            if a[i-1]==None:
                a[i-1]=a[i]+1
                q.append(i-1)
            else:
                a[i-1]=max(a[i]+1,a[i-1])

print(sum(a))

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

#define MAX_DATA 200

int main(){
    int a, b;
    int c;
    int f[ MAX_DATA ];
    int i;

    c = 0;

    while ( ( c < MAX_DATA ) && ( 2 == scanf( "%d %d", &a, &b ) ) ) {
        f[ c ++ ] = ( int )log10( ( double )( a + b ) ) + 1;
    }

    for ( i = 0; i < c; i ++ ) {
        printf( "%d\n", f[ i ] );
    }

    return 0;
}

Measured memory_bytes: 640
N = int(input())
S = input()
 
result = min(S.count("."),S.count("#"))
leftblack = 0
rightwhite = S.count(".")
 
for i in range(N):
    if(S[i] == "."):
        rightwhite -= 1
    else:
        leftblack += 1
    if result >= leftblack + rightwhite:
        result = leftblack + rightwhite
 
print(result)

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll m,d;
  cin >> m >> d;
  ll cnt = 0;
  REP(i,m){
    ll mi = i+1;
    REP(j,d){
      ll di = j+1;
      if(di/10>1 && di%10>1){
        if(mi==(di/10)*(di%10)) cnt++;
      }
    }
  }
  cout << cnt<< endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
#define yes(a) printf(a ? "yes\n" : "no\n")
#define Yes(a) printf(a ? "Yes\n" : "No\n")
#define YES(a) printf(a ? "YES\n" : "NO\n") 
const long double PI = acos(-1);
const long long INF = (1 << 30);
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

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

  ll ans = 0;
  ll mode = 0;
  for(ll i = 0; i < n-1; i++){
    if(a[i] > a[i+1]){
      if(mode == 0) mode = 1;
      if(mode == 2){
        ans++;
        mode = 0;
      }
    }else if(a[i] < a[i+1]){
      if(mode == 0) mode = 2;
      if(mode == 1){
        ans++;
        mode = 0;
      }
    }
    //cout << mode << endl;
  }
  cout << ans+1 << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include <climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
struct P {
	ll pos, cost;
	bool operator<(const P &b) { return cost < b.cost; }
	bool operator>(const P &b) { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) { return cost < b.cost; }
	bool operator>(const E &b) { return cost > b.cost; }
};
struct H {
	ll x, y;
	bool operator<(const H &b) {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) { return (*this) != b; }
};
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ld mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
signed main() {
	int n;
	int h[200];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		while (h[i] > 0) {
			for (int j = i; j < n&&h[j]>0; j++) {
				h[j]--;
			}
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
// date: July 13 2020
// author: Tibbarnit

#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
typedef long long ll;
int n,W,w[105],v[105];
ll f[105][100020];

void DP()
{
    for (int i=1;i<=n;++i)
        for (int j=0;j<=W;++j)
        {
            f[i][j]=f[i-1][j];
            if (w[i]<=j)
                f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
        }
    cout<<f[n][W];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>W;
    for (int i=1;i<=n;++i) cin>>w[i]>>v[i];
    DP();
    return 0;
}


Measured memory_bytes: 81748
H,W = map(int,input().split())
a = [''] * H
for i in range(H):
    a[i] = input()
row = [False] * H
col = [False] * W
for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            row[i] = True
            col[j] = True

for i in range(H):
    if row[i] :
        for j in range(W):
            if col[j]:
                print(a[i][j],end='')
        print()

Measured memory_bytes: 4468
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 200000
long long a[N], b[N], c[N];
int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; ++i) cin >> a[i];
    for(int i=0; i<n; ++i) cin >> b[i];
    long long res = 0;
    for(int i=0; i<30; ++i){
        for(int j=0; j<n; ++j) c[j] = b[j]%(2<<i);
        sort(c, c+n);
        for(int k=0; k<n; ++k){
            int j = a[k]%(2<<i);
            if(j>>i){
                int x = (1<<i)-(j-(1<<i));
                res ^= ((lower_bound(c,c+n,x)-c)&1)<<i;
                res ^= ((c+n-lower_bound(c,c+n,(1<<i)+x))&1)<<i;
            }
            else {
                int x = (1<<i)-j;
                res ^= ((lower_bound(c,c+n,(1<<i)+x)-lower_bound(c,c+n,x))&1)<<i;
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int a[100010];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi();
	for(int i=1;i<=n;++i)a[i]=gi();
	std::sort(a+1,a+n+1,std::greater<int>());
	for(int i=1;i<=n;++i)
		if(a[i+1]<i+1){
			int R=i;while(R<n&&a[R+1]==i)++R;
			R-=i;
			if((a[i]-i&1)||(R&1))puts("First");
			else puts("Second");
			return 0;
		}
}


Measured memory_bytes: 640