akhauriyash/Code-Regression huggingface dataset:
'use strict'

const main = arg => {
    var input = arg.trim().split("\n");
    var str = input[0];
    var count = parseInt(input[1], 10);
    var runs = input.slice(2, 2+count);
    runs.forEach(com => {
        const command = com.split(" ");
        const a = parseInt(command[1], 10);
        const b = parseInt(command[2], 10);
        switch(command[0]){
            case "replace":
                str = str.slice(0, a) + command[3] + str.slice(b+1, str.length);
                break;
            case "reverse":
                str = str.slice(0, a) + str.slice(a, b+1).split("").reverse().join("") + str.slice(b+1, str.length);
                break;
            case "print":
                console.log(str.slice(a, b+1));
                break;
        }
    });
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

int main(){

      int i ;
      char s[1100], hukusu1[] = "s" ;
      char hukusu2[] = "es";
      scanf("%s",s) ;
      i = strlen(s) ;
      if(s[i-1] == 's') 
            strcat(s, hukusu2) ;
      else 
              strcat(s, hukusu1) ;
      printf("%s", s) ;
      return 0 ;
}

Measured memory_bytes: 1732
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    a,b = map(int, input().split(' '))
    print(a*b if a < 10 and b < 10 else -1)
    pass

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
N, A, B = [int(_) for _ in input().split()]
S = input()

ca, cb = 0, 0
for s in S:
    if s == "a":
        if ca + cb < A + B:
            print("Yes")
            ca += 1
        else:
            print("No")
    elif s == "b":
        if ca + cb < A + B and cb < B:
            print("Yes")
            cb += 1
        else:
            print("No")
    else:
        print("No")


Measured memory_bytes: 4016
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

using VVL = vector< vector <long long> >;
using VP = vector < pair<long long, int> >;

long long solve(VVL& dp, VP& cho, int now, int used) {
    if (now == cho.size()) {
        return 0;
    }

    if (dp[now][used] >= 0) {
        return dp[now][used];
    }

    int N = cho.size();

    // to left
    // N-used-1 - left == N - now-1
    // left = now-used
    int left = now-used;
    long long gain = abs(left-cho[now].second) * cho[now].first;
    dp[now][used] = max(dp[now][used], solve(dp, cho, now+1, used) + gain);

    // to right
    int right = N-used-1;
    gain = abs(right-cho[now].second) * cho[now].first;
    dp[now][used] = max(dp[now][used], solve(dp, cho, now+1, used+1) + gain);

    return dp[now][used];
}

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

    vector <long long> A(N);
    VP cho(N);

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        cho[i] = make_pair(A[i], i);
    }

    sort(cho.begin(), cho.end(), greater<pair<long long, int>>());

    VVL dp(N+1, vector<long long>(N+1, -1));

    cout << solve(dp, cho, 0, 0) << endl;

    return 0;
}

Measured memory_bytes: 34936
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long ll;

int dx[9] = {1,1,0,-1,-1,-1,0,1};
int dy[9] = {0,-1,-1,-1,0,1,1,1};

class DSnukesColoring {
public:
	void solve(std::istream& cin, std::ostream& cout) {
		int h,w,n;cin >> h >> w >> n;
		map<pair<int,int>,int> m;
		for (int i = 0; i < n; ++i)
		{
			int a,b;cin >> a >> b;
			a--,b--;
			if(a>=1 and a < h-1 and b >= 1 and b < w-1)m[make_pair(a,b)]++;
			for (int j = 0; j < 8; ++j)
			{
				int nx = a + dx[j];
				int ny = b + dy[j];
				if(nx >= 1 and nx < h-1 and ny >= 1 and ny < w-1){
					m[make_pair(nx,ny)]++;
				}
			}
		}

		vector<int> cnt(10,0);
		ll all = (ll)(h-2)*(ll)(w-2);
//		cout << "all = " << all << endl;
		for(auto i : m){cnt[i.second]++;}
		for(int i = 1;i <= 9;i++){
			all -= (ll)cnt[i];
		}
		cout << all << endl;
		for (int i = 1; i <= 9; ++i)
		{
			cout << cnt[i] << endl;
		}

	}
};


int main() {
	DSnukesColoring solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 56448
#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    if(s.size()%2!=0){cout<<"No"<<endl;return 0;}
    for(int i=0;i<s.size();i++){
        if(i%2==0&&s[i]!='h'){cout<<"No"<<endl;return 0;}
        if(i%2==1&&s[i]!='i'){cout<<"No"<<endl;return 0;}
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int sex[1010]; // male 0 female 1
typedef long long ll;
int read(){
	char c = getchar();
	int res = 0,flag = 0;
	while((c<'0'||c>'9')&&c!='-')
		c = getchar();
	if(c=='-'){
		flag = 1; c = getchar();
	}
	while(c>='0'&&c<='9'){
		res = res*10+c-'0';
		c = getchar();
	}
	if(flag) sex[res] = 1;
	return res;
}

int main(){
	int n;
	cin >> n;
	ll res = 0;
	for(int i=1;i<=n;i++){
		if(i%3==0||i%5==0||i%15==0) continue;
		else res+= i;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>

using namespace std;

int main()
{
	int n,x;
	cin>>n>>x;
	int l[n];
	for (int i=0; i<n; i++)
		cin>>l[i];
	int bounce=1;
	int coor=0;
	for(int i=0; i<n; i++)
	{
		coor+=l[i];
		if (coor<=x)
			bounce++;
		else
			break;
	}
	cout<<bounce<<endl;

}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int cmpint(const void *x, const void *y) {
	return *(int *)x - *(int *)y;
}
int main() {
	int n, a[200000], num[200000] = {0};
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d", &a[i]);
		num[a[i] - 1]++;
	}
	qsort(a, n, sizeof(int), cmpint);
	for (int i = 0; i < n; i++) {
		printf("%d\n", num[i]);
	}
	return 0;
}

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

int main(){
    int n;
  	cin >> n;
    rep(i,9){
        rep(j,9){
            if(n == i*j){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  int offset = int('A' - 'a');
  string s;
  getline(cin, s);
  rep(i, s.size()){
    if('a' <= s[i] && s[i] <= 'z'){
      s[i] = char(s[i] + offset);
    }
  }
  cout << s << endl;
	return 0;
}



Measured memory_bytes: 3052
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define N 100005
int a[N],n;
char s[20];
int g(int x){
	printf("%d\n",x);
	fflush(stdout);
	scanf("%s",s+1);
	if(s[1]=='M')return 0;
	if(s[1]=='F')return 1;
	return -1;
}
int main(){
	scanf("%d",&n);
	int l=0,r=n;
	a[l]=a[r]=g(l);
	if(a[l]==-1)return 0;
	while(l+1<r){
		int mid=(l+r)>>1;a[mid]=g(mid);
		if(a[mid]==-1)return 0;
		if(((mid-l+1)&1)==(a[l]^a[mid]))r=mid;else l=mid;
	}
	return 0;
}

Measured memory_bytes: 852
import heapq

X,Y,Z,K = map(int, input().split())
A = [int(x) for x in  input().split()]
B = [int(x) for x in  input().split()]
C = [int(x) for x in  input().split()]

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

h = []

heapq.heappush(h, (-A[0]-B[0]-C[0], 0,0,0))

result = []
used = set()

for _ in range(K):
    value, i,j,k = heapq.heappop(h)
    result.append(-value)
    if i < X-1 and (i+1,j,k) not in used:
        heapq.heappush(h, (-A[i+1]-B[j]-C[k],i+1,j,k))
        used.add((i+1,j,k))
    if j < Y-1 and (i,j+1,k) not in used:
        heapq.heappush(h, (-A[i]-B[j+1]-C[k],i,j+1,k))
        used.add((i,j+1,k))
    if k < Z-1 and (i,j,k+1) not in used:
        heapq.heappush(h, (-A[i]-B[j]-C[k+1],i,j,k+1))
        used.add((i,j,k+1))
        
for v in result:
    print(v)

Measured memory_bytes: 5104
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    s = input().rstrip()
    count = 0
    for i in range(len(s)//2):
        if s[i]!=s[len(s)-1-i]:
            count += 1
    print(count)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
 
#define srep(s, i, n) for (size_t i = s; i < (size_t)n; ++i)

typedef int32_t i32;

using namespace std;
 
int main() {
  size_t n, k;
  cin >> n;
  k = 2;
  auto vec = vector<i32>(n);
  for (auto &x : vec) {
    cin >> x;
  }
 
  auto dp = vector<i32>(n, 0);
  srep(1, to, n) {
 
    auto min = INT32_MAX;
    srep((to < k ? 0 : to - k), from, to) {
      auto cost = abs(vec[to] - vec[from]);
      auto result = dp[from] + cost;
      if (result < min) {
        min = result;
      }
    }
    dp[to] = min;
  }
 
  cout << dp.back() << endl;
}


Measured memory_bytes: 1024
S = input()
T = input()
itch = 0
for i in range(len(S)-len(T)+1):
    tmp = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            tmp += 1
    itch = max(tmp, itch)
    tmp = 0
print(len(T)-itch)

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

#define stirng string
#define vvi vector<vector<int>>
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int inf = 1e9 + 7;

int main() {
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  if (s < t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;

static inline ll mod(ll x, ll m)
{
    ll y = x % m;
    return (y >= 0 ? y : y+m);
}

// }}}

int N, W;
int w[101], v[101];
ll dp[101][100001];

void solve()
{
    FOR (i, 1, N+1) {
        REP(j, W+1) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    cout << dp[N][W] << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> W;
    FOR (i, 1, N+1) cin >> w[i] >> v[i];
    solve();
    return 0;
}

// vim:set foldmethod=marker:


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

int main() {
  int H,W;
  cin >> H >> W;
  
  char c;
  
  for(int i=1;i<=H+2;i++){
    for(int j=1;j<=W+2;j++){
      if(i==1 || i==H+2 || j==1 || j==W+2){
        cout << "#";
      }
      else{
        cin >> c;
        cout << c;
      }
    }
    cout << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    // 文字を数値として扱う場合は定数として宣言しておくとよい。
    const int A=0,B=1,C=2,D=3,E=4;
    
    // 入力
    int time[5];
    for(int i=A; i<=E; i++)
        scanf("%d",&time[i]);
    
    // 全パターン計算。
    // あらかじめ最大値を持っておき、
    // より短いものが見つかるたび更新する。
    int ans=643;
    int i,j,k,m,l;
    for(i=A; i<=E; i++) // 1番目
    for(j=A; j<=E; j++) // 2番目
    for(k=A; k<=E; k++) // 3(以下略)
    for(l=A; l<=E; l++)
    for(m=A; m<=E; m++){
        // i,j,k,m,lにかぶりがあってはいけない。
        if(i==j||i==k||i==l||i==m||j==k||j==l||j==m||k==l||k==m||l==m) continue;
        
        int order[] = {i,j,k,m,l};
        
        // シミュレーション
        
        int waitingTime = 0;
        int arrived = -1;    // 今何番目の料理まで届いているか？
        
        // t:現在の時刻
        int t;
        for(t=0; t<=643; t++){
            // 最後まで届いていたら終わり。
            if(arrived==E) break;
            
            // 何も待っていなくて、時刻が10の倍数なら次の料理を注文する。
            if(waitingTime==0 && t%10==0)
                waitingTime = time[order[arrived+1]];
            
            // 待ち時間の更新
            if(waitingTime == 1) arrived++;
            if(waitingTime > 0) waitingTime--;
        }
        
        if(t < ans) ans=t;
    }
    
    printf("%d",ans);
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#include<map>
#include<cstring>

using namespace std;

typedef long long int ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vi vector<int>
#define vivi vector<vi>
const int INF = 1e9;
const ll LLINF = 1LL<<60;
/* -- template -- */
int dp[3001][3001];

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

    for(int s = 0;s < S.size();++s){
        for(int t = 0;t < T.size();++t){
            dp[s + 1][t + 1] = max(dp[s + 1][t], dp[s][t + 1]);
            if(S[s] == T[t])dp[s + 1][t + 1] = dp[s][t] + 1;
        }
    }
    int s = S.size(), t = T.size();
    string res = "";
    while(s > 0 && t > 0){
        if(dp[s - 1][t] == dp[s][t]){
            --s;
        }else if(dp[s][t - 1] == dp[s][t]){
            --t;
        }else{
            --s;
            --t;
            res = S[s] + res;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 35456
#include<stdio.h>
int main() {
  int h,count,x,y;
  
  
  while(1){
    count=0;
    scanf("%d %d",&x,&y);
    if(x<y)
      {
	h=x;
	x=y;
	y=h;
      }    

    if(x==0 && y==0){ break;}
    
    while(1)  /*Ã§ÂÂÃ£ÂÂ£Ã£ÂÂ¦Ã£ÂÂÃ¥Â Â´Ã¦ÂÂ is here*/
      {
	x=x%y;  /*Ã§ÂÂ*/

	h=x;   /*Ã§ÂÂ*/
	x=y;  /*Ã§ÂÂ*/
	y=h; /*Ã§ÂÂ*/
	
	if(y==0){break;}	
	count++;
      }
    
    
    printf("%d %d\n",x,(count+1));
  }
  return 0; 
}

Measured memory_bytes: 0
#include <bits/stdc++.h> 
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<int>>;

template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

int main(){
    int r,d;
    vector<int> x(11);
    cin>>r>>d>>x[0];
    for(int i=1;i<=10;++i){
        x[i]=x[i-1]*r-d;
        cout<<x[i]<<endl;
    }
}

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

class Stack{
	private:
		int sp;
		int S[200];
	public:
		Stack(){sp=0;}
		bool isFull() const{return (sp==200);}
		bool isEmpty() const{return (sp==0);}
		void push(int d);
		int top();
		void pop();
};
void Stack::pop(){
	if(isEmpty()){
		return;
	}
	sp--;
}
void Stack::push(int d){
	if(isFull()){
		return;
	}
	S[sp++]=d;
}
int Stack::top(){
	if(isEmpty()){
		return -1;
	}
	return S[sp-1];
}

int main(){
	Stack S;
	string str;
	getline(cin,str);
	for(int i=0;i<str.size();i++){
		int cnt=1;
		int tkr=i;
		int bai=0;
		int ati=0;
		int a=i;
		if(str[i]=='*'){
			int b=S.top();
			S.pop();
			int c=S.top();
			S.pop();
			S.push(b*c);
		}
		else if(str[i]=='+'){
			int b=S.top();
			S.pop();
			int c=S.top();
			S.pop();
			S.push(b+c);
			}
		else if(str[i]=='-'){
			int b=S.top();
			S.pop();
			int c=S.top();
			S.pop();
			S.push(c-b);
		}
		else{
				while(str[tkr+1]!=' '){
					cnt++;
					tkr++;
					i++;
				}
				while(cnt>=1){
					
					bai+=(str[a]-'0')*pow(10,cnt-1);
					cnt--;
					a++;
				}
			S.push(bai);
		}
		i++;
	}
	int ans=S.top();
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1220
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using Debug;
//using static System.Globalization.CultureInfo;
using System.Text;
class Program
{ 
    static void Main(string[] args)
    {
        Solve();
        //WriteLine(Solve());
    }
    static void Solve()
    {
        var ar = Input.arL;
        var res = ar[1];
        res += ar[0] / 2 * 2;
        res += ar[3] / 2 * 2;
        res += ar[4] / 2 * 2;
        res += 3 * ToInt32(ar[0]%2 == 1 && ar[3]%2 == 1 && ar[4]%2 == 1);
        var r = ar[1];
        if(ar[0]>0&&ar[3]>0&&ar[4]>0)
        { r += 3;ar[0]--;ar[3]--;ar[4]--; }
        r += ar[0] / 2 * 2;
        r += ar[3] / 2 * 2;
        r += ar[4] / 2 * 2;
        WriteLine(Max(res, r));
    }
}

public class Input
{
    public static string read => ReadLine().Trim();
    public static int[] ar => read.Split(' ').Select(int.Parse).ToArray();
    public  static int num => ToInt32(read);
    public static long[] arL => read.Split(' ').Select(long.Parse).ToArray();
    public  static long numL => ToInt64(read);
    public static char[][] gred(int h) 
        => Enumerable.Repeat(0, h).Select(_ => read.ToCharArray()).ToArray();
    public static int[][] ar2D(int num)
        => Enumerable.Repeat(0, num).Select(_ => ar).ToArray();
    public static long[][] arL2D(int num)
        => Enumerable.Repeat(0, num).Select(_ => arL).ToArray();
    public static T getValue<T>(string g)
    {
        var t = typeof(T);
        if (t == typeof(int))
            return (T)(object)int.Parse(g);
        if (t == typeof(long))
            return (T)(object)long.Parse(g);
        if (t == typeof(string))
            return (T)(object)g;
        if (t == typeof(char))
            return (T)(object)char.Parse(g);
        if (t == typeof(double))
            return (T)(object)double.Parse(g);
        if (t == typeof(bool))
            return (T)(object)bool.Parse(g);
        return default(T);
    }
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    bool used[110][110];
    rep(i,110)rep(j,110) used[i][j]=false;
    vector<P> cnt;
    vector<P> ans;
    if(n%2==0) FOR(i,1,n/2+1) cnt.push_back(P(i,n+1-i));
    else FOR(i,1,n/2+1) cnt.push_back(P(i,n-i));
    for(auto itr1:cnt)for(auto itr2:cnt){
        if(itr1==itr2) continue;
        int a=itr1.first,b=itr1.second,c=itr2.first,d=itr2.second;
        if(!used[a][c]){
          ans.push_back(P(a,c));
          used[a][c]=true;
          used[c][a]=true;
        }
        if(!used[a][d]){
          ans.push_back(P(a,d));
          used[a][d]=true;
          used[d][a]=true;
        }
        if(!used[b][c]){
          ans.push_back(P(b,c));
          used[b][c]=true;
          used[c][b]=true;
        }
        if(!used[b][d]){
          ans.push_back(P(b,d));
          used[b][d]=true;
          used[d][b]=true;
        }
      }
      if(n%2==0){
        cout<<len(ans)<<endl;
        for(auto itr:ans){
          cout<<itr.first<<' '<<itr.second<<endl;
        }
      }else{
        cout<<len(ans)+n-1<<endl;
        for(auto itr:ans){
          cout<<itr.first<<' '<<itr.second<<endl;
        }
        FOR(i,1,n){
          cout<<n<<' '<<i<<endl;
        }
      }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b,c,n,i,m=0,d;
    cin>>a>>b>>n;
    m=min(b-1,n);
    d=(a*m)/b-(a*(m/b));
    cout<<d<<endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 1; i <= (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
int main () {
    int x, y, z;
    cin >> x >> y >> z;
    cout << z << " "  << x <<  " " << y << endl; 

}

Measured memory_bytes: 3616
/*-------enazuma11----------------*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(v) v.begin(),v.end()
#define inc(a,n) sort(a,a+n)
#define dec(a,n) sort(a,a+n,greater<int>() )
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define F first
#define S second
#define M 1000000007
 
/* int x[]={-1,-1,0,1,1,1,0,-1};
int y[]={0,1,1,1,0,-1,-1,-1};
*/
/* int x[]={-1,0,1,0};
int y[]={0,1,0,-1};
*/

double dp[3005][3005];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		double a[n+1];
		ll i,j;
		rep(i,1,n+1)
		{
			cin>>a[i];
		}
		//double dp[n+1][n+1];
		dp[0][0]=1.0;
		rep(i,1,n+1)
		{
			dp[0][i]=(1-a[i])*dp[0][i-1];
			rep(j,1,i+1)
			{
				dp[j][i]=a[i]*dp[j-1][i-1]+(1-a[i])*dp[j][i-1];
			}
		}
		double ans=0.0;
		ll st=n/2;
		st+=1;
		rep(i,st,n+1)
		ans+=dp[i][n];
		cout<<fixed<<setprecision(9)<<ans<<'\n';
	}
	return 0;
}


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

string divide[4] = {"dream", "dreamer", "erase", "eraser"};

// 後ろから解く
// Greedy
int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    rep(i, 4) reverse(divide[i].begin(), divide[i].end());

    bool can = true;
    for (int i=0; i<s.size(); ) {
        bool can2 = false;
        rep(j, 4) {
            string d = divide[j];
            if (s.substr(i, d.size()) == d) {
                can2 = true;
                i += d.size();
            }
        }
        if (!can2) {
            can = false;
            break;
        }
    }
    if (can) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 3764
import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static int evalRPN(String input){
        int totalValue = 0;
        String operators = "+-*/";
        String inputArray[] = input.split(" ");
        Stack<String> stack = new Stack<>();

        for(String t : inputArray){
            if(!operators.contains(t)){
                stack.push(t);
            } else {
                int y = Integer.valueOf(stack.pop());
                int x = Integer.valueOf(stack.pop());
                switch (t){
                    case "+":
                        stack.push(String.valueOf(x + y));
                        break;
                    case "-":
                        stack.push(String.valueOf(x - y));
                        break;
                    case "*":
                        stack.push(String.valueOf(x * y));
                        break;
                    case "/":
                        stack.push(String.valueOf(x / y));
                        break;
                }
            }
        }
        return Integer.valueOf(stack.pop());
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String inputString = in.nextLine();

        System.out.println(evalRPN(inputString));

        in.close();
    }

}



Measured memory_bytes: 26080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
int n,p[200005],q[2][200005],l1,l2,r1,r2,m1[200005],m2[200005],k,kk,ans=1;bool s,o[200005];
void push1(int x){
    while(p[q[0][r1]]>=p[x]&&r1>=l1) r1--;
    q[0][++r1]=x;
}
void pop1(){l1++;}
void push2(int x){
    while(p[q[1][r2]]<=p[x]&&r2>=l2) r2--;
    q[1][++r2]=x;
}
void pop2(){l2++;}
int main()
{
    scanf("%d%d",&n,&k);kk=k-1;
    rep(i,1,n) scanf("%d",p+i);
    l1=l2=2;r1=r2=1;
    rep(i,1,kk) push1(i),push2(i);
    m1[kk]=p[q[0][l1]];m2[kk]=p[q[1][l2]];
    rep(i,kk+1,n){
        if(r1>=l1&&q[0][l1]<=i-kk) pop1();
        if(r2>=l2&&q[1][l2]<=i-kk) pop2();
        push1(i);push2(i);
        m1[i]=p[q[0][l1]];m2[i]=p[q[1][l2]];if(r1-l1+1==kk&&p[i-kk]<m1[i]) o[i]=1;
        //printf("%d %d %d\n",i,p[q[0][l1]],p[q[1][l2]]);
    }
    s=o[k];
    rep(i,k+1,n){
        //printf("%d ",o[i]);
        if(s&&o[i]) continue;
        s|=o[i];
        if(m1[i-1]<=p[i-k]||m2[i-1]>=p[i]) ans++;
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i;
    double count,a;
    cin>>n;
    count = 0;
    for(i=1;i<=n;i++)
    {
    
        scanf("%lf",&a);
        count = count + 1/a;
    }
    printf("%.5lf",1/count);
    return 0;
}

Measured memory_bytes: 256
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
LE = 1 << N
DP = [10**15]*(LE)
DP[0] = 0

for _ in range(M):
    a,b=LI()
    key = 0
    for i in LI():
        key |= 1<<(i-1)
    for j in range(LE):
        DP[j | key] = min(DP[j | key], DP[j] + a)

res = DP[(1 << N) - 1]
print(res if res != 10**15 else -1)


Measured memory_bytes: 47064
package main

import (
	"fmt"
)

func main() {
	var k int
	var s string
	fmt.Scanf("%d\n%s", &k, &s)
	answer := tripleDots(k, s)
	fmt.Println(answer)
}

func tripleDots(k int, s string) string {
	if k >= len(s) {
		return s
	}
	return s[:k] + "..."
}


Measured memory_bytes: 1816
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int n;
    cin >> n;
    set<string> st;
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        st.insert(s);
    }
    int ans = st.size();
    cout << ans << endl;
}

Measured memory_bytes: 19240
#include<bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(s[0] != s[1] || s[1] != s[2])
        cout<<"Yes\n";
    else
    {
        cout<<"No\n";
    }
    
}

Measured memory_bytes: 256
#%%
n, m = map(int, input().split())
a = list(map(int, input().split())) 

a[0] %= m
for i in range(1, n):
    a[i] += a[i-1]
    a[i] %= m
a.append(0)

count = {}
for i in range(n+1):
    count[a[i]] = 0
for i in range(n+1):
    count[a[i]] += 1

c = list(count.values())
ans = 0
for i in range(len(c)):
    tmp = c[i] * (c[i]-1) // 2
    ans += tmp
print(ans)

Measured memory_bytes: 14700
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define read(FILE)  freopen(FILE, "r", stdin);
#define out(FILE) freopen(FILE, "w", stdout);
#define clr(x, y) memset(x,y,sizeof(x));
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define rep(i, m, n) for(int i=m ; i<n ; i++)
#define forr(i, m, n) for(ll i=m ; i<=n ; i++)
#define endl '\n'
#define pb push_back
#define re return
const int N = 2e5 + 5;
const ll OO = 1e9+7;
using namespace std;
ll n;
ll arr[N];
ll dp[N][3];
ll knap1(ll i ,ll c)
{
    if(i>=n)
        return 0;
    if(dp[i][c]!=-1)
        return dp[i][c];
    if(c==0)
        return dp[i][c]=max(arr[i]+knap1(i+2,0),max(arr[i+1]+knap1(i+3,1),arr[i+2]+knap1(i+4,2)));
    if(c==1)
        return dp[i][c]=max(arr[i]+knap1(i+2,1),arr[i+1]+knap1(i+3,2));
    else
        return dp[i][c]=arr[i]+knap1(i+2,2);
}
ll knap(ll i ,ll c)
{
    if(i>=n)
        return 0;
    if(dp[i][c]!=-1)
        return dp[i][c];
    if(c==0)
        return dp[i][c]=max(arr[i]+knap(i+2,0),arr[i+1]+knap(i+3,1));
    else
        return dp[i][c]=arr[i]+knap(i+2,1);
}
int main()
{
    cin>>n;
    rep(i,0,n)
    {
        cin>>arr[i];
    }
    memset(dp,-1,sizeof(dp));
    ll sum=0;
    if(n%2==0)
        cout<<knap(0,0);
    else
        cout<<knap1(0,0);
    return 0;
}


Measured memory_bytes: 20808
sx, sy, tx, ty = map(int, input().split())

right1 = ["R" for _ in range(tx-sx)]
up1 = ["U" for _ in range(ty-sy)]
left1 = ["L" for _ in range(tx-sx)]
down1 = ["D" for _ in range(ty-sy)]
hoge = ["D"]
right2 = ["R" for _ in range(tx-sx+1)]
up2 = ["U" for _ in range(ty-sy+1)]
hoge2 = ["LU"]
left2 = ["L" for _ in range(tx-sx+1)]
down2 = ["D" for _ in range(ty-sy+1)]
hoge3 = ["R"]
print("".join(right1+up1+left1+down1+hoge+right2+up2+hoge2+left2+down2+hoge3))

Measured memory_bytes: 3432
def distance(s, c):
    return abs(s[0] - c[0]) + abs(s[1] - c[1])


def findshortest(s, checkpoints):
    shortest = 0
    for i in range(1, len(checkpoints)):
        if distance(s, checkpoints[i]) < distance(s, checkpoints[shortest]):
            shortest = i
    return shortest

n, m = map(int, input().split())
students = []
checkpoints = []
for _ in range(n):
    a, b = map(int, input().split())
    students.append((a, b))
for _ in range(m):
    c, d = map(int, input().split())
    checkpoints.append((c, d))

for s in students:
    print(findshortest(s, checkpoints) + 1)


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

int check ( int );

int main(void){
    int N,i,num;
    int result = 0;
    scanf( "%d" , &N );
    
    for( i = 0 ; i < N ; i++ ){
        scanf( "%d" , &num );
        if( check( num ) ){
            result++;
        };
    }
    printf( "%d\n" , result );
}

int check( int num ){
    int j,k,max;
    max = sqrt( num );
    for( j = 2 ; j <= max ; j++ ){
       for( k = j ; k <= max ; k+j ){
            if( ( num % k ) == 0 ) return 0;
            k += j;
       } 
    }
    return 1;
}


Measured memory_bytes: 2052
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			list.add(x);
		}
		List<Integer> temp = new ArrayList<>(list);
		Collections.sort(temp);
		int min = temp.get(n / 2 - 1);
		int max = temp.get(n / 2);
		for (int i = 0; i < n; i++) {
			if (list.get(i) <= min) {
				System.out.println(max);
			} else if (list.get(i) >= max) {
				System.out.println(min);
			}
		}
	}
}

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

using namespace std;

typedef long double ld;
typedef long long ll;

#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define f first
#define s second

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
typedef pair<int, int> pii;
typedef vector<int> vi;


template<typename T, typename U> bool ckmin(T &a, U b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool ckmax(T &a, U b){ return b > a ? a = b, true : false; }

const ll INF = 69696969;
const ll MOD = 2e5 + 3;

ll prod = 0;
int n;
//g[i] = 2^i, rg[i] = j s.t. 2^j = i
vector<double> poly, res;
vector<ll> g, rg;

typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vector<complex<long double>> R(2, 1);
	static vector<C> rt(2, 1);  // (^ 10% faster if double)
	for (static int k = 2; k < n; k *= 2) {
		R.resize(n); rt.resize(n);
		auto x = polar(1.0L, acos(-1.0L) / k);
		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
	}
	vi rev(n);
	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
		}
}
vd conv(const vd& a, const vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n);
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in);
	for (C& x : in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
	return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    n = 1;
    g.assign(MOD, INF);
    rg.assign(MOD, INF);
    for(int i = 0; i < MOD - 1; ++i){
        ckmin(g[i], n);
        ckmin(rg[n], i);
        n = (n * 2)%MOD;
    }
    cin >> n;
    poly.assign(MOD - 1, 0);
    for(int i = 0; i < n; ++i){
        ll x; cin >> x;
        if(!x) continue;
        // cout << rg[x] << "\n";
        poly[rg[x]]++;
        prod -= (x * x)%MOD;
    }
    res = conv(poly, poly);
    for(int i = 0; i < sz(res); ++i){
        prod += round(res[i]) * g[i%(MOD - 1)];
    }
    cout << (prod >> 1);
    return 0;
}

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

using namespace std;

void fastio() {
	cin.tie(nullptr);
	cin.sync_with_stdio(false);
}

using LL = long long;
using LD = long double;

const LL MOD = 998244353;
const LL INF = LLONG_MAX;
const LL N = 1e6+1;

#define F first
#define S second

int main() {
	fastio();
	
	LL n, x, m;
	cin >> n >> x >> m;

	vector<LL> next(m, -1);
	next[0] = 0;
	next[1] = 1;
	for (LL i = 2; i < m; ++i) {
		LL j = i;
		while (true) {
			LL nx = (j*j)%m;
			next[j] = nx;
			if (nx != -1) {
				break;
			} 
			else {
				j = (j*j) % m;
			}
		}
	}

	LL st = x, cst, sum = 0, len = 0, csum = 0, clen = 0;
	vector<LL> vis(m, 0);

	while (vis[st] == 0) {
		vis[st] = 1;
		len++;
		sum += st;
		st = next[st];
	}

	while (vis[st] == 1) {
		vis[st] = 2;
		clen++;
		csum += st;
		st = next[st];
	}

	LL nsum = sum - csum;
	LL nlen = len - clen;

	LL vst = x, vsum = 0;
	if (nlen > n) {
		for (LL i = 0; i < n; ++i) {
			vsum += vst;
			vst = next[vst];
		}
	}
	else {
		for (LL i = 0; i < nlen; ++i) {
			vsum += vst;
			vst = next[vst];
		}
		n -= nlen;
		vsum += (n/clen)*csum;
		n %= clen;
		for (LL i = 0; i < n; ++i) {
			vsum += vst;
			vst = next[vst];
		}
	}
	cout <<  vsum << "\n";

}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  
  ll ans = 0;
  int count = 0;
  while(true){
    ans += (ll)a[(count+1)/2];
    count++;
    if(count == n-1) break;
  }
  
  cout << ans << endl;
  return 0;
}

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

int A[2][110], dp[2][110];

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

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    dp[0][0] = A[0][0];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < N; j++) {
            if (i + 1 < 2) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + A[i + 1][j]);
            if (j + 1 < N) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + A[i][j + 1]);
        }
    }
    cout << dp[1][N - 1] << endl;

    return 0;
}

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

typedef struct{
  int time;
  bool inout;
} Data;

int main(){
  int n,m;
  while(cin>>n>>m,n){
    int r,q;
    Data data;
    vector<vector<Data> > vec(m);
    cin>>r;
    for(int i=0;i<r;i++){
      int t,pc,number,check;
      cin>>t>>pc>>number>>check;
      data.time=t;
      data.inout=(bool)check;
      vec[number-1].push_back(data);
    }
    cin>>q;
    for(int i=0;i<q;i++){
      int ts,te,number;
      cin>>ts>>te>>number;
      number--;
      int time=ts;
      int check=0;
      int sum=0;
      for(int i=0;i<(int)vec[number].size();i++){
	data = vec[number][i];
	if(data.inout) check++;
	else check--;
	if(ts <= data.time && data.time <= te){
	  if(data.inout && check == 1) time=data.time;
	  if(!data.inout&& check == 0){ 
	    sum += data.time-time;
	    time=data.time;
	  }
	}
	if(!data.inout && data.time > te){
	  sum+=te-time;
	  break;
	}
	if(check == 1 && data.inout && data.time > te) break;
      }
      cout<<sum<<endl;
    }
  }
  return 0;
}

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

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define Fix( x ) setprecision( x ) << fixed
#define mem( a , x ) memset( a , x , sizeof( a ) )
#define bug( a , b ) cerr<< #a <<" = "<<a<<" , "<< #b <<" = "<<b<<"\n";
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define FOR( i , a , b ) for( int i = a; i <= b; i++ )
#define ROF( i , a , b ) for( int i = a; i >= b; i-- )
#define sz( V ) (int)V.size( )
#define all( V ) V.begin( ),V.end( )
#define Found( S , val ) S.find( val ) != S.end( )
#define Unique( V ) sort( all( V ) ), V.erase( unique( all( V ) ), V.end() )
typedef pair < int , int > ii;
typedef pair < int , ii > iii;
typedef long long int LL;
typedef unsigned long long uLL;
const int inf = (int)1e9;
const LL INF = (LL)1e18;
const int N = 100005;
const int mod = 1000000007;
const double eps = 1e-8;
const double pi = acos( -1.0 );

LL a[ N ];


int main( int argc, char const *argv[] ) {
        fast_io;
        int n;
        cin >> n;
        FOR( i , 1 , n ) cin >> a[i];
        LL mx = 0;
        FOR( i , 1 , n ) {
            FOR( j , 1 , n ) {
                if( i != j ) mx = max( mx , abs(a[i]-a[j]));
            }
        }
        cout << mx << endl;
        return 0;
}








Measured memory_bytes: 896
import java.io.FileNotFoundException;
import java.util.Scanner;

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

//    	File file = new File("src/in.txt");

        //コード
//    	Scanner sc = new Scanner(file);
    	Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	String S = sc.next();
    	char[] c = S.toCharArray();
    	int numR = 0;
    	for(int i=0;i<S.length();i++) {
    		if(c[i]=='R') {
    			numR++;
    		}
    	}
    	if(numR==0) {
    		System.out.println(0);
    	} else {
    		int numR2 = 0;
    		for(int i=0;i<numR;i++) {
    			if(c[i]=='R') {
    				numR2++;
    			}

    		}
			int ans = numR - numR2;
			System.out.println(ans);
    	}

    }

}


Measured memory_bytes: 40736
"""
マスターオブ整数
"""

from collections import Counter
N, P = map(int, input().split())

# Pを素因数分解する
if N == 1:
    print(P)
    exit()

prime_list = []

for i in range(2, int(P**0.5) + 1):
    if P % i == 0:
        while P % i == 0:
            prime_list.append(i)
            P //= i
prime_count = Counter(prime_list)
ans = 1
for k,v in prime_count.items():
    if v >= N:
        ans *= k ** (v//N) 
print(ans)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(ll x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
template<class T>bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

const ll M = 100010;
ll fac[M];

void pr(ll ans){
    cout << ans << endl;
    exit(0);
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n, m;
    cin >> n >> m;
    if(abs(n-m) >= 2){
        pr(0);
    }
    ll f = 1;
    repr(i, 1, M){
        f *= i;
        f %= MOD;
        fac[i] = f;
    }
    ll ans = 1;
    if(n == m){
        ans *= fac[n];
        ans %= MOD;
        ans *= fac[n];
        ans %= MOD;
        ans *= 2;
        ans %= MOD;
    }else{
        ans *= fac[n];
        ans %= MOD;
        ans *= fac[m];
        ans %= MOD;
    }
    pr(ans);
    return 0;
}

Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N, P := ReadInt(), ReadInt()
	A := ReadInts(N)
	var evens, odds int
	for _, ai := range A {
		if ai%2 == 0 {
			evens++
		} else {
			odds++
		}
	}
	var p0 int
	if odds == 0 {
		p0 = 1 << N
	} else {
		p0 = 1 << (N - 1)
	}
	if P == 0 {
		fmt.Println(p0)
	} else {
		fmt.Println(1<<N - p0)
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1844
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << (x) << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

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

    const int power[14] = {0, 14, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

    OUT(power[a] == power[b] ? "Draw" : power[a]< power[b]? "Bob" : "Alice");

    return 0;
}



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


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        x,yを同じグループとしてまとめる
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


V, E = map(int, input().split())
edges = []
for _ in range(E):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    edges.append([a, b, w])

Un = UnionFind(V)

edges = sorted(edges, key=lambda x: x[2])
cost = 0
for s, g, w in edges:
    if not Un.same(s, g):
        Un.union(s, g)
        cost += w
print(cost)



Measured memory_bytes: 27060