akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main()
{
    bool cr = false, cg = false, cb = false;
    int n;
    long long ans = 0;
    string s;
    cin >> n >> s;
    int r[n + 1], g[n + 1], b[n + 1];
    r[0] = 0;
    g[0] = 0;
    b[0] = 0;
    for(int i = 0; i < n; i++)
    {
        r[i + 1] = r[i];
        g[i + 1] = g[i];
        b[i + 1] = b[i];
        if(s[i] == 'R')
        {
            r[i + 1]++;
        }
        else if(s[i] == 'G')
        {
            g[i + 1]++;
        }
        else
        {
            b[i + 1]++;
        }
    }
    for(int i  = 0; i < n - 2; i++)
    {
        if(s[i] == 'R')
        {
            cr = true;
        }
        else if(s[i] == 'G')
        {
            cg = true;
        }
        else
        {
            cb = true;
        }
        for(int j = i + 1; j < n - 1; j++)
        {
            if(s[i] != s[j])
            {
                if(s[j] == 'R')
                {
                    cr = true;
                }
                else if(s[j] == 'G')
                {
                    cg = true;
                }
                else
                {
                    cb = true;
                }
                if(!cr)
                {
                    ans += r[n] - r[j];
                    if(j + j - i < n && s[j + j - i] == 'R')
                    {
                        ans--;
                    }
                }
                else if(!cg)
                {
                    ans += g[n] - g[j];
                    if(j + j - i < n && s[j + j - i] == 'G')
                    {
                        ans--;
                    }
                }
                else
                {
                    ans += b[n] - b[j];
                    if(j + j - i < n && s[j + j -i] == 'B')
                    {
                        ans--;
                    }
                }
                if(s[j] == 'R')
                {
                    cr = false;
                }
                else if(s[j] == 'G')
                {
                    cg = false;
                }
                else
                {
                    cb = false;
                }
            }
        }
        if(s[i] == 'R')
        {
            cr = false;
        }
        else if(s[i] == 'G')
        {
            cg = false;
        }
        else
        {
            cb = false;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3656
import java.util.*;

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

		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String[] data = str.split(" ");
		double num[] = new double[data.length];
		for(int i = 0; i < data.length; i++){
			num[i] = Double.parseDouble(data[i]);
		}
	
		double a = num[0];
		double p = Math.PI;

		double kotae = (a * a * p) ;
		double kotae2 = (a * 2 * p);
		String hoge = String.format("%.6f",kotae);
		String hoge2 = String.format("%.6f",kotae2);
		System.out.println(hoge + " " + hoge2);
	}
}


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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int ans;

	if(n!=k) ans=1+((n-k)+(k-1)-1)/(k-1);
	else ans = 1;
	cout << ans << endl;
}



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

#define f first 
#define s second 
#define pb push_back               
#define all(x) x.begin(), x.end())

using namespace std;                    

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)1e5 + 123, mod = (int)1e9 + 7, inf = (int)1e9, LOG = 18;
const ll INF = (ll)1e8;
const double eps = 1e-9;

int n, a[N][3], val[N], pos[N], cnt[2];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i][0];
	for(int i = 1; i <= n; i++)
		cin >> a[i][1];
	for(int i = 1; i <= n; i++)
		cin >> a[i][2];
	
	for(int i = 1; i <= n; i++)
		if(max(a[i][0], max(a[i][1], a[i][2])) == a[i][1] || min(a[i][0], min(a[i][1], a[i][2])) == a[i][1] || max(a[i][0], max(a[i][1], a[i][2])) - min(a[i][0], min(a[i][1], a[i][2])) != 2 ||  (min(a[i][0], min(a[i][1], a[i][2])) - 1) / 3 % 2 == i % 2)
			cout << "No", exit(0);
	
	for(int i = 1; i <= n; i++){
    	int x = (min(a[i][0], min(a[i][1], a[i][2])) - 1) / 3; 
		if(min(a[i][0], min(a[i][1], a[i][2])) != a[i][0])
			cnt[i&1] ^= 1;
		val[i] = x + 1;
		pos[x + 1] = i;
	}

	for(int i = 1; i <= n; i++){
		if(val[i] == i)
			continue;
		
		int p = pos[i];
		int j = val[i];

		cnt[i&1^1] ^= 1;
		
		pos[i] = i;
		pos[j] = p;
		
		val[i] = i;
		val[p] = j;    
	}

	if(cnt[0]|cnt[1])
		cout << "No";
	else
		cout << "Yes";
}


Measured memory_bytes: 2176
n=int(input())
a=list(map(int,input().split()))
s=set(a)
print('YES' if len(s)==len(a) else 'NO')
# def has_duplicates(seq):
#   return len(seq) != len(set(seq))

# if has_duplicates(a) == True:
#   print('No')
# elif has_duplicates(a) == False:
#   print('Yes')

# # for i in range(n-1):
# #   if a[i] == a[i+1]:
# #     print('No')
# #     exit()

# # print('Yes')


Measured memory_bytes: 26808
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
arrA = np.array(input().split(),dtype=np.int64)

def check():
    temp = arrA % 2
    if 1 in temp:
        return False
    return True

ans = 0
while check():
    arrA = arrA // 2
    ans += 1

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


Measured memory_bytes: 12508
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr double INF{1e9};
constexpr int MAGIC_PRIME{1000000000 + 7};
constexpr array<int, 4> dy{-1, 1, 0, 0};
constexpr array<int, 4> dx{0, 0, -1, 1};
constexpr int div_ru(int a, int b)
{
    return (a - b + 1) / b;
}
ll pow_mod(ll b, ll e, ll m)
{ // https://atcoder.jp/contests/atc002/tasks/atc002_b
    ll r = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
    }
    return r;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b;
    cin >> a >> b;
    int ans = 0;
    if (a >= 13)
        ans = b;
    else if (a >= 6)
        ans = b / 2;
    else
        ans = 0;

    cout << ans << endl;

    return 0;
}
// 　　　　　　_......_
// 　　　　 , ´　 <＊y　♪
// 　　　　 i,（i ﾉﾉﾊ）_）
// 　　　　ﾉ_iﾊﾟ ヮﾟﾉﾊ
// 　　　 　 ,´i'_ｿﾉj,〈つ　))
// 　　　　〈_,ﾉ＾＾＾ヽ.´
// 　　　　 .＾＾i_ｿ_ｿ^´
// 　　　　 ￣￣ ￣　
// vector<vector<int>> mm(h, vector<int>(w, -1));


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

double max(double x, double y){
	return x > y ? x : y;
}

int main(){
	int n;
	cout << fixed << setprecision(8);
	cin >> n;
	vector<int> x(n);
	vector<int> y(n);
	double d1, d2, d3, d4;
	d1 = 0; d2 = 0; d3 = 0; d4 = 0;
	for (int i = 0; i < n; i++){
		cin >> x[i];
	}
	for (int i = 0; i < n; i++){
		cin >> y[i];
	}
	for (int i = 0; i < n; i++){
		d1 += abs(x[i] - y[i]);
		d2 += (x[i] - y[i]) * (x[i] - y[i]);
		d3 += abs((x[i] - y[i]) * (x[i] - y[i]) * (x[i] - y[i]));
		d4 = max(d4, abs(x[i] - y[i]));
	}
	cout << d1 << endl << sqrt(d2) << endl << pow(d3, 1.0 / 3) << endl << d4 << endl;
}


Measured memory_bytes: 3484
#include<stdio.h>

int main(){
  int x,y,i,min,gcd=1;
  scanf("%d%d",&x,&y);
  if(x>y)
    min = y;
  else min =x;

  i =2;
  while(min >= i){
    if(x%i == 0 && y%i ==0){
      x /= i;
      y /= i;
      min /= i;
      gcd *= i;
      continue;
    }
    i++;
  }
  printf("%d\n",gcd);
  return 0;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
int main(){
    int n;scanf("%d",&n);
    vector<int> a(3*n);for(int i=0;i<3*n;i++)scanf("%d",&a[i]);

    sort(a.begin(),a.end(),greater<int>());

    ll ans=0;
    //for(int i=0;i<3*n;i++)printf("%d ",a[i]);
    //printf("\n");
    for(int i=1;i<2*n;i+=2){
        ans+=a[i];
    }
    printf("%lld\n",ans);
    
}

Measured memory_bytes: 1408
package main

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

func main() {
	nextReader = newScanner()
	n := nextInt()

	m := map[string]struct{}{}
	for i := 0; i < n; i++ {
		s := nextString()
		m[s] = struct{}{}
	}
	fmt.Println(len(m))
}

// ---------------------------------------------------------------
// I/O
// ---------------------------------------------------------------
var nextReader func() string

func newScanner() func() string {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 1024), int(1e11))
	sc.Split(bufio.ScanWords)
	return func() string {
		sc.Scan()
		return sc.Text()
	}
}

func nextString() string { return nextReader() }

func nextInt() int { n, _ := strconv.Atoi(nextReader()); return n }

func nextInts(size int) []int {
	ns := make([]int, size)
	for i := 0; i < size; i++ {
		ns[i] = nextInt()
	}
	return ns
}


Measured memory_bytes: 14528
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int n,m,dgr[100111];
int main()
{
	get2(n,m);
	for(int i=1,u,v;i<=m;i++)
	{
		get2(u,v);
		dgr[u]++;
		dgr[v]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(dgr[i]%2==1)
		{
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

Measured memory_bytes: 640
m, f, r = map(int, input().split())

while not(m == -1 and f == -1 and r == -1):
	if m == -1 or f == -1:
		print("F")
	elif m + f >= 80:
		print("A")
	elif m + f >= 65:
		print("B")
	elif m + f >= 50:
		print("C")
	elif m + f >= 30:
		if r >= 50:
			print("C")
		else:
			print("D")
	else:
		print("F")
	m, f, r = map(int, input().split())


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

using namespace std;

int main()
{
	string str;
	int i;
	int count[26] = {};
	int num = 0;

	while (getline(cin, str)){

		for (i = 0; i < str.length(); i++)
		{
			if (islower(str[i])){
				num = str[i] - 'a';
				count[num]++;
			}
			else if (isupper(str[i])){
				str[i] = tolower(str[i]);
				num = str[i] - 'a';
				count[num]++;
			}

		}
	}

	for (i = 0; i < 26; i++)
	{
		cout << char(i + 'a') << " : " << count[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1184
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int x1, y1, x2, y2,x3, y3, x4, y4;
	cin >> x1 >> y1 >> x2 >> y2;
	x3 = x2 - (y2 - y1);
	y3 = x2 - x1 + y2;
	x4 = x3 - (y3 - y2);
	y4 = x3 - x2 + y3;
	cout << x3 <<" "<< y3<< " " << x4<< " " << y4<<endl;

}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
  char S[11];
  char H[11] = "2019/04/30";
  scanf("%s",&S);
  int i = 0;
  while (H[i])
  {

    if (H[i] < S[i])
    {
      printf("TBD");
      return (0);
    }
    else if (H[i] > S[i])
    {
      printf("Heisei");
      return(0);
    }
    i++;
  }
  printf("Heisei");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI arccos(-1)
#define rep(i, N) for (int i = 0; i < (N); i++)
#define REP(i, a, N) for (int i = a; i < (N); i++)
#define rrep(i, N, k) for (int i = (N); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - (int)1e8;
const ll INFLL = numeric_limits<ll>::max() - (ll)1e17;

int main() {
    int N;
    cin >> N;
    multiset<int> now;
    for (int i = 0; i < (1<<N); i++) {
        int S;
        cin >> S;
        now.insert(S);
    }
    bool check = true;
    vector<int> explore;
    explore.push_back(*now.rbegin());
    now.erase(next(now.end(), -1));
    while (!now.empty()) {
        vector<int> temp;
        for (auto ancestor : explore) {
            auto itr = now.lower_bound(ancestor);
            if (itr == now.begin()) {
                check = false;
                break;
            }
            itr--;
            temp.push_back(*itr);
            now.erase(itr);
        }
        if (!check) break;
        for (auto next : temp) explore.push_back(next);
    }
    cout << (check ? "Yes" : "No") << endl;
}

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


int n, l, r, q[100010], vis[100010];
vector <int> e[100010];

int main()
{
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
      
		cin >> u >> v;
      
		e[u].push_back(v), e[v].push_back(u);
	}
	l = 1, r = 0;
	vis[1] = 1; vis[n] = 2;
	q[++r] = 1; q[++r] = n;
	while (l <= r) {
		int u = q[l++];
		for (int v : e[u]) {			
			if (!vis[v]) {
				vis[v] = vis[u];
				q[++r] = v;
			}
		}
	}
	int sum1 = 0, sum2 = 0;
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 1)sum1++;
		else sum2++;
	}
  
	if(sum1 > sum2){
      cout << "Fennec" << endl;
    }
  
  else{
    cout << "Snuke" << endl;
  }

	
}


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

int main(){
  int W,H;
  cin>>W>>H;
  
  int x,y,r;
  cin>>x>>y>>r;

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


Measured memory_bytes: 3100
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;

int main (){
  int N;
  cin >> N;
  int C[N+1],S[N+1],F[N+1];
  for(int i=1;i<=N-1;i++){
    cin >> C[i] >> S[i] >> F[i];
  }
  int time = 0;
  for(int i=1;i<=N;i++){
    time=0;
    for(int j=i;j<=N-1;j++){
      if(time<=S[j]){
        time=S[j]+C[j];
        continue;
      }
      else{
        int machi=S[j];
        while(time>machi){
          machi+=F[j];
        }
      time =machi+C[j];
      }
    }
    cout << time << endl;
  }
  return 0;
}

Measured memory_bytes: 256
if __name__ == '__main__':
    from sys import stdin

    r, c = (int(n) for n in stdin.readline().split())

    table = []
    for _ in range(r):
        row = [int(n) for n in stdin.readline().split()]
        row.append(sum(row))

        print(" ".join(map(str, row)))
        table.append(row)
        
    sum_column = (sum(column) for column in zip(*table))
    print(" ".join(map(str, sum_column)))



Measured memory_bytes: 5680
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn f(a: u32) -> u32 {
    if a % 2 == 0 {
        a / 2
    } else {
        3 * a + 1
    }
}

fn main() {
    let s = read::<u32>();

    let mut v = vec![];
    let mut m = 1;
    let mut a = s;
    loop {
        if v.contains(&a) {
            break;
        } else {
            v.push(a);
        }

        a = f(a);
        m += 1;
    }
    println!("{}", m);
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>

using namespace std;

int N, M;

void solve()
{
	int t = M * 1900 + (N - M) * 100;
	cout << t * (1 << M) << endl;
}


int main()
{
	cin >> N >> M;
	solve();
	return 0;
}

Measured memory_bytes: 256
import sys
from collections import deque
readline = sys.stdin.readline

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

P = 10**9 + 7

ans = 0

for i in range(60):
    c = 0
    for a in A:
        c += ((a >> i) & 1)
    
    ad = c * (N - c) % P
    ans += ad * (1 << i)
    ans %= P

print(ans)


Measured memory_bytes: 123132
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> tree(200001);
int depth[200001];
int d_sum[2];

void dfs(int i, int j, int k);

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

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

	queue<int> q[3];
	for (int i = 1; i <= n; i++) {
		q[i % 3].push(i);
	}

	depth[1] = 0;
	dfs(1, 1, -1);

	for (int i = 1; i <= n; i++) {
		if (depth[i] % 2 == 1) {
			d_sum[1]++;
		}
		else {
			d_sum[0]++;
		}
	}

	vector<int> ans(n + 1);
	if (d_sum[0] > n / 3 && d_sum[1] > n / 3) {
		for (int i = 1; i <= n; i++) {
			if (depth[i] % 2 == 1) {
				if (!q[1].empty()) {
					ans[i] = q[1].front();
					q[1].pop();
				}
				else {
					ans[i] = q[0].front();
					q[0].pop();
				}
			}
			else {
				if (!q[2].empty()) {
					ans[i] = q[2].front();
					q[2].pop();
				}
				else {
					ans[i] = q[0].front();
					q[0].pop();
				}
			}
		}
	}
	else if (d_sum[0] <= n / 3) {
		for (int i = 1; i <= n; i++) {
			if (depth[i] % 2 == 0) {
				ans[i] = q[0].front();
				q[0].pop();
			}
			else {
				if (!q[1].empty()) {
					ans[i] = q[1].front();
					q[1].pop();
				}
				else if (!q[2].empty()) {
					ans[i] = q[2].front();
					q[2].pop();
				}
				else {
					ans[i] = q[0].front();
					q[0].pop();
				}
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (depth[i] % 2 == 1) {
				ans[i] = q[0].front();
				q[0].pop();
			}
			else {
				if (!q[1].empty()) {
					ans[i] = q[1].front();
					q[1].pop();
				}
				else if (!q[2].empty()) {
					ans[i] = q[2].front();
					q[2].pop();
				}
				else {
					ans[i] = q[0].front();
					q[0].pop();
				}
			}
		}
	}

	for (int i = 1; i < n; i++) {
		cout << ans[i] << " ";
	}
	cout << ans[n] << endl;

	return 0;
}

void dfs(int i, int j, int k)
{
	for (auto n : tree[i]) {
		if (n == k) {
			continue;
		}
		depth[n] = j;
		dfs(n, j + 1, i);
	}
}

Measured memory_bytes: 22144
#計算ミスあり最終スコアがtesterと異なる
import random
import time

def search(day, schedule, c, s, satisfy):
    score = 0
    date = [0] * 26
    for d in range(day):
        tmp = 0
        contest = 0
        nmax = -float('inf')
        for i in range(26):
            tmp += c[i] * (d + 1 - date[i])
        for i in range(26):
            tmp2 = s[d][i] - tmp + c[i] * (d + 1 - date[i])
            if nmax < tmp2:
                nmax = tmp2
                contest = i
        
        date[contest] = d + 1
        satisfy.append(tmp - c[contest] * (d + 1 - date[contest]))
        schedule.append(contest)
        score += s[d][contest] - satisfy[d]

    return score
    
# def decrease(day, schedule, c, s, satisfy):
#     ret = 0
#     date = [0] * 26

#     for d in range(day):
#         now = schedule[d] + 1
#         date[now - 1] = d + 1
#         tmp = 0
#         for i in range(26):
#             tmp += c[i] * (d+1 - date[i])
#         ret += tmp
#         satisfy.append(tmp)

#     return ret

def change(_from, _to, schedule, c, s, satisfy):
    ret = 0
    date = [0] * 26

    for d in range(_to):

        now = schedule[d] + 1
        date[now - 1] = d + 1
        if d < _from:
            ret += satisfy[d]
            continue

        tmp = 0
        for i in range(26):
            tmp += c[i] * (d+1 - date[i])
        ret += tmp
        satisfy[d] = tmp

    return ret

def Main():
    D = int(input())
    c = list(map(int, input().split()))
    s = [list(map(int, input().split())) for _ in range(D)]
    
    dissatisfy=[]
    schedule = []
    ans = search(D, schedule, c, s, dissatisfy)
    for i in range(D):
        print(schedule[i] + 1)


if __name__ == "__main__":
    Main()

Measured memory_bytes: 9800
n = int(input())
p_lst = list(map(int,input().split()))
p_lst_s = sorted(p_lst)
cnt = 0
for i in range(n):
	if p_lst[i] != p_lst_s[i]:
		cnt += 1


print("YES" if cnt == 2 or cnt == 0 else "NO")


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


int main(){
    int x[4],y[4];
    cin >> x[0] >> y[0] >> x[1] >> y[1];
    cout << x[1] + y[0] - y[1] << " " << y[1] + x[1] - x[0] << " " << x[0] + y[0] - y[1] << " " << y[0] + x[1] - x[0];
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void max_self(long long& a, long long b){
	a = max(a, b);
}
int main(){
	int n, W; cin >> n >> W;
	vector<long long> dp(W+1);
	for(int i = 0; i < n; i++){
		int weight, value; cin >> weight >> value;
		for(int weight_already = W-weight; weight_already >= 0; --weight_already){
			max_self(dp[weight_already+weight], dp[weight_already]+value);
		}
	}
	cout << *max_element(dp.begin(), dp.end());
	return 0;
}


Measured memory_bytes: 4048
#include<bits/stdc++.h>
#define INFTY 1000000000
#define N 500000
using namespace std;
int num=0,n=0;
vector<int> a(N,0),L(N/2+2,0),R(N/2+2,0);

void merge(vector<int> &a,int left,int mid,int right){
	int n1 = mid - left;
	int n2 = right - mid;
	//vector<int> L(n1),R(n2);
	
	for(int i=0;i<n1;i++) L.at(i) = a.at(left+i);
	for(int i=0;i<n2;i++) R.at(i) = a.at(mid+i);
	
	L.at(n1) = INFTY;
	R.at(n2) = INFTY;
	//L.push_back(INFTY);
	//R.push_back(INFTY);

	int j=0,i=0;
	for(int k=left;k<right;k++){
		num++;
		if(L.at(i) <= R.at(j)){
			a.at(k) = L.at(i);
			i++;
		}else{
			a.at(k) = R.at(j);
			j++;
		}
	}
}

void mergeSort(vector<int> &a,int left,int right){
	int mid;
	if(left+1 < right){
		mid = (left+right)/2;
		//mergeSort(left,mid);
		mergeSort(a,left,mid);
		//mergeSort(mid,right);
		mergeSort(a,mid,right);
		//merge(left,mid,right);
		merge(a,left,mid,right);
	}
}

int main(){
	int i=0;
	cin >> n;
	for(i=0;i<n;i++) cin >> a.at(i);
	//mergeSort(0,n);
	mergeSort(a,0,n);
	
	for(i=0;i<n;i++){
		if(i == n-1) cout << a.at(i) << endl;
		else cout << a.at(i) << " ";
	}

	cout << num << endl;
}



Measured memory_bytes: 6628
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n,k,m; string s,t;
char maze[60][60];
int dis[101][101];
int nm[8][8];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
int main() {
	cin >> n;
	ll res = 1LL;
	rep(i, n) {
		ll t;
		cin >> t;
		res = lcm(res, t);
	}
	
	cout << res << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		checked = new boolean[n + 1];
		
		calcIndex(0, 1, n);
		
		String[] tmpArray = br.readLine().split(" ");
		
		int p = 0;
		int q = 0;
		
		for(int i = 0; i < n; i++) {
			p += Integer.parseInt(tmpArray[i]);
			p *= 10;
		}
		p /= 10;

		tmpArray = br.readLine().split(" ");
		
		for(int i = 0; i < n; i++) {
			q += Integer.parseInt(tmpArray[i]);
			q *= 10;
		}
		q /= 10;
		
//		System.out.println(p+" "+q);
		System.out.println(Math.abs(map.get(p) - map.get(q)));
	}
	
	static boolean checked[];
//	static final int fact[] = {1,1,2,6,24,120,720,5040,40320};
	static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	static int index = 0;
	
	static void calcIndex(int num, int depth, int n) {
		if(depth == n + 1) {
//			System.out.println("add "+num+" as "+index);
			map.put(num, index);
			index++;
		}
		
		for(int i = 1; i <= n; i++) {
			if(!checked[i]) {
				checked[i] = true;
				calcIndex(num*10 + i, depth + 1, n);
				checked[i] = false;
			}
		}
	}

}


Measured memory_bytes: 23812
#ABC131D
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
l=sorted(l,key=lambda x:x[1])
deadline=0
tmp=0
for i in range(n):
    tmp=l[i][1]
    deadline+=l[i][0]
    if tmp<deadline:
        print("No")
        exit()
print("Yes")


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

using namespace std;
int N, K;
vector<int> p;
int main(){
    cin >> N >> K;
    cin.ignore();
    int tmp;
    for(int i = 0;i < N; i++){
        cin >> tmp;
        p.push_back(tmp);
    }
    cin.ignore();

    sort(p.begin(), p.end());
    long long sum = 0;
    for(int i = 0; i < K; i++){
        sum += p[i];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>

using namespace std;

int main(){
  int a,b,c,d,e,k;
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  cin >> e;
  cin >> k;
  if (e-a <= k){
    cout <<"Yay!"<<endl;
  }else{
    cout <<":("<<endl;
  } 
}

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

int main(void){
	int n, k;
	cin >> n >> k;
	long long x = n/k, y, ans=0;
	if(x*k+k/2<=n) y = x+1;
	else y = x;
	ans += pow(x,3)+pow(y,3)*((k+1)%2);
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

#define N 100

int data[N],num1,num2;

bool flag=false;

bool solve(int i,int m){

  if(i>num1) return false;
  else if(m<0) return false;
  if(m== 0 || m-data[i] == 0){
    flag=true;
    return true;
  }

  else{
    solve(i+1,m);
    solve(i+1,m-data[i]);
  }   
}

int main(){

  int i,m;


  cin >>num1;

  for(i=0;i<num1;i++){
    cin >>data[i];
  }

  cin >>num2;

  for(i=0;i<num2;i++){
    cin >>m;
    flag=false;

    solve(0,m);
    if(flag==true){
      cout <<"yes"<<endl;
    }  
    else cout <<"no"<<endl;
  }

  return 0;
}

Measured memory_bytes: 856
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.container;
import std.array;
import std.math;
import std.range;
import std.typecons;
import std.ascii;
import std.format;

void main()
{
  auto a = readln.chomp.split.map!(to!int);
  writeln = a[0] ^ a[1] ^ a[2];
}


Measured memory_bytes: 380
#include <iostream>
#include <string>
#include <algorithm>
#include <map>

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

    std::map<std::string, int> m;

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        std::string s;
        std::cin >> s;

        std::sort(s.begin(), s.end());

        ans += m[s]++;
    }
    std::cout << ans << "\n";
}

Measured memory_bytes: 11136
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<fstream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;

int main()
{
    int a,b,c,d;
    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
    {
        if(b<=c||d<=a) printf("0\n");
        else printf("%d\n",min(b,d)-max(a,c));
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int N,M,d;
  bool c=true;
  string s,list[256];

  cin >> N;
  for(int i=0;i<N;i++){
    cin >> list[i];
  }
  cin >> M;
  for(int i=0;i<M;i++){
    d = 0;
    cin >> s;
    for(int j=0;j<N;j++){
      if(list[j]==s){
	if(c == true){
	  c = false;
	  d = 1;
	  cout << "Opened by " << s << endl;
	}else{
	  c = true;
	  d = 1;
	  cout << "Closed by " << s << endl;
	}
      }
    }
    if(d==0){
      cout << "Unknown " << s <<endl;
    }
  }
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll PS(ll x) {
    ll a=1;
    rep(i,x) {
      a*=2;
    }
    return a;
  }

int main() {
  
      
ll H;
  cin >>H;
  ll count=0;
  if(H==1) {
    cout<<1<<endl;
  }
  else if(H!=1) {
    while(H>1) {
      H=floor(H/2);
      count++;
    }
    //cout<<count<<"A"<<endl;
    ll x=0;
    rep(i,count) {
      x+=PS(i);
    }
    
    ll y=PS(count);
    ll z=x+y;
    cout<<z<<endl;
  }
   
  
}
    
 

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if(n==5||n==3||n==7)
		puts("YES");
	else
		puts("NO");
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

int main() {
	long long int n=0,m,a,b,c,d,e;
	long double z,w;
	string str,str2,str3;
	char ch;
	long long int x[130]={};
	cout << fixed << setprecision(10);
	cin>>str;
	if(str[0]==str[2]){cout<<"Yes";}
	else{cout<<"No";}





	cout<<endl;
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],b[2005][2005],s[2005],f;char c[2005][2005];
int main()
{
    scanf("%d%d",&n,&m);f=max(n,m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=c[i][j]=='.'?0:1;
    for(int i=1;i<n;i++) for(int j=1;j<m;j++) a[i][j]=a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1];
    for(int i=1;i<n;i++) for(int j=1;j<m;j++) b[i][j]=(b[i-1][j]+(a[i][j]==0))*(a[i][j]==0);
    for(int i=1,t=0;i<n;i++,t=0) for(int j=1;j<=m;s[++t]=j,j++) while(b[i][j]<=b[i][s[t]]&&t) f=max(f,(j-s[t-1])*(b[i][s[t]]+1)),t--;
    printf("%d\n",f);
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    int N;
    cin >> N;
    cout << N/2+N%2;
    return 0;
}


Measured memory_bytes: 256
l = []
for i in range(50000):
  n = int(input())
  if n == 0:
    break
  else:
    A = list(map(int,input().split()))
    for i in range(n):
      for j in range(i+1,n):
        l.append(abs(A[i]-A[j]))
    print(min(l))
    l.clear()


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

int main(){

 int first_num;
 int second_num;

 for(first_num = 1 ; first_num <= 9 ; first_num++){
   for(second_num = 1 ; second_num <= 9 ; second_num++){
     cout << first_num << "x" << second_num << "=" << first_num * second_num << endl;
   }
 }
 return 0;
}

Measured memory_bytes: 3068
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,A,B = map(int, readline().split())

    if A == 0:
        print(0)
        exit()
        
    m = N // (A + B)
    ans = m * A

    N -= m * (A + B)

    if N >= A:
        ans += A
    else:
        ans += N
    
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  ll t1, t2;
  cin >> t1 >> t2;
  ll a1, a2;
  cin >> a1 >> a2;
  ll c1 = a1*t1, c2 = c1 + a2*t2;
  ll b1, b2;
  cin >> b1 >> b2;
  ll d1 = b1*t1, d2 = d1 + b2*t2;
  ll x1, x2, y1, y2;
  if(c1 < d1){
    x1 = c1; x2 = c2;
    y1 = d1; y2 = d2;
  }else{
    x1 = d1; x2 = d2;
    y1 = c1; y2 = c2;
  }
  cerr << y1 << " " << x1 << " : " << x2 << " " << y2 << endl;
  ll h = y1 - x1;
  ll s = x2 - y2;
  if(s < 0) cout << 0 << endl;
  else if(s == 0)cout << "infinity" << endl;
  else if(h % s == 0) cout << h/s*2 << endl;
  else cout << 1 + h/s*2 << endl;
  return 0;
}

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

template<class T>
ostream& operator<<(ostream& os,vector<T> const& v){for(auto itr=v.begin();itr!=v.end();++itr){if(itr!=v.begin())os<<' ';os<<*itr;}return os;}

signed main(){

  int n;
  cin>>n;
  vector<int> a(n);
  iota(a.begin(),a.end(),1);
  do{
    cout<<a<<endl;
  }while(next_permutation(a.begin(),a.end()));

}


Measured memory_bytes: 3104
using System;

public class hello
{
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var correct = line[0];
            var anser = line[1];
            if (correct == "0" && anser == "0") break;
            var hit = 0;  var blow = 0;
            for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++)
                    if (correct[i] == anser[j])
                        if (i == j) hit++;
                        else blow++;
            Console.WriteLine("{0} {1}", hit, blow);
        }
    }
}

Measured memory_bytes: 9132
#!/usr/bin/env python3
import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    deq = deque([-1])

    for i in range(N):
        index = bisect_left(deq,A[i])
        if index == 0:
            deq.appendleft(A[i])
        else:
            deq[index-1] = A[i]
    print(len(deq))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 8048
#include "iostream"
using namespace std;

int winner(int A, int B) {
	while (1) {
		if (A > B) {
			A = A - B;
		}
		else {
			return A;
		}
	}
}
int main()
{
	int N = 0;//??\????????°
	int K[1000];//???????????°
	int P[1000];//????????°
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> K[i] >> P[i];
	}
	for (int i = 0; i < N; i++) {
		cout << winner(K[i], P[i])<<endl;
	}
    return 0;
}

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

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

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

int main2() {
  int N; cin >> N;
  string S; cin >> S;
  int Q; cin >> Q;
  vector<int> ks(Q);
  REP(i, Q) cin >> ks[i];

  for (int k : ks) {
    ll ans = 0;
    ll D = 0;
    ll M = 0;
    ll co = 0;
    REP(i, N) {
      if (i-k >= 0) {
        if (S[i-k] == 'D') {
          D--;
          co -= M;
        } else if (S[i-k] == 'M') {
          M--;
        }
      }

      if (S[i] == 'D') {
        D++;
      }
      else if (S[i] == 'M') {
        M++;
        co += D;
      }
      else if (S[i] == 'C') {
        ans += co;
      }
    }
    cout << ans << endl;
  }

  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 1412
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    h = []
    for i, ai in enumerate(a):
        h.append([i, ai])
    h.sort(key=lambda x: x[1])
    ans = " ".join([str(i + 1) for i, _ in h])
    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 27616
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if(abs(C - A) <= D){
    cout << "Yes" << endl;
  }
  else if(abs(C - B) <= D && abs(B - A) <= D){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

int main() {
  int A11,A12,A13,A21,A22,A23,A31,A32,A33,N;
  cin >> A11 >> A12 >> A13;
  cin >> A21 >> A22 >> A23;
  cin >> A31 >> A32 >> A33;
  cin >> N;
  vector<int> b(N);
  for(int i=0;i<N;i++){
    cin >> b.at(i);
    if(b.at(i)==A11){
      A11=0;
    }
    if(b.at(i)==A12){
      A12=0;
    }
    if(b.at(i)==A13){
      A13=0;
    }
    if(b.at(i)==A21){
      A21=0;
    }
    if(b.at(i)==A22){
      A22=0;
    }
    if(b.at(i)==A23){
      A23=0;
    }
    if(b.at(i)==A31){
      A31=0;
    }
    if(b.at(i)==A32){
      A32=0;
    }
    if(b.at(i)==A33){
      A33=0;
    }
  }
  if((A11==0 && A12==0 && A13==0)||(A21==0 && A22==0 && A23==0)||(A31==0 && A32==0 && A33==0)){
    cout << "Yes" << endl;
  }
  else if((A11==0 && A21==0 && A31==0)||(A12==0 && A22==0 && A32==0)||(A13==0 && A23==0 && A33==0)){
    cout << "Yes" << endl;
  }
  else if((A11==0 && A22==0 && A33==0)||(A13==0 && A22==0 && A31==0)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


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

using namespace std;

#define maxn l005
#define ll long long

vector<string> v;

int vis[60][30];
int sum[30];

int main() {
	int n;
	scanf("%d", &n);
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.size(); j++) {
			vis[i][str[j] - 'a']++;
		}
	}

	for (int j = 0; j < 26; j++) {
		sum[j] = 100;
		for (int i = 1; i <= n; i++) {
			sum[j] = min(sum[j], vis[i][j]);
		}
	}

	for (int i = 0; i < 26; i++)
		for (int j = 1; j <= sum[i]; j++)
			cout << (char)('a' + i);

	puts("");
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;

#define pll pair<ll,ll>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define rep(i,n) for (int i = 0; i < n; ++i) 
#define REP(i,k,n) for (int i = k; i <= n; ++i) 
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
#define sz(a) int((a).size())
#define endl '\n' // remove for interactive

const int INF = 1e9;
const ll mod = 998244353;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

const int N = 2e5+25;

long long BIT[N];
int n;

void update(int x, int delta){
      for(; x <= n; x += x&-x)
      {
            BIT[x] = (BIT[x] + delta + mod) % mod;
      }
}

long long query(int x){
     long long sum = 0;
     for(; x > 0; x -= x&-x)
        sum = (sum + BIT[x]) % mod;
     return sum;
}




void solve()
{
    
    int k; cin>>n>>k;
    // vi v;
    vpii vp;
    rep(i, k) {
        int x; cin>>x; int y; cin>>y;
        vp.pb({x, y});
    }
    // sort(all(vp));
    // int sez = unique(all(v)) - v.begin();
    // v.resize(sez);
    // watch(sz(v));
    update(1, 1);
    update(2, -1);
    // watch(n);
    // watch(sz(vp));
    REP(i, 1, n) {
        for(auto x: vp) {
            int str = x.F+i;
            int end = x.S+i;
            if(str > n) continue;
            end = min(n, end);
            
            ll curr = query(i);
            // watch(curr);
            update(str, curr);
            update(end+1, -curr);
        }
    }
    cout<<query(n)%mod;
}

int main()
{
    // clock_t start, end;
    // start = clock();
    ios_base::sync_with_stdio(0); //cant use scanf, printf
    cin.tie(0);cout.tie(0); // no longer auto flush cout before each cin, remove for interactive
    int t = 1;
    // cin>>t;
    REP(i, 1, t)
    {
        solve();
        
    }
    // end = clock();
    // double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    // watch(time_taken);
    ll x = INF; x++;
    return 0;
    
}



/*before sub
TEST: 0(1 by 1 too), 1, equal, -ve, bounds(random and ez)
ERR/WA: loop vars, out of bounds, endl, finish taking inputs, large doubles, larger INF, corr mod, t, early/late mod
RE: double dec, integer overflow(ll or 1LL mult)
*/





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

#define ios  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n;

int main() {
    ios;

    ll n;
    cin>>n;
    ll arr[n+2][3];
    for(ll i=1;i<=n;i++)
    {
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    ll dp[n+2][3]={0};

     for(ll i=n;i>=1;i--)
     {
         for(ll j=0;j<3;j++)
         {
           dp[i][j]=max(arr[i][j]+dp[i+1][(j+1)%3],arr[i][j]+dp[i+1][(j+2)%3]);
         }
     }
    ll ans=max(dp[1][0],max(dp[1][1],dp[1][2]));
     cout<<ans;
     return 0;
}


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

constexpr int INF = 1 << 30;

int N, a[200009];
vector<int> G[200009];
int dp[200009];
int ans[200009];

void dfs(int v, int p) {
    int *it = lower_bound(dp, dp + N, a[v]);
    swap(*it, a[v]);

    ans[v] = lower_bound(dp, dp + N, INF) - dp;

    for(int u : G[v])
        if(u != p) dfs(u, v);

    swap(*it, a[v]);
}

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    for(int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    fill(dp, dp + N, INF);

    dfs(1, -1);

    for(int i = 1; i <= N; i++)
        cout << ans[i] << endl;

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<ll> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
        v[i] -= i + 1;
    }
    sort(v.begin(), v.end());
    ll median = (n % 2 == 0) ? v[n / 2 - 1] : v[(n + 1) / 2 - 1];
    ll ans = 0;
    for(ll x:v) ans += abs(x - median);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
//Brick Break

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <map>
#include <stdio.h>
#include <string.h>
#include <initializer_list>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <set>

using namespace std;

int main()
{
    int N;
    vector<int> A;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        A.push_back(x);
    }

    int x = 1;
    for (int i = 0; i < N; i++) {
        if (A[i] == x) {
            x++;
        }
    }
    cout << ((x==1) ? -1 : (N + 1 - x)) << endl;
    return 0;
}

Measured memory_bytes: 1400
#include<iostream>
using namespace std;
int main()
{
  string S,T;
  cin>>S>>T;
  bool flag = false;
  for(int i=0;i<T.size();i++){
    auto itr=T.end()-1;
    T=*itr+T;
    T.erase(T.end()-1);
    if(S==T){
      flag=true;
      break;
    }
  }
  cout<<((flag)? "Yes":"No");
}

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

int main(void)
{
   char a[11],b[11],c[11];

   scanf("%s%s%s",a,b,c);

   if( a[strlen(a)-1] == b[0] && b[strlen(b)-1] == c[0] ) printf("YES\n");
   else                                                   printf("NO\n");

   return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    int n, k;
    cin >> n >> k;
    if (k == 1)
        cout << 0 << endl;
    else
    {
        int ans = 0;
        ans = n - k;
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  string O,E;
  cin >> O >> E;
  int P = O.size();
  int F = E.size();
  for(int i=0;i<P;i++)
  {
    if(P==F)
    {
      cout << O[i] << E[i];
    }
    else
    {
      if(i!=F)
      {
        cout << O[i] << E[i];
      }
      else
      {
        cout << O[i];
      }
      
    }
    
  }
  return 0;
}

Measured memory_bytes: 384
$a=($h=Hash[15,2244,12,1870,10,1520,5,850,3,550,2,380]).dup
def f n;$a[n]||=n<1?1e9:$h.map{|k,v|f(n-k)+v}.min;end
while 0<n=gets.to_i/100;p f(n)end

Measured memory_bytes: 6112
using namespace std;

#include <bits/stdc++.h>

int main()
{
	int N; cin>>N;
  	int A[N] = {0};

  	int aux;
  	for(int i=0;i<N-1;i++)
    {
      	cin>>aux; ++A[aux-1];
    }
  	for(int i=0;i<N;i++) cout<<A[i]<<"\n";
}


Measured memory_bytes: 4416
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
 
using namespace std;
 
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
 
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
 
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
 
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
 
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


vector<vector<int>> G;

void dfs(int v,vector<bool> &visited,int &res ){
  bool end = true;
  rep(i,visited.size()) if(!visited[i] && i != v) end = false;
  if(end){
    res++;
    return;
  }

  visited[v] = true;
  for(auto nv : G[v]){
    if(visited[nv]) continue;
    dfs(nv,visited,res);
  }
  visited[v] = false;
  
}

int main(){
  int N,L;
  cin >> N >> L;
  int ans = 0;
  int dif = inf;
  for(int i = 1; i<= N; i++){
    ans += L+i-1;
    dif = min(dif,abs(L+i-1));
    
  }
  if(L+N-1 < 0) cout << ans + dif << endl;
  else cout << ans - dif << endl;
}

  
                           

                                                          






Measured memory_bytes: 256
s = list(input())
s_r = s[::-1]

count=0
i=0
while("".join(s) != "".join(s_r)):
    
    if (s[i] != s_r[i]) and i<len(s):
        s[i] = s_r[i]
        s_r = s[::-1]
        count+=1
    i+=1
print(count)

Measured memory_bytes: 3060