akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

// MACROS

#define ll long long
#define ull unsigned long long
#define ld long double

#define vi vector<int>
#define vll vector<ll>
#define vld vector<ld>
#define u_s unordered_set

#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i, n) for (ll (i) = 0; i < n; i++)
#define FORN(i, a, b) for (ll (i) = a; i < b; i++)
#define FORE(i, l) for (auto (i) : l)

#define pb push_back
#define pob pop_back
#define emp emplace

#define in(n) cin >> (n);
#define debug(n) cout << #n << ": " << n << '\n';

// FUNCTIONS

template< typename T >
inline T gcd(T a, T b) { if (b) return gcd(b, a % b); return a; }

template< typename T >
inline T ext_gcd(T a, T b, T & x, T & y) { if (a == 0) { x = 0; y = 1; return b; } T x1, y1; T g = ext_gcd(b % a, a, x1, y1); x = y1 - (b / a) * x1; y = x1; return g; }

#define MOD (ll)(1e9+7)

#define MAX (ll)(1e6+1)

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    ll x, y;
    cin >> x >> y;
    ll t = max(x, y);
    y = min(x, y);
    x = t;
    ll move1 = x - y;
    x -= 2 * move1;
    y -= move1;
    if (x % 3 != 0 || x < 0 || y < 0 || x != y) { cout << 0 << '\n'; return 0; }
    move1 += x / 3;
    ll move2 = x / 3;
    ll total = move1 + move2;
    map<ll, ll> divs;
    vi sieve(MAX);
    vll primes;
    FORN(i, 2, move2 + 1)
    {
        if (!sieve[i])
        {
            primes.pb(i);
            for (ll j = i * i; j < move2 + 1; j += i) sieve[j]++;
        }
    }
    FORE(i, primes) 
    {
        ll j = i;
        while (j <= move2) 
        {
            divs[i] += move2 / j;
            j *= i;
        }
    }
    ll cur = 1;
    FORN(i, move1 + 1, total + 1)
    {
        ll div = 1;
        ll t = i;
        while (t > 1)
        {
            bool a = 0;
            for (ll i = 1; i * i <= t; i++)
            {
                if (t % i == 0 && divs[i])
                {
                    a = 1;
                    divs[i]--;
                    div *= i;
                    t /= i;
                    break;
                }
                if (t % i == 0 && divs[t / i])
                {
                    a = 1;
                    divs[t / i]--;
                    div *= t / i;
                    t /= t / i;
                    break;
                }
            }
            if (!a) break;
        }
        cur *= i / div;
        cur %= MOD;

    }
    cout << cur << '\n';
    for (auto k = divs.begin(); k != divs.end(); k++) if (k->second != 0) cout << k->first << " " << k->second << '\n';
}



Measured memory_bytes: 46076
S = list(input())
N = len(S)


l = [0] * 2019
l[0] = 1
m = 1
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * m
    temp %= 2019
    l[temp] += 1
    m *= 10
    m %= 2019

ans = 0

for i in range(0, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

Measured memory_bytes: 10304
#include<bits/stdc++.h>
#include<cstring>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int           long long
#define umapii        unordered_map<int,int>
#define ps(x,y)       fixed<<setprecision(y)<<x // sets precision upto required digits
#define arr(a,n)      int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}
#define outarr(a,n)   for(int i=0;i<n;i++){cout<<a[i]<<" ";}
#define mod           1000000007
#define ff            first
#define big           1e15
#define ss            second
#define add           push_back
#define remove        pop_back
#define mapii         map<int,int>
#define large         *max_element
#define small         *min_element
#define pqi           priority_queue<int>
#define mpqi          priority_queue<int,vector<int>,greater<int>>
#define in(n)         int n;cin>>n;
#define w(t)          int t;cin>>t;while(t--)
#define vi            vector<int>
#define vivi          vector<vector<int>>
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>pbds;



int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output3.txt", "w", stdout);
#endif

    in(k);
    string s;
    cin >> s;
    if (s.size() <= k) {
        cout << s;
    } else {
        for (int i = 0; i < k; i++) {
            cout << s[i];
        }
        cout << "...";
    }
}


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

int N;

int main() {
  cin >> N;
  int P[N];
  int Q[N];
  for (int i = 0; i < N; i++) cin >> P[i];
  for (int i = 0; i < N; i++) cin >> Q[i];

  vector<vector<int>> p(0, vector<int>(N));

  vector<int> p_0(N);
  for (int i = 0; i < N; i++) p_0[i] = i+1;

  do {
    vector<int> p_i(0);
    for (int x : p_0) {
      p_i.push_back(x);
    }
    p.push_back(p_i);
  } while (next_permutation(p_0.begin(), p_0.end()));

  int a = 0;
  int b = 0;

  for (int i = 0; i < 50000; i++) {
    a++;
    bool same = true;
    for (int j = 0; j < N; j++) {
      if (p[i][j] != P[j]) {
        same = false;
      }
    }
    if (same) break;
  }

  for (int i = 0; i < 50000; i++) {
    b++;
    bool same = true;
    for (int j = 0; j < N; j++) {
      if (p[i][j] != Q[j]) {
        same = false;
      }
    }
    if (same) break;
  }

  cout << abs(a-b) << endl;

}

Measured memory_bytes: 3256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	

	
	
	
	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		int a[] = new int[5];
		int index = 0;
		for(int i=0;i<5;i++) {
			a[i] = s.nextInt();
			if(a[i]==0) {
				index = i+1;
			}
		}
		System.out.println(index);
	}
}

Measured memory_bytes: 35692
#include <stdio.h>

int main(void){

  int n;
  scanf("%d", &n);
  char a[n+1], b[n+1], c[n+1];
  scanf("%s %s %s", a, b, c);
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i] && b[i] == c[i]) {
      continue;
    } else if (a[i] == b[i] || b[i] == c[i] || c[i] == a[i]) {
      count++;
    } else {
      count += 2;
    }
  }
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

/*
using PAIR = pair<string, int>;
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA() cerr << "AAAAA" << endl
#define debug_() cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;

using Graph = vector<vector<int>>;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> vec(n);
    int MIN = 1001001001;
    int ans = 0;
    int ret;
    for (int i = 0; i < n; i++)
    {
        vec[i] = m + i;
        if (MIN > abs(vec[i]))
        {
            MIN = min(MIN, abs(vec[i]));
            ret = vec[i];
        }

        ans += vec[i];
    }
    cout << ans - ret << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,total=0;string s;
	cin>>n>>s;
	char c=s[0];
	for(int i=1;i<s.size();i++){
		if(s[i]!=c){ total++;c=s[i];} 
	}
	cout<<total+1;
	return 0;
}


Measured memory_bytes: 512
#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;

ll power(ll x,ll n){
    if(n==0) return 1;
    ll res=power(x*x%mod,n/2);
    if(n&1) res=res*x%mod;
    return res;
}

int main(){
  int k;
  string s;
  cin>>k>>s;
  int n=s.size();
  ll a[n+k+1];
  a[0]=1;
  rep(i,1,n+k+1) a[i]=a[i-1]*i%mod;
  ll b[n+k+1];
  b[0]=1;
  rep(i,1,n+k+1) b[i]=power(a[i],1e9+5);
  ll ans=0;
  rep(i,0,k+1){
    ans+=power(25,i)*a[n+k]%mod*b[i]%mod*b[n+k-i]%mod;
    ans%=mod;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 35652
#include <iostream>
#include <string>

int main() {
  std::string s;
  std::cin >> s;
  int cnt = 0;
  char c = 'A';
  for (auto &e : s) {
    if (e <= c) {
      cnt += 1;
    }
    c = e;
  }
  std::cout << cnt << std::endl;
}


Measured memory_bytes: 3180
import math

A, B, H, M = list(map(int, input().split()))

h_theta = -min(H, 12) * 30 + 90. - M * 0.5
m_theta = -M * 6 + 90.
h_theta = math.radians(h_theta)
m_theta = math.radians(m_theta)

#  print("theta: ", h_theta, m_theta)
h_x, h_y = A*math.sin(h_theta), A*math.cos(h_theta)
m_x, m_y = B*math.sin(m_theta), B*math.cos(m_theta)
#  print("h_pos: ", h_x, h_y)
ans = math.sqrt((h_x - m_x)**2 + (h_y - m_y)**2)

print(ans)

Measured memory_bytes: 62248
#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define int ll
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)3e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);
 
#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        



int a, b, c, cnt;
void solve(){
	cin >> a >> b >> c;
	while(cnt <= 100000000){
		if((a & 1) || (b & 1) || (c & 1)){
			printf("%d", cnt);
			return;
		}
		int A = a, B = b, C = c;
		a = (B + c) >> 1, b = (A + C) >> 1, c = (A + B) >> 1;
		cnt++;
	}
	puts("-1");
}
main () {
	int t = 1;
	//scanf("%d", &t);
	while(t--)
		solve(); 
}	    

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	//数列Aの長さ決定
	int N = sc.nextInt();
	int[] A = new int[N];
	for(int i = 0;i < N;i++){
	    A[i] = sc.nextInt();
	}
	int q = partition(A,0,N-1);
	System.out.print(A[0]+" ");
	for(int j = 1;j < N-1;j++){
	    if(j == q) {
		System.out.print("[");
		System.out.print(A[q]);
		System.out.print("] ");
	    }else{
		System.out.print(A[j]);
		System.out.print(" ");
	    }
	}
	System.out.println(A[N-1]);
	
    }
    public static int partition(int[] A,int p,int r){
	int temp1,temp2;
	int x = A[r];
	int i = p-1;
	for(int j = p;j <= r-1;j++){
	    if(A[j] <= x){
		//A[r]の値より小さかったらA[i]とA[j]を交換
		i = i+1;
		temp1 = A[i];
		A[i] = A[j];
		A[j] = temp1;
	    }
	    
	}
	temp2 = A[i+1];
	A[i+1] = A[r];
	A[r] = temp2;
	
	return i+1;

    }
    
}



Measured memory_bytes: 70540
<?php
  fscanf(STDIN, "%d", $n,);
 $arr = array_map('intval', explode(' ', trim(fgets(STDIN))));
 //print_r($arr);
$ans=0;
$t=$arr[0];
for($i=1;$i<$n;++$i){
  if($t>$arr[$i]){
  $ans=$ans+$t-$arr[$i];   
  $t=max($t,$arr[$i]);
  }else{   
    $t=max($t,$arr[$i]);
  }
}
echo $ans;

Measured memory_bytes: 37784
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a;
    string s;
    cin >> a >> s;
    if (a >= 3200) {
        cout << s << endl;
    } else {
        puts("red");
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n,a,b;
  scanf("%d%d%d",&n,&a,&b);
  int p[n];
  int i;
  for(i=0;i<n;i++){
    scanf("%d",&p[i]);
  }
  int q1 = 0;
  int q2 = 0;
  int q3 = 0;
  for(i=0;i<n;i++){
    if(p[i] <= a){
      q1++;
    }else if(b < p[i]){
      q3++;
    }else{
      q2++;
    }
  }
  int ans = q1;
  if(q2 < ans){
    ans = q2;
  }
  if(q3 < ans){
    ans = q3;
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>

using namespace std;

bool isOdd(int& n) {
	return n%2 == 1;
}

int main() {
	int N, A;
	cin>>N;
	int counter = 0;
	for(int i=0; i<N; i++) {
		cin>>A;
		if (A%2 == 1) {
			counter += 1;
		}
	}

	if (isOdd(counter)) {
		cout<<"NO"<<endl;
	}
	else cout<<"YES"<<endl;
}


Measured memory_bytes: 384
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
const int dx[8] = {1,1,1,-1,-1,-1,0,0};
const int dy[8] = {1,-1,0,1,-1,0,1,-1};
struct data
{
	int mask,x,y;
};
int n;
data next_state(int mask, int x, int y)
{
	int T = 0;
	mask |= (1 << (x*n+y));
	rep(i,n)
		rep(j,n)
		{
			int cnt = 0;
			rep(k,8)
			{
				int xx = i + dx[k];
				int yy = j + dy[k];
				if (xx < 0 || xx >= n || yy < 0 || yy >= n)
					continue;
				if (mask & (1 << (xx*n+yy)))
					cnt++;
			}
			if (mask & (1 << (i * n + j)))
			{
				if (cnt == 3 || cnt == 2)
					T |= 1 << (i * n + j);
			}
			else
			{
				if (cnt == 3)
					T |= 1 << (i*n+j);
			}
		}
	T &= ~(1 << (x * n + y));
	return (data){T, x, y};
}
bool dfs(data s, int dep)
{
	if (s.mask == 0)
		return true;
	if (dep == 0)
		return false;
	rep(i,8)
	{
		int xx = s.x + dx[i];
		int yy = s.y + dy[i];
		if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
		if (s.mask & (1 << (xx*n+yy)))
			continue;
		if (dfs(next_state(s.mask,xx,yy),dep-1))
			return true;
	}
	return false;
}
char c[10];
int main()
{
	for (; scanf("%d", &n), n;)
	{
		data s = {};
		rep(i,n)
		{
			scanf("%s", c);
			rep(j,n)
			{
				switch(c[j])
				{
					case '@': s.x = i, s.y = j; break;
					case '#': s.mask |= 1 << (i * n + j);break;
				}
			}
		}
		int ans = -1;
		rep(t,11)
			if (dfs(s, t))
			{
				ans = t;
				break;
			}
		printf("%d\n", ans);
	}
	return 0;
}

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

int main() {
  int a,b,c,k; cin >> a >> b >> c >> k;
  int score = 0;
  for (int i = 0; i < k; i++){
    if (a != 0){
      a--;
      score++;
    }
    else if (b != 0){
      b--;
    }
    else  if (c != 0){
      c--;
      score--;
    }
  }
  cout << score;
}

Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <vector>

int main() {
  std::string s;
  std::cin >> s;
  int n = s.size();
  long long ans = 1LL * n * (n + 1) / 2;
  std::vector<int> cnt(26, 0);
  for (int i = 0; i < n; ++i) cnt[s[i] - 'a']++;
  for (int i = 0; i < 26; ++i) ans -= 1LL * cnt[i] * (cnt[i] + 1) / 2;
  std::cout << ans + 1 << "\n";
  return 0;
}


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

int main(){
    int H,W,i,j;
    
    while(1){
        cin >> H >> W;
        for (i = 1;i <= H; i++ ){
            for(j = 1;j <= W; j++ ){
                if (i == 1 || i == H || j == 1 || j ==W){
                    cout << "#";
                }
                else {
                    cout << ".";
                }
            }
            cout <<'\n';
        }
        if (H == 0 && W == 0) break;
        cout <<'\n';
    }
    return 0;
}


Measured memory_bytes: 3068
x, y, h = [], [], []
n = gets.to_i
n.times do |i|
  x[i], y[i], h[i] = gets.split.map(&:to_i)
end


101.times do |i|
  101.times do |j|
    hereH = -1
    n.times do |k|
      if h[k] > 0
        if hereH == -1
          hereH = h[k] + (x[k] - i).abs + (y[k] - j).abs
        else
          if hereH !=  h[k] + (x[k] - i).abs + (y[k] - j).abs
            hereH = -2
            break
          end
        end
      end
    end
    if hereH == -2
      next
    end
    n.times do |k|
      if h[k] ==  0
        dist =  (x[k] - i).abs + (y[k] - j).abs
        if hereH > dist
          hereH = -2
        end

      end
    end
    if hereH == -2
      next
    end
    printf("%d %d %d\n", i, j, hereH)
    exit


  end
end

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

int abs(int x){ return x>=0?x:-x;}

int main() {
    int N, X;
    cin >> N >> X;
    int x[N], diff[N] = {0};
    REP(i, N){
        cin >> x[i];
        diff[i] = abs(x[i] - X);
    }
    sort(diff, diff + N);

	bool flag = true;
	while(flag){
	int amari = 0;
	    REP(i, N-1) {
	        if(diff[i+1]%diff[0]){
	        		amari++;
	        		break;
	        	}
	    }
	    if(amari) diff[0]--;
	    else flag = false;
    }
    
    cout << diff[0] << "\n";

}

Measured memory_bytes: 1024
import java.util.Scanner;

/**
 * Created by Reopard on 2014/05/06.
 */
public class Main {
    public static void main(String args[]){
        char direction;
        int N, M, robot_x, robot_y, distance, count;
        int x[] = new int[20];
        int y[] = new int[20];
        String line;
        Scanner sc = new Scanner(System.in);
        while(true){
            N = sc.nextInt();
            if(N == 0) break;
            for(int i = 0; i < N; i++){
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
            }
            M = sc.nextInt();
            count = 0;
            robot_x = 10;
            robot_y = 10;
            for(int i = 0; i < M; i++) {
                line = sc.next();
                direction = line.charAt(0);
                for(distance = sc.nextInt(); distance > 0; distance--) {
                    switch (direction) {
                        case 'N':
                            robot_y++;
                            break;
                        case 'E':
                            robot_x++;
                            break;
                        case 'S':
                            robot_y--;
                            break;
                        case 'W':
                            robot_x--;
                            break;
                        default:
                            System.exit(0);
                    }
                    for (int j = 0; j < N; j++) {
                        if (robot_x == x[j] && robot_y == y[j]) {
                            count++;
                            x[j] = -1;
                            y[j] = -1;
                        }
                    }
                }
            }
            if(count == N) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}

Measured memory_bytes: 32336
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(),x.end()
#define ceil(n, m) ((n / m) + ( n % m ? 1 : 0))
#define fast_IO  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file_in freopen("input.txt","r",stdin);
#define file_out freopen("output.txt","w",stdout);
#define file freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

int main(){
    //fast_IO;

    int a,b,c;
    cin >> a >> b >> c;
    if((a==5&&b==5&&c==7)||(a==5&&b==7&&c==5)||(a==7&&b==5&&c==5))
        cout << "YES\n";
    else cout << "NO\n";
    return 0;
}


Measured memory_bytes: 3640
A = list(map(int, input().split()))
b = [[0, 1], [2, 1], [2, 0]]
l = 0
n = []
for i, j in b:
	l = l + abs(A[j]-A[i])
	n.append(abs(A[j]-A[i]))
l = l - max(n)
print(l)

Measured memory_bytes: 3060
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int K;
    cin >> K;
    ll sum = 0;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= K; j++) {
            for (int k = 1; k <= K; k++) {
               sum += gcd(i, gcd(j, k));
            }
        }
    }    
    cout << sum << endl;
}


Measured memory_bytes: 3636
using System;

namespace abc141_a
{
    static class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();

            var ans = "Sunny";
            if (s == "Sunny")
            {
                ans = "Cloudy";
            }
            else if (s == "Cloudy")
            {
                ans = "Rainy";
            }
            else
            {
                ans = "Sunny";
            }
            Console.WriteLine($"{ans}");
        }
    }
}


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

int main() {
	vector<vector<int>> a(3, vector<int>(3));
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a.at(i).at(j);
		}
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (tmp == a.at(j).at(k)) {
					a.at(j).at(k) = 0;
				}
			}
		}
	}

	if (n < 3) {
		cout << "No" << endl;
		return 0;
	}
	int sum_diag = 0;
	for (int i = 0; i < 3; i++) {
		int sum_yoko = 0, sum_tate = 0;
		sum_diag += a.at(i).at(i);
		for (int j = 0; j < 3; j++) {
			sum_yoko += a.at(i).at(j);
			sum_tate += a.at(j).at(i);
			if (j == 2) {
				if (sum_yoko == 0 || sum_tate == 0) {
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
		if (i == 2) {
				if (sum_diag == 0) {
					cout << "Yes" << endl;
					return 0;
				}
			}
	}
	if (a.at(0).at(2) == 0 && a.at(1).at(1) == 0 && a.at(2).at(0) == 0) {
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  ll n, a;
  cin >> n >> a;
  if(a>=n%500){
    print("Yes");
  }
  else{
    print("No");
  }
}

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

int main() {
    string s;
    cin >> s;
    int N = s.size();
    int K;
    cin >> K;
    set<string> st;

    for (int i = 0; i <= N - 1; ++i) {
        string S = "";
        for (int j = 0; i + j <= N - 1 && j <= K; ++j) {
            S += s[i + j];
            st.insert(S);
        }
    }
    auto itr = st.begin();
    while (--K)
        ++itr;
    cout << *itr << endl;
}

Measured memory_bytes: 2176
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include <cassert>
    #include <cmath>
    #include<cstdint>

    #define INF 1e7
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;
    using Graph = vector<vector<int>>;
    using P = pair<int,int>;

    int main(){
        int a,b,c;cin>>a>>b>>c;
        cout<<max(c-a+b,0);
    }
    


Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
	int min = sc.nextInt();
	int max = sc.nextInt();
	int result = 0;
	for(int i = 1; i <= num; i++){
      	int j = i;
		int total = 0;
		while(j != 0){
			total = total + j %10;
			j = j/10;
		}

		if(min <= total && total <= max){
			result = result + i;
		}
	}
    	System.out.println(result);
  }
}

Measured memory_bytes: 25172
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <deque>
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}


#define INF 1e9+7
#define LLINF 1e18+7
const ll MOD=1e9+7;
const int N=500000;

main(){
    int n=in();
    ll x=in();
    ll res=in();
    ll ans=0;
    rep(i,n-1){
        ll now=in();
        ans+=max(now+res-x,0ll);
        res=min(max(0ll,x-res),now);
    }
    cout<<ans;
}


Measured memory_bytes: 256
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m, k = map(int, input().split())
ans = ((n-1)*n*(n+1)//6*m**2 + (m-1)*m*(m+1)//6*n**2) * comb(n*m-2, k-2)
print(ans%MOD)

Measured memory_bytes: 18804
#include<bits/stdc++.h>
namespace ZDY{
#define fir freopen("2.in","r",stdin)
#define ll long long
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define fur(i,x,y) for(i=x;i<=y;i++)
#define Fdr(i,x,y) for(int i=x;i>=y;i--)
#define in2(x,y) in(x),in(y)
#define in3(x,y,z) in2(x,y),in(z)
#define in4(a,b,c,d) in2(a,b);in2(c,d)
#define clr(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define fl(i,x) for(ll i=head[x],to;to=e[i].to,i;i=e[i].next)
#define inf 2147483647
}
namespace FAST{
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
#define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
namespace fib{char b[300000]= {},*f=b;}
inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}
inline void in(int &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}
namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}struct foce{~foce(){pob;fflush(stdout);}} _foce;namespace ib{char b[100];}
inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}inline void outn(ll x){out(x);pc('\n');}
inline void out(int x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}inline void outn(int x){out(x);pc('\n');}
inline char sc(){char c=gc;while(!(('A'<=c&&c<='Z')||('a'<=c&&c<='z')||('0'<=c<='9')))c=gc;return c;}
inline ll jdz(ll x){return x>0?x:-x;}
inline ll max(ll x,ll y){return x>y?x:y;}
}using namespace FAST;using namespace ZDY;using namespace std;
#define N 100100
struct qj{int l,r;}a[N];
inline bool cmp(qj x,qj y){if(x.l!=y.l)return x.l<y.l;else return x.r<y.r;};
int n,m,l,r,jl=-inf,jr=-inf,ans=0;
int main(){
	in2(n,m);
	Fur(i,1,m)in2(a[i].l,a[i].r);
	sort(a+1,a+m+1,cmp);
	Fur(i,1,m){
		l=a[i].l,r=a[i].r;
		if(l>=jr)ans++,jl=l,jr=r;
		else jl=max(jl,l),jr=min(r,jr);
	}
	outn(ans);
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long 
#define endl "\n"
#define all(x) (x).begin(),(x).end()
const int MOD = 1e9+7;
const int mxN = 2e5+3;

void solve(){
	int n;
	cin >> n;
	int q = n / 1000;
	if(n % 1000 != 0)q++;
	int tt = (1000 * q);
	int ans = tt - n;
	cout << ans << endl;
}

int32_t main(){
	IO;
	
	int nT = 1;
	//cin >> nT;
	for(int i = 1; i <= nT; ++i)
		solve();
	return 0;
}


Measured memory_bytes: 3656
while line = gets.chomp
  break if line == "-1 -1 -1"
  m,f,r = line.split(" ").map(&:to_i)
  if m == -1 or f == -1
    puts "F"
  elsif m + f >= 80
    puts "A"
  elsif m + f >= 65
    puts "B"
  elsif m + f >= 50 or (m + f >= 30 and r >= 50) 
    puts "C"
  elsif m + f >= 30
    puts "D"
  else
    puts "F"
  end
end

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

using namespace std;

int judge(vector <int> array, int n)
{
    for (int i = 0; i < n; i++){
        if (array.at(i) > i + 1 )
            return -1;   
    }
    return 1;
}

int find(vector <int> array, int n)
{
    int ans;
    for (int i = n - 1; i >= 0; i--){
        if (array[i] == i + 1){
            ans = i;
            break;
        }
    }
    return ans;
}

int main()
{
    int N;
    cin >> N;
    vector <int> b(N);
    vector <int> a(N,1);

    for (int i = 0; i < N; i++) cin >> b.at(i);

    for (int i = 0; i < N; i++){
        if (judge(b,N - i) == -1){
            cout << -1 << endl;
            return 0;
        }else{
            int ans = find(b,N - i);
            b.erase(b.begin() + ans);
            a.at(N - i - 1) = ans + 1;
        }
    }

    for (int i = 0; i < N; i++){
        cout << a.at(i) << endl;
    }
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {

    private static void dfs(int from, int to, long[] nodes, List<List<Integer>> list) {
        nodes[to] += nodes[from];
        for (int next : list.get(to)) {
            if (next == from) {
                continue;
            }
            dfs(to, next, nodes, list);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n - 1];
        int[] b = new int[n - 1];
        int[] p = new int[q];
        int[] x = new int[q];
        long[] nodes = new long[n + 1];
        for (int i = 0; i < n - 1; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        for (int i = 0; i < q; i++) {
            p[i] = sc.nextInt();
            x[i] = sc.nextInt();
            nodes[p[i]] += x[i];
        }

        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            List<Integer> la = list.get(a[i]);
            la.add(b[i]);
            list.set(a[i], la);
            List<Integer> lb = list.get(b[i]);
            lb.add(a[i]);
            list.set(b[i], lb);
        }

        dfs(0, 1, nodes, list);

        StringJoiner sj = new StringJoiner(" ");
        for (int i = 1; i <= n; i++) {
            sj.add(String.valueOf(nodes[i]));
        }
        System.out.println(sj.toString());
    }

}


Measured memory_bytes: 198228
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define NO "Miserable Hokusai!"
int main(){
  int n;
  cin >> n;
  for(int a = 0; a < n; a++){
    int g[2];
    cin >> g[0] >> g[1];
    vector<vector<long long> > ans(g[0]+1, vector<long long>(g[1]+1, 0));
    int p;
    cin >> p;
    vector<vector<bool> > v(g[0]+1, vector<bool>(g[1]+1, true));
    vector<vector<bool> > h(g[0]+1, vector<bool>(g[1]+1, true));
    int x1,x2,y1,y2;
    for(int i = 0; i < p; i++){
      cin >> x1 >> y1 >> x2 >> y2;
      if(x1 == x2)
        v[x1][max(y1,y2)] = false;
      else if(y1 == y2)
        h[max(x1,x2)][y1] = false;
    }

    for(int i = 0; i <= g[1]; i++)
      h[0][i] = false;
    for(int i = 0; i <= g[0]; i++)
      v[i][0] = false;

    for(int i = 0; i <= g[0]; i++){
      for(int j = 0; j <= g[1]; j++){
        if(i == 0 && j == 0){
          ans[i][j] = 1;
        }else if(!h[i][j] && !v[i][j]){
          ans[i][j] = 0;
        }else if(!h[i][j] && v[i][j]){
          ans[i][j] = ans[i][j-1];
        }else if(h[i][j] && !v[i][j]){
          ans[i][j] = ans[i-1][j];
        }else if(h[i][j] && v[i][j]){
          ans[i][j] = ans[i-1][j] + ans[i][j-1];
        }
      }
    }
    if(ans[g[0]][g[1]] == 0)
      cout << NO << endl;
    else
      cout << ans[g[0]][g[1]] << endl;
  }
}

Measured memory_bytes: 3084
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            final String s = reader.readLine();

            final String[] sl = s.split(" ");

            final Integer[] x = new Integer[sl.length];
            x[0] = Integer.parseInt(sl[0]);
            x[1] = Integer.parseInt(sl[1]);
            x[2] = Integer.parseInt(sl[2]);
            Arrays.sort(x);

            System.out.println(x[0] + x[1] == x[2] ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 23252
#include<iostream>

using namespace std;

int main(void)
{
  int n; cin>>n;
  int x=n;
  long long int sum=0;
  
  for(;x!=0;){
    sum+=(x%10);
    x/=10;
  }
  
  if(n%sum==0){puts("Yes");}
  else{puts("No");}
  return 0;
}

Measured memory_bytes: 256
// from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } }
// macro_rules! debug { ($x: expr) => () }

#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
    T: Iterator,
    T::Item: std::fmt::Display
{
    let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
    res.pop();
    res
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};
#[allow(unused_imports)]
use std::mem::swap;

fn main() {
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }
    
    input! {
        n: usize,
        t: usize,
        ct: [(usize, usize); n],
    }
    let ans = ct.iter().map(|&(a, b)| if b <= t {a} else {1000000}).min().unwrap();
    if ans == 1000000 {
        printfln!("TLE");
    } else {
        printfln!("{}", ans);
    }
}


Measured memory_bytes: 4352
// D - 3N Numbers
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VL = vector<ll>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define pq priority_queue

#define NMAX 100000
int N;
VL A(3*NMAX);

void f(VL &V, ll sign){
	V[0] = A[0];
	pq<int> que;
	que.push(sign*A[0]);
	rp(i, 1, 3*N){
		que.push(sign*A[i]);
		ll topA = 0;
		if(que.size() > N){
			topA = sign*que.top();
			que.pop();
		}
		V[i] += V[i-1] + A[i] - topA;
	}
}

int main(){
	cin>>N;
	int N3 = N*3;
	rp(i, 0, N3) cin>>A[i];

	VL F(N3), B(N3);
	f(F, -1L);
	reverse(A.begin(), A.begin()+N3);
	f(B, 1L);

	ll maxfb = LLONG_MIN;
	rp(i, 0, N+1){
		int f = N - 1 + i;
		int b = N3 - 1 - N - i;
		maxfb = max(maxfb, F[f]-B[b]);
	}
	cout<< maxfb <<endl;
}

Measured memory_bytes: 8180
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INF = 1001001001;
 
int main() {
  int n;
  cin >> n;
  vector<int> b(n-1);
  rep(i,n-1) cin >> b[i];
  vector<int> a(n,INF);
  rep(i,n-1) {
    a[i] = min(a[i], b[i]);
    a[i+1] = min(a[i+1], b[i]);
  }
  int ans = 0;
  rep(i,n) ans += a[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const long long INF=200000000000000;
double pi=3.141592653589793;

const int MOD = 1000000007;

long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	return gcd(a%b,b);
}

long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
long myPow(long long x, long long n, long long m=MOD){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

ll N,M;
vector<ll>A(106);

void batten(ll i,ll k){
	if(i==N)return;
	if((A[i]%k)>(A[i+1]%k)){
		swap(A[i],A[i+1]);
		batten(i+1,k);
		return;
	}else{
		batten(i+1,k);
		return;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll N,A,B;
	cin>>N>>A>>B;
	ll kaigai=1;
	ll num=0;
	for(int i=1;i<=N;i++){
		char p;
		cin>>p;
		bool a=false;
		if(p=='a' && num<A+B){
			a=true;
			num++;
		}
		if(p=='b' && num<A+B && kaigai<=B){
			a=true;
			num++;
			kaigai++;
		}
		if(a)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}



Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		int sec = scanner.nextInt();

		// ??????
		int h = sec / 3600;

		// ???
		int m = (sec - (3600 * h)) / 60;

		// ?§?
		int s = sec - (3600 * h) - (60 * m);

		System.out.println(h + ":" + m + ":" + s);
	}

}

Measured memory_bytes: 17328
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		string str = Console.ReadLine();
		int ans = 1;
		for(var i=0;i<N-1;i++){
			string s1 = str.Substring(i,1);
			string s2 = str.Substring(i+1,1);
			if(s1!=s2){
				ans++;
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 15328
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;
import std.ascii;


void main()
{
  int n, a, b;
  readf("%s %s %s\n", &n, &a, &b);
  writefln("%s %s", min(a, b), max(0, min(a, b) - (n - max(a, b))));
}


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

const int INF = 1 << 29;

int N, M, Tmax;
int G[400][400];
int order_dest[10000];
int dist[400][400];

int current_dest = 0, remaining_dist = 0, latest_order = -1;
int command[10000];

bool is_at_store() {
    return current_dest == 0 && remaining_dist == 0;
}

void search() {
    vector<int> dests;
    REP(t, Tmax) {

        if (remaining_dist > 0) {
            command[t] = current_dest;
            remaining_dist -= 1;
        }

        if (remaining_dist > 0) {
            continue;
        }

        if (is_at_store()) {
            for (int i = 0; i < dests.size(); ) {
                if (dests[i] == 0) {
                    swap(dests[i], dests[(int)dests.size()-1]);
                    dests.pop_back();
                } else {
                    i += 1;
                }
            }
            while (latest_order < t) {
                latest_order += 1;
                if (order_dest[latest_order] != 0) {
                    dests.push_back(order_dest[latest_order]);
                }
            }
        }

        if (is_at_store() && dests.empty())  {
            command[t] = -1;
            continue;
        }

        for (int i = 0; i < dests.size(); ) {
            if (dests[i] == current_dest) {
                swap(dests[i], dests[(int)dests.size()-1]);
                dests.pop_back();
            } else {
                i += 1;
            }
        }

        if (dests.empty()) {
            dests.push_back(0);
        }

        int mdest = -1;
        int mdist = INF;

        for (auto dest: dests) {
            int d = dist[current_dest][dest];
            if (d < mdist) {
                mdist = d;
                mdest = dest;
            }
        }

        int mdest2 = -1;
        int mdist2 = INF;

        REP(i, N) if (i != current_dest && G[current_dest][i] != INF) {
            int d = G[current_dest][i] + dist[i][mdest];
            if (d < mdist2) {
                mdist2 = d;
                mdest2 = i;
            }
        }

        command[t] = mdest2;
        remaining_dist = G[current_dest][mdest2];
        current_dest = mdest2;
    }
}

void warshall_floyd() {
    REP(i, N) REP(j, N) {
        dist[i][j] = G[i][j];
    }
    REP(i, N) REP(j, N) REP(k, N) {
        dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
    }
}

void input() {
    cin >> N >> M;
    REP(i, N) REP(j, N) {
        G[i][j] = i == j ? 0 : INF;
    }
    REP(i, M) {
        int u, v, d;
        cin >> u >> v >> d;
        --u, --v;
        G[u][v] = d;
        G[v][u] = d;
    }
    cin >> Tmax;
    REP(i, Tmax) {
        int n; cin >> n;
        if (n == 1) {
            cin >> n >> order_dest[i];
            order_dest[i] -= 1;
            //cerr << order_dest[i] << endl;
        }
    }
}

void output() {
    REP(t, Tmax) {
        cout << (command[t] == -1 ? command[t] : command[t] + 1) << "\n";
    }
}

int main() {
    input();
    warshall_floyd();
    search();
    output();
}

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

int main() {
	long n,m,x=0,k=1,l=0;
	cin>>n>>m;
	long a[m],b[m];
	vector<long>v(400010,0);
	for(int i=0;i<m;i++)cin>>a[i]>>b[i];
	for(int i=0;i<m;i++){
		if(a[i]==1){
		v.at(i)=b[i];
		x++;
		}
		if(b[i]==n){
			v.at(i)=a[i];
			x++;
		}
	}
	sort(v.begin(),v.end());
	for(int i=0;i<400009;i++){
		if(v.at(i)!=v.at(i+1)){
			k++;
		}
		if(v.at(i)==0){
			l++;
		}
	}
	if(k+l==400010)cout<<"POSSIBLE"<<endl;
	else{
		cout<<"IMPOSSIBLE"<<endl;
	}
	return 0;
}

Measured memory_bytes: 6528
#include <iostream>
using namespace std;
string s;
int main(){
	cin >> s;
	int n = s.length();
	bool flag = false;
	for (int i = 1; i < n; ++ i)
		if (s[i - 1] != s[n - i - 1]){
			flag = true;
			break;
		}
	if (s[0] == '0' || s[n - 1] == '1' || flag){
		cout << -1 << endl;
		return 0;
	}
	int last = 1, rt = 1, node_cnt = 1;
	for (int i = 2; i <= n; ++ i)
		if (s[i - 1] == '1'){
			cout << rt << " " << ++ node_cnt << endl;
			rt = node_cnt;
			for (int j = 1; j <= i - (last + 1); ++ j)
				cout << rt << " " << ++ node_cnt << endl;
			last = i;
		}
	cout << rt << " " << ++ node_cnt << endl;
}


Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std ;
#define endl '\n' 

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif

int main() 
{
	stack < int > st ;
	string s ;
	
	while(cin >> s){ 
		if(s[0] != '+' && s[0]  != '-' && s[0] != '*'){
			st.push(atoi(s.c_str())) ;
			//cout << atoi(s.c_str()) << endl ;
		}
		else if( s[0] == '+'){
			int a = st.top() ; st.pop() ;
			int b = st.top() ; st.pop() ;
			st.push(a + b) ;
		}
		else if(s[0] == '-'){ 
			int a = st.top() ; st.pop() ;
			int b = st.top() ; st.pop() ;
			st.push(b - a) ;
		}
		else if(s[0] == '*'){
			int a = st.top() ; st.pop() ;
			int b = st.top() ; st.pop() ;
			st.push(a * b) ;
		} 
	} 
	
	cout << st.top() << endl ;
	return 0 ;
}



Measured memory_bytes: 3172
//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;
 
//const long long INF = 1LL << 55;
 
#define itn int
#define endl '\n'
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define rrep(i,n) for(int i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define ioboost cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20)
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
 
#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int h,w,d;
vector<pair<int,int>> cost_map(310*310);
vector<int> tour_modd[310*310];
int main(void){
   ioboost;
   cin >> h >> w >> d;
   for(int i = 0;i < h;i++){
      for(int j = 0;j < w;j++){
         int a;cin >> a;
         a--;
         cost_map[a] = mp(i,j);
      }
   }
   for(int i = 0;i < d;i++){
      tour_modd[i].pb(0);
      for(int j = 1;i + d*j < h*w;j++){
         int next_x = cost_map[i + d*j].ff;
         int next_y = cost_map[i + d*j].ss;
         int prev_x = cost_map[i + d*(j-1)].ff;
         int prev_y = cost_map[i + d*(j-1)].ss;
         
         tour_modd[i].pb(tour_modd[i].back() + abs(next_x - prev_x) + abs(next_y - prev_y));
      }
   }
   
   int q;cin >> q;
   rep(i,q){
      int l,r;cin >> l >> r;
      l--,r--;
      int m = l % d;
      int idx_l = (l - m)/d;
      int idx_r = (r - m)/d;
      cout << tour_modd[m][idx_r] - tour_modd[m][idx_l] << endl;
   }
   
}

Measured memory_bytes: 6272