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

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

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

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

  int n, y;
  cin >> n >> y;

  lint ans = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n - i; j++) {
      lint total = 10000 * i + 5000 * j + 1000 * (n - i - j);
      if (y == total) {
        cout << i << " " << j << " " << n - i - j << endl;
        return 0;
      }
    }
  }
  cout << -1 << " " << -1 << " " << -1 << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define pb push_back
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define endl "\n"
#define pii pair<int,int>
#define mii map<int,int>
#define int long long int
#define fbo find_by_order
#define ook order_of_key
#define in insert
#define F first
#define S second
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a) for(auto ws: a)cout<<ws<<" "; cout<<endl
#define print1(a,b) for(int ws=0;ws<b;ws++) {cout<<a[ws]<<" ";} cout<<endl
#define all(a) a.begin(), a.end()
#define si set<int>
#define print2(a) for(auto ws: a)cout<<"("<<ws.F<<","<<ws.S<<") "; cout<<endl

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
    const char* comma = strchr (names + 1, ',');
    cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
int cache[3001][3001];
// int dp(string s, string t, int i, int j)
// {
//     if (i == s.size())return 0;
//     if (j == t.size())return 0;
//     int &ans = cache[i + 1][j + 1];
//     if (ans != -1)return ans;
//     if (s[i] == t[j])
//     {
//         return ans = 1 + dp(s, t, i + 1, j + 1);
//     }
//     else
//     {
//         return ans = max(dp(s, t, i + 1, j), dp(s, t, i, j + 1));
//     }
// }
void dp(string s, string t)
{
    int n = s.size();
    int m = t.size();
    int dp[n + 1][m + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (i == 0 || j == 0)dp[i][j] = 0;
            else if (s[i - 1] == t[j - 1])
            {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    string ans;
    for (int j = t.size(), i = s.size(); j >= 1  && i >= 1;)
    {
        if (s[i - 1] == t[j - 1])
        {
            ans += s[i - 1];
            i--, j--;
        }
        else if (dp[i - 1][j] > dp[i][j - 1])i--;
        else j--;
    }
    reverse(all(ans));
    cout << ans << endl;

}
void solve()
{
    memset(cache, -1, sizeof(cache));
    string s, t;
    cin >> s >> t;
    dp(s, t);


}
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt",  "r",  stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout << setprecision(9) << fixed;
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 144320
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <iomanip>

using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){

    ll N;
    cin >> N;

    vector<ll> v(N);
    for(int i = 0; i < N; i++) cin >> v[i];

    ll INF = 1e10;
    vector<ll> dp(N, INF);
    dp[0] = 0;

    for(int i = 1; i < N; i++){
        if(i - 2 >= 0){
            dp[i] = min( dp[i-1] + abs( v[i] - v[i-1] )  ,dp[i-2] + abs( v[i] - v[i-2] ) ) ;
        }
        else{
            dp[i] = dp[i-1] + abs( v[i] - v[i-1] ) ;
        }
    }
    
    cout << dp[N - 1] << endl;


}

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

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int data[10][10]={ 	{1,0,2,0,1,1,1,1},
					{1,0,2,1,0,1,1,1},
					{1,0,2,1,1,0,1,1},
					{1,0,2,1,1,1,0,1},
					{1,0,2,1,1,1,1,0},
					{0,1,2,0,1,1,1,1},
					{0,1,2,1,0,1,1,1},
					{0,1,2,1,1,0,1,1},
					{0,1,2,1,1,1,0,1},
					{0,1,2,1,1,1,1,0},
				};

int main(){
	string n;
	int fie[8][5];
	bool f=false;
	while(cin>>n){
		if(f)cout<<endl;
		else f=true;
		rep(i,5)rep(j,8){
			fie[j][i]=data[0][j];
		}
		int len = n.size();

		for(int i=5-len;i<5;i++){
			rep(j,8){
				fie[j][i]=data[n[i-(5-len)]-'0'][j];
			}
		}
		rep(i,8){
			rep(j,5){
				if(fie[i][j]==1){
					cout<<'*';
				}else if(fie[i][j]==2){
					cout<<'=';
				}else cout<<' ';
			}
			cout<<endl;
		}
	}
}

Measured memory_bytes: 1172
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int N, M;
vector<int> p;
vector<string> S;
bool found[100001];
bool ac[100001];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  p.resize(M);
  S.resize(M);
  for (int i = 0; i < M; i++) {
    int pi;
    string Si;
    cin >> pi >> Si;
    pi--;
    if (Si == "AC") {
      found[pi] = true;
    }
    p[i] = pi;
    S[i] = Si;
  }

  int ans = 0;
  int penalty = 0;
  for (int i = 0; i < M; i++) {
    if (!ac[p[i]] && found[p[i]]) {
      if (S[i] == "AC") {
        ans++;
        ac[p[i]] = true;
      } else {
        penalty++;
      }
    }
  }

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

Measured memory_bytes: 6272
package main

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

var sc = bufio.NewScanner(os.Stdin)

func swap(a int64, b int64) (int64, int64) {
	return b, a
}

func gcd(a int64, b int64) int64 {
	if b > a {
		a, b = swap(a, b)
	}
	if b == 0 {
		return a
	} else {
		return gcd(a%b, b)
	}
}

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

func min(nums ...int64) int64 {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int64(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int64) int64 {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int64(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func nextLong() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func nextByte() byte {
	sc.Scan()
	s := sc.Bytes()
	return s[0]
}

func main() {
	sc.Split(bufio.ScanWords)
	//ans := 1
	N := nextInt()
	M := nextInt()
	var s [5]int
	var c [5]byte
	for i := 0; i < M; i++ {
		s[i] = nextInt()
		c[i] = nextByte()
	}
	ans := -1
	mn := 1
	mx := 10
	ok := true
	for i := 0; i < N-1; i++ {
		mn *= 10
		mx *= 10
	}
	if N == 1 {
		mn = 0
	}
	for i := mn; i < mx; i++ {
		num := strconv.Itoa(i)
		ok = true
		for j := 0; j < M; j++ {
			if num[s[j]-1] != c[j] {
				ok = false
			}
		}
		if ok == true {
			ans = i
			break
		}
	}
	//ans := int64(math.Ceil(float64(N)/float64(minnum)) + 4)
	fmt.Printf("%d\n", ans)
}


Measured memory_bytes: 1776
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <cstdlib>
#include <stack>

using namespace std;

typedef long long LL;
typedef double db;
#define FAST ios::sync_with_stdio(false);
const int MaxN = 105;
char chang(char x)
{
	if(x <= 'Z' && x >= 'A')x = x;
	else x = x - 32;
	return x;
	}
int main()
{
	string a , b , c;
	cin >> a >> b >> c;
	char x , y , z;
	x = a[0];
	y = b[0];
	z = c[0];
	x = chang(x);
	y = chang(y);
	z = chang(z);
	cout << x << y << z << endl;
	return 0;
	}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var nx = Array.ConvertAll(ReadLine().Split(' '), long.Parse);
        WriteLine(dfs(nx[1], nx[0]));
    }
    private static long dfs(long x,long level)
    {
        if (level == 0) return ToInt64(x > 0);
        var bab = (long)Pow(2, level + 2) - 3;
        if (x < (bab + 1) / 2)
            return dfs(x-1, level - 1);  
        else if (x > (bab + 1) / 2)
            return (long)Pow(2, level) + dfs(x - (bab + 1) / 2, level - 1);
        else return (long)Pow(2, level);
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


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

vector<string> maze(60);
vector<vector<int>> d(60,vector<int>(60,-1));
int h,w;

struct P {
  int y,x;
};
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

void bfs() {
  queue<P> Q;
  Q.push({0,0});
  d[0][0]=0;
  P now;
  while(!Q.empty()) {
    now=Q.front(); Q.pop();
    for(int i=0;i<4;i++) {
      int ny=now.y+dy[i];
      int nx=now.x+dx[i];
      if(ny>=0&&ny<h&&nx>=0&&nx<w&&d[ny][nx]==-1&&maze[ny][nx]=='.') {
        Q.push({ny,nx});
        d[ny][nx]=d[now.y][now.x]+1;
      }
    }
  }
}

int main() {
  cin>>h>>w;
  int white=0;
  for(int i=0;i<h;i++) {
    cin>>maze[i];
    for(int j=0;j<w;j++) {
      if(maze[i][j]=='.') white++;
    }
  }
  bfs();
  if(d[h-1][w-1]==-1) cout<<-1;
  else cout<<white-d[h-1][w-1]-1<<endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
using ll = long long;

int main()
{
    long double a,b, h, m;
    cin >> a >> b >> h >> m ;
    
    long double x1, y1, x2 , y2, d;
    long double e, f ,g;
    long double pi= 3.141592653589;
    g = 60.0;
    h +=  m/g;
    e = 2.0;
    f = 12.0;
    
    x1 = a * cosl(e*pi*h/f);
    y1 = a * sinl(e*pi*h/f);
    x2 = b * cosl(e*pi*m/g);
    y2 = b * sinl(e*pi*m/g);

    d = powl((x1 - x2),e) + powl((y1 - y2),e);
    d = sqrtl(d);
    printf("%.20Lf",d);
    
    return 0;
}


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

int main() {
  int x,y,a1,a2,a3,a4;
  cin >> x >> y;

  a1=x+y;
  a2=x+x-1;
  a3=y+y-1;
  
  if (a1 < a2) {
    if (a2 < a3) {
      cout << a3;
    }else{
      cout << a2;
    }
  }else{
     if (a1 < a3) {
      cout << a3;
    }else{
      cout << a1;
    }
  }

}

Measured memory_bytes: 256
#include <stdio.h>

int main() 
{
    int n;   
    int count;
    while (scanf("%d", &n) == 1) {
        count = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    for (int l = 0; l < 10; l++) {
                        if (i + j + k + l == n)
                            count++;
                    }
                }
            }
        } 
        printf("%d\n", count);
    }                
    return 0;
}        


Measured memory_bytes: 2048
import java.util.*;
 
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        
        
        if(S.equals("ABC")) {
            System.out.println("ARC");
        }else {
            System.out.println("ABC");
        }
    }
}

Measured memory_bytes: 35720
import math
a,b,x=map(int,input().split())
c=x/(a**2)
if c*2>b:
    print(math.degrees(math.acos(a/((a**2+((b-c)*2)**2)**0.5))))
else:
    print(math.degrees(math.acos((2*a*c/b)/(((2*a*c/b)**2+b**2)**0.5))))

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 10001
#define INF (1<<28);
#define QUEUE_SIZE 20001;

typedef struct Node * NodePointer;

typedef struct Node {
  NodePointer next;
  int v, c;
} Node;

int N;
NodePointer E[MAX_N] = {};
NodePointer tail[MAX_N] = {};
int cost[MAX_N];

NodePointer makeNode(int v, int c) {
  NodePointer node = (NodePointer)malloc(sizeof(Node));
  node->next = NULL;
  node->v = v;
  node->c = c;
  return node;
}

void addEdge(int u, int v, int c) {
  tail[u]->next = makeNode(v,c);
  tail[u] = tail[u]->next;
}

int daiku() {
  int i, j;
  int mini, id;
  int vis[MAX_N];
  NodePointer np;
  for(i = 0; i < N; ++i) {
    cost[i] = INF;
    vis[i] = 0;
  }
  cost[0] = 0;
  while(1) {
    mini = INF;
    id = -1;
    for(i = 0; i < N; ++i) {
      if(vis[i]) continue;
      if(cost[i] < mini) {
        mini = cost[i];
        id = i;
      }
    }
    if(id == -1) break;
    vis[id] = 1;
    for(np = E[id]->next; np != NULL; np = np->next) {
      if(vis[np->v]) continue;
      j = cost[id] + np->c;
      if(j < cost[np->v]) cost[np->v] = j;
    }
  }
}

int main() {
  int i, j, k;
  int id, v, c;
  int tmp;

  for(i = 0; i < MAX_N; ++i) {
    E[i] = makeNode(-1,-1);
    tail[i] = E[i];
  }

  scanf("%d", &N);
  for(i = 0; i < N; ++i) {
    scanf("%d %d", &id, &k);
    while(k--) {
      scanf("%d %d", &v, &c);
      addEdge(id,v,c);
    }
  }

  daiku();

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

  return 0;
}



Measured memory_bytes: 17784
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<string>
 
using namespace std;
 
int main(void){
 int N;
 vector<string> s(200000);
 unordered_map<string, int> mp;
 cin >> N;
  
 for(int i=0; i<N; i++){
  cin >> s[i];
 }
  mp[s[0]] = 1;
  for(int i=1; i < N; i++){
   if(mp.find(s[i]) == mp.end()){
     mp[s[i]] = 1;
   }else{
     mp[mp.find(s[i])->first]++;
   }
  }
  int max = 1;
  vector<string> maxs;
  for(auto it = mp.begin(); it != mp.end(); it++){
    if (it->second > max){
      max = it->second;
    }
  }
  for(auto it = mp.begin(); it != mp.end(); it++){
    if (it->second == max){
      maxs.push_back(it->first);
    }
  }
  sort(maxs.begin(), maxs.end());
  for(int k= 0; k < maxs.size(); k++){
   cout << maxs[k] << endl; 
  }
  return 0;
}

Measured memory_bytes: 28228
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
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; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

int c[300000];

int main() {
  int n,Q;
  while(input(n,Q)) {
    inputs(c,n);
    sort(c,c+n);
    n = unique(c,c+n) - c;
    while(Q--) {
      int x;
      input(x);
      int ans = 0;
      if (x <= 600) {
        REP(i,n) chmax(ans, c[i]%x);
      } else {
        for (int y=x; y<300000+x; y+=x) {
          int idx = lower_bound(c,c+n,y) - c;
          if (idx > 0) {
            chmax(ans, c[idx-1]%x);
          }
        }
      }
      output(ans);
    }
  }
}

Measured memory_bytes: 2256
#include<bits/extc++.h>
#ifdef _debug 
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#include<bits/stdc++.h>
#define dout(i) 0&&0
#endif
#pragma GCC optimize("unroll-loops,no-stack-protector,O3")
#define eout(i) {cout << (i) << '\n';exit(0);}
#define priority_queue __gnu_pbds::priority_queue
#define unordered_map __gnu_pbds::gp_hash_table
#define rep(a, b) {for(int _i = a;_i > 0;--_i){b;}}
#define multe int _T;for(cin >> _T;_T--;)
using namespace std;
using ll = long long;using ull = unsigned long long;using ul = unsigned;using db = double;
using __gnu_pbds::null_type;
template<typename T> void read(int n, T s){while(n--)cin >> *s, ++s;}
template<typename T> void write(int n, T s){while(n--)cout << *s << " \n"[n==0], ++s;}
template<typename T> using rbtree = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T> inline ostream& operator << (ostream &ou, const vector<T> &a){for(auto it = a.begin();it != a.end();++it)ou << (it != a.begin() ? " " : "") << *it;return ou;}
template<typename T1, typename T2>inline istream& operator >> (istream &in, pair<T1, T2> &a){return in >> a.first >> a.second;}
template<typename T1, typename T2>inline ostream& operator << (ostream &ou, const pair<T1, T2> &b){return ou << b.first << ' ' << b.second;}
template<typename T> inline long long pow(long long v, long long t, const T &p){long long res = 1;for(;t;t >>= 1, v = v * v % p)if(t & 1)res = res * v % p;return res;}
const int maxn = 18;
const int p = 1e9+7;
int n, m;
int lo[maxn];
ll dp[1 << maxn];
ll fa[1 << maxn], inv[1 << maxn], fainv[1 << maxn];
inline void init(){
	inv[1] = fa[1] = fainv[1] = fa[0] = inv[0] = fainv[0] = 1;
	for(int i = 2;i < (1 << maxn);++i){
		fa[i] = fa[i-1] * i % p;
		inv[i] = (p-p/i) * inv[p % i] % p;
		fainv[i] = inv[i] * fainv[i-1] % p;
	}
}
// ll C(int a, int b){
// 	return fa[a] * fainv[b] % p * fainv[a - b] % p;
// }
ll per(int a, int b){
	return (a < b ? 0 : fa[a] * fainv[a - b]) % p;
}
int count_bit(int v){
	int res = 0;
	for(;v;v -= (v & -v))++res;
	return res;
}
void out(int s){
	for(int i = n-1;i >= 0;--i)cout << !!(s & (1 << i));
	cout << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	init();
	cin >> n >> m;
	read(m, lo+1);
	sort(lo+1, lo+1+m, greater<int>());
	dp[0] = 1;
	for(int i = 1;i <= m;++i){
		for(int s = 1<<n;s > 0;--s){
			for(int j = 0;j < n;++j)if(s & (1 << j)){
				int pleft = (1<<n)-lo[i]-s+(1<<j);
				dp[s] = (dp[s] + (dp[s ^ (1 << j)] * per(pleft, (1<<j)-1) % p * (1<<j) % p)) % p;				
			}
		}
	}
	// for(int i = 1;i < (1<<n);++i)cout << dp[i] << '\n';
	ll res = 0;
	for(int s = 1;s < (1 << n);++s){
		dp[s] = dp[s] * fa[(1<<n)-1-s];
		if(count_bit(s)&1)res = (res + p - dp[s]) % p;
		else res = (res + dp[s]) % p;
	}
	res = (fa[(1<<n)-1] + p + res) % p * (1 << n) % p;
	cout << res << '\n';
}

Measured memory_bytes: 8448
n, m = gets.chomp.split.map(&:to_i)
b1 = []
an = []
m.times do |_|
  a, b = gets.chomp.split.map(&:to_i).sort!
  if a == 1
    b1 << b
  elsif b == n
    an << a
  end
end
puts ((b1 & an).size > 0)? "POSSIBLE" : "IMPOSSIBLE"

Measured memory_bytes: 9852
use std::io;


fn main() {
    let (h, w) = {
        let i = read::<usize>();
        (i[0], i[1])
    };
    let mut vec = Vec::new();
    for _ in 0..h {
        let i = read::<usize>();
        vec.push(i);
    }

    let mut ss = Vec::new();
    for i in 0..h { for j in 0..w {
        if vec[i][j] % 2 != 0 {
            if j < w - 1 {
                vec[i][j + 1] += 1;
                vec[i][j] -= 1;
                ss.push(format!("{} {} {} {}", i + 1, j + 1, i + 1, j + 2));
            }
            if j == w - 1 && i < h - 1 {
                vec[i + 1][j] += 1; vec[i][j] -= 1;
                ss.push(format!("{} {} {} {}", i + 1, j + 1, i + 2, j + 1));
            }
        }
    }}

    println!("{}", ss.len());
    for s in ss {
        println!("{}", s);
    }
}

#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

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

using namespace std;
int main() {
  int n;
  cin >> n;
  int c[n] = {0};
  int v[n] = {0};

  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  int total = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] > c[i]) total += v[i] - c[i];
  }
  cout << total << endl;
}

Measured memory_bytes: 256
// E - Coprime
#include <bits/stdc++.h>
using namespace std;
#define rpd(i,s,e,d) for(int i=(s);i<(int)(e);i+=(d))

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

	int mx = 1000000;
	vector<int> D(mx+1, 0);
	rpd(i, 2, mx+1, 1)
		if(!D[i]) rpd(j, i, mx+1, i) D[j] = i;

	int N; cin>>N;
	int g = 0;
	bool not_pairwise = false;
	unordered_set<int> past;
	rpd(i, 0, N, 1){
		int a; cin>>a;
		g = gcd(g, a);
		if(not_pairwise) continue;
		unordered_set<int> now;
		while(a != 1){
			// 素数 D[a]: 今回は未済 & 過去は済
			if(( not_pairwise = now.find(D[a]) == now.end()
			&& past.find(D[a]) != past.end() )) break;
			now.insert(D[a]);
			past.insert(D[a]);
			a /= D[a];
		}
	}
	int t = not_pairwise + (g > 1);
	cout<< vector<string>{"pairwise","setwise","not"}[t] <<" coprime\n";
}


Measured memory_bytes: 10512
#include<iostream>
using namespace std;
int main()
{
    string s;
    int ans=0;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='7')
            ans=1;
    }
    if(ans==1)
        cout<<"Yes";
    else
        cout<<"No";
}




Measured memory_bytes: 3628
#include <iostream>
using namespace std;
 
int main(){

    int n;

	cin >> n;

    int cn = n;
    int i;

    for(i=0; i<6; i++){
        cn = cn/10;
        if (cn == 0)
            break;
    }

    switch(i){
	case 0:
		cout << n << endl;
		break;
	case 1:
		cout << 9 << endl;
		break;
	case 2:
		cout << n - 99 + 9 << endl;
		break;
    case 3:
		cout << 909 << endl;
		break;
    case 4:
		cout << n - 9999 + 909 << endl;
		break;
    case 5:
		cout << 90909 << endl;
		break;
	default:
		cout << "eof" << endl;
		break;
    }
}

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

using namespace std;
#define ll  long long
#define ld  long double

#define endl '\n'
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
int freq[200];
int main()
{
    FAST
ll x;
cin>>x;
ll a=log2(x)+1;
cout<<setprecision(13)<<pow(2,a)-1<<endl;

    return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
int main()
{
    int a,b,i,j,n;
    char s[105][105],temp[105];
    scanf("%d %d",&a,&b);
    for(i=0; i<a; i++)
    {
        scanf("%s",s[i]);
    }
    for(i=0; i<a; i++)
    {
        for(j=i+1; j<a; j++)
        {
            if(strcmp(s[i],s[j])>0)
            {
                strcpy(temp,s[i]);
                strcpy(s[i],s[j]);
                strcpy(s[j],temp);
            }
        }
    }
    for(i=0; i<a; i++)
    {
        printf("%s",s[i]);
    }
    return 0;
}



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

using namespace std;

int main() {
    int n, max = -1;
    string s;
    map<string, int> m;
    cin >> n;
    for(int i = 0; i < n; i++) {
         cin >> s;
         if (m.find(s) == m.end()) {
             m[s] = 0;
         }
         if (++m[s] > max) max = m[s];
    }
    for (auto i = m.begin(); i != m.end(); i++) {
        if (i->second == max) {
            cout << i->first << endl;
        }
    }
    return 0;
}

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

#pragma GCC optimize ("O3")

using namespace std;

int readln(char* buf, int max)
{ 
   int len = 0;
   while ((max-- > 0) &&
          ((buf[len] = fgetc(stdin)) != '\n') &&
          (buf[len] != EOF)) ++len;
   buf[len] = 0;
   return len;
}

int N;
char S[401];

void solve()
{
    for (int i = 1; i <= N; ++i) {
        if (S[i] == 'Y') {
            cout << "Four" << endl;
            return;
        }
    }

    cout << "Three" << endl;
}

int main()
{
    scanf("%d\n", &N);

        readln(S, 400);

    solve();

    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    #0~Nまで逆元などを事前計算

    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]

    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
    for i in range(1,K+1):
        ans=(cmb(N-K+1,i,mod)*cmb(K-1,i-1,mod))%mod
        print(ans)
        
        
        

main()


Measured memory_bytes: 74588
def gcd(a,b):
  return a if b == 0 else gcd(b,a%b)

N= int(input())
A=[int(x) for x in input().split()]
gcd_L=[0]*N
gcd_R=[0]*N
for i in range(1,N):
  gcd_L[i]=gcd(A[i-1],gcd_L[i-1])
  gcd_R[N-1-i]=gcd(A[N-i],gcd_R[N-i])
answer=0
for j,k in zip(gcd_L,gcd_R):
  answer=max(answer,gcd(j,k))
print(answer)

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

#define rep(i, n) for(int i = 0; i < (n); i++)
using LL = long long;
using ULL = unsigned long long;


void solve() {
	int n; cin >> n;
	ULL k; cin >> k;
	unsigned a[200000]; rep(i, n) cin >> a[i];
	unsigned f[200000]; rep(i, n) cin >> f[i];
	sort(a, a + n); reverse(a, a + n);
	sort(f, f + n);
	ULL e = 0; rep(i, n) { e = max(e, (ULL)a[i] * f[i]); }

	ULL l = 0, r = e;
	while (l != r) {
		ULL p = (l + r) / 2;
		ULL s = 0, kp = 0;
		rep(i, n) {
			s = p / f[i]; if (s >= (ULL)a[i]) continue;
			kp += (ULL)a[i] - s;
		}
		if (kp > k) { l = p + 1; }
		else { r = p; }
	}
	cout << l << endl;
}

int main() {

	solve();

	return 0;
}


Measured memory_bytes: 1792
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

MOD = 1000000007

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

t = Tree(N, E)
t.setroot(0)

res = 0

for node in range(N):
    tmp = pow(2, N - 1, MOD) - 1
    for adj in t.tree[node]:
        if t.parent[node] == adj:
            s = N - t.size[node]
        else:
            s = t.size[adj]
        tmp -= pow(2, s, MOD) - 1
        tmp %= MOD
    res += tmp
    res %= MOD

res *= pow(pow(2, N, MOD), MOD - 2, MOD)
res %= MOD

print(res)

Measured memory_bytes: 182728
N, X = map(int, input().split())
NLs = [1]
NPs = [1]
for L in range(1, N+1):
  NLs.append(NLs[L-1]*2+3)
  NPs.append(NPs[L-1]*2+1)
#print(NLs, NPs)
def sub(L, X):
  if L == 0:
    return X
  if X <= 1:
    return 0
  elif X <= 1+NLs[L-1]:
    return sub(L-1, X-1)
  elif X == 1+NLs[L-1]+1:
    return NPs[L-1]+1
  elif X <= 1+NLs[L-1]+1+NLs[L-1]:
    return NPs[L-1]+1+sub(L-1, X-1-NLs[L-1]-1)
  else:
    return NPs[L-1]*2+1
r = sub(N, X)
print(r)


Measured memory_bytes: 3064
import math
K = int(input())
A, B = map(int, input().split())
ans=''

if K>B:
    ans='NG'
elif K>=A:
    ans='OK'
else:
    K=K*(math.ceil(A/K))
    if K>B:
        ans='NG'
    else:
        ans='OK'

print(ans)


Measured memory_bytes: 9068
/*
 * Author : Sadi
 * Thu 09/07/2020
 *  0:01:23.58
 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    string s, t;
    cin >> s;
    cin >> t;
    int count = 0;
    for(int i = 0; i < (int) s.size(); ++i) {
    	if(s[i] == t[i]) {
    		count++;
    	}
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3596
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = sc.nextInt();
        Map<Long, Integer> m = new HashMap<>();
        for(int i=0; i<n; i++) {
            long l = sc.nextLong();
            if(m.containsKey(l)) {
                m.remove(l);
            } else {
                m.put(l, 1);
            }
        }

        int cnt = 0;
        for(long l: m.keySet()) {
            if(m.get(l) == 1) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 63796
N,x = map(int,input().split())
if x==1 or x==2*N-1:
    print("No")
else:
    print("Yes")
    A = [0 for _ in range(2*N-1)]
    hist = [0 for _ in range(2*N)]
    A[N-1] = x
    A[N-2] = x-1
    A[N] = x+1
    hist[x]=1
    hist[x-1]=1
    hist[x+1]=1
    if x>2:
        cur = 1
    else:
        cur = 4
    for i in range(2*N-1):
        if i<N-2 or i>N:
            while hist[cur]==1:
                cur += 1
            A[i] = cur
            hist[cur] = 1
            cur += 1
    for i in range(2*N-1):
        print(A[i])
    

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

int main() {
  int N;
  cin >> N;
  
  vector<int> A(N, 0);
  vector<int> B(N - 1, 0);
  for (int i = 0; i < N - 1; ++i) {
    cin >> B[i];
  }
  
  A[N - 1] = B[N - 2];
  for (int i = N - 2; i >= 0; --i) {
    A[i] = min(B[i], B[i-1]);
  }
  A[0] = B[0];
  
  unsigned long long ans = 0;
  for (int i = 0; i < N; ++i) ans += A[i];
  cout << ans << endl;
  
  return 0;
}


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

int main(){
	unsigned int n, a[10000], result = 0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		while(a[i] % 2 == 0){
			a[i] /= 2;
			result++;
		}
	}
	cout << result << endl;
}

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

using namespace std;

#define ll long long

int main(void){
    int h, a, ans;
    cin >> h >> a;
    ans = 0;

    do{
        ans++;
        h -= a;
    }while(h > 0);

    cout << ans << endl;

    return 0;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    int n; cin >> n; vector<lint> a(n); rep(i, n) cin >> a[i];
    rep(i, n-1) a[i+1] += a[i]; a.push_back(0); sort(all(a));
    lint s = 1, t = a[0], r = 0;
    rep(i, n){
        if(a[i+1] == t) s++;
        else{
            r += s*(s-1)/2; s = 1; t = a[i+1];
        }
    } out(r + s*(s-1)/2);
}


Measured memory_bytes: 4736
from collections import deque
S=deque(input())
q=int(input())
rev=False
for _ in range(q):
   inp=input()
   if inp=="1":
      rev= not rev
   else:
      t,f,c=inp.split()
      if (rev and f=="1") or (not rev and f=="2"):
         S.append(c)
      else:
         S.appendleft(c)
if rev:
   S.reverse()
print("".join(S))

Measured memory_bytes: 74456
/** Author : Parth Prajapati
 * 	Institute : Pandit Deendayal Petroleum University
**/
#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,i,k,min,cnt=1;
    cin>>n>>k;
    min = k;
    for(i=1;i<n;++i)
    {
        cin>>k;
        if(min >= k)
        {
            min = k;
            ++cnt;
        }
    }
    cout<<cnt;
	return 0;
}

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

int main(){
    int n,x; cin>>n>>x;
    int loc = 0;
    int ans =0;
    do{
        int l; cin>>l;
        loc+=l;
        ans++;
    }while(ans<=n&&loc<=x);
    cout<< ans <<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn=new Scanner(System.in);
		int a=scn.nextInt();
		int b=scn.nextInt();
		if(a>b&&b>a-1) {
			System.out.println(a+b);
		}else if(a>b&&a-1>=b) {
			System.out.println(a+a-1);
		}else if(a>b-1) {
			System.out.println(a+b);
		}else {
			System.out.println(b+b-1);
		}
	}

}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n-1; i >= 0; i--)
#define ALL(x) x.begin(),x.end()
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 1e9+7;
const int INF = 2e9;
// const ll INF = 1e12;
const int MAX = 1e6;
// const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

// struct edge {int to, cost;}; // 辺
// vector<edge> graph[MAX]; // 隣接リスト
// bool visited[MAX]; // 訪問状況

ll dp[51][51][2501];

int main() {
    // input
    int n, a;
    cin >> n >> a;
    vi x(n+1);
    rep(i, n+1) {
        if (i > 0) cin >> x[i];
    }
    // solve
    rep(i, n+1) {
        rep(j, n+1) {
            rep(k, 50*n+1) {
                if (i == 0 and j == 0 and k == 0) {
                    dp[i][j][k] = 1;
                } else if (i >= 1 and k < x[i]) {
                    dp[i][j][k] = dp[i-1][j][k];
                } else if (i >= 1 and j >= 1 and k >= x[i]) {
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i]];
                } else {
                    dp[i][j][k] = 0;
                }
            }
        }
    }
    ll sum = 0;
    rep(i, n+1) {
        if (i > 0) sum += dp[n][i][i*a];
    }
    // output
    cout << sum << endl;
}

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

int main() {
  int n,m,k,a,x;
  cin >> n >> m;
  x = 0;
  
  vector<int> vec(30);
  
  for(int i = 0 ; i < n ; i++){
    cin >> k;
    for(int j = 0 ; j < k ; j++){
      cin >> a;
      vec.at(a -1)++;
    }
  }
  
  for(int i = 0 ; i < m ; i++){
    if(vec.at(i) == n){
      x++;
    }
  }
  
  cout << x << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

#define all(v) (v).begin(),(v).end()
using ll = long long;
constexpr ll INF = 1e18;
constexpr ll MOD = 998244353;

// https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
long long mod(long long val, long long m) {
  long long res = val % m;
  if (res < 0) res += m;
  return res;
}

int main(void) {
    ll N, K;
    cin >> N >> K;
    vector<ll> L(K), R(K);
    for (ll i = 0; i < K; i++) {
        cin >> L[i] >> R[i];
    }

    vector<ll> map(N*3);
    // vector<ll> dmap(N*2);
    map[0] = 0;
    map[1] = -1;
    ll c = 1;
    for (ll i = 0; i < N; i++) {
        c = (c + map[i]) % MOD;
        for (ll j = 0; j < K; j++) {
            map[i+L[j]] = (map[i+L[j]] + c) % MOD;
            map[i+R[j]+1] = mod(map[i+R[j]+1] - c, MOD);
        }
    }
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 7560
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};



void solve(){
    ll a,b;
    string s;
    cin>>a>>b>>s;
    ll n=s.size();
    bool ok=true;
    rep(i,n){
        if(i!=a){
            if(s[i]=='-') ok=false;
        }
        else if(s[i]!='-') ok=false;
    }
    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    solve();

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
using namespace std;


typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
  int n;
  cin >> n;
  vector<int> x(n), xsort(n);
  int sum = 0;
  rep(i, n){
    int a;
    cin >> a;
    x[i] = a;
    xsort[i] = a;
  }

  sort(xsort.begin(), xsort.end());
  int t = (x.size()) / 2;
  for(int i = 0; i < n; ++i){
    if(x[i] < xsort[t]){
      cout << xsort[t] << endl;
    } else {
      cout << xsort[t-1] << endl;
    }
  }

}


Measured memory_bytes: 3712
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int main(void){
	int n;
	double h,m;
	double ans;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lf:%lf",&h,&m);
		h=h*30+m/2;
		m=m*6;
		if(h>m)ans=h-m;
		else ans=m-h;
		if(ans<30 || ans>330)cout << "alert" << endl;
		else if(90<=ans && ans<=270)cout << "safe" << endl;
		else cout << "warning" << endl;
	}
    return 0;
}

Measured memory_bytes: 1232
#include<stdio.h>
#define MAX 100000
#define SENTINEL 2000000000

struct Card {
    char suit;
    int value;
};

struct Card L[MAX / 2 + 2], R[MAX / 2 + 2];

void merge(struct Card A[], int n, int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left;
    int n2 = right - mid;
    for ( i = 0; i < n1; i++ ) L[i] = A[left + i];
    for ( i = 0; i < n2; i++ ) R[i] = A[mid + i];
    L[n1].value = R[n2].value = SENTINEL;
    i = j = 0;
    for ( k = left; k < right; k++ ) {
        if ( L[i].value <= R[j].value ) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void mergeSort(struct Card A[], int n, int left, int right) {
    int mid;
    if ( left + 1 < right ) {
        mid = (left + right) / 2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        merge(A, n, left, mid, right);
    }
}

int partition(struct Card A[], int n, int p, int r) {
    int i, j;
    struct Card t, x;
    x = A[r];
    i = p - 1;
    for ( j = p; j < r; j++ ) {
        if( A[j].value <= x.value ) {
            i++;
            t = A[i]; A[i] = A[j]; A[j] = t;
        }
    }
    t = A[i + 1]; A[i + 1] = A[r]; A[r] = t;
    return i + 1;
}

void quickSort(struct Card A[], int n, int p, int r) {
    int q;
    if ( p < r ) {
        q = partition(A, n, p, r);
        quickSort(A, n, p, q - 1);
        quickSort(A, n, q + 1, r);
    }
}
int main(void) {
  int n, i, v;
  struct Card A[MAX], B[MAX];
  char S[10];
  int stable = 1;

  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
      scanf("%s %d", S, &v);
      A[i].suit = B[i].suit = S[0];
      A[i].value = B[i].value = v;
  }

  mergeSort(A, n, 0, n);
  quickSort(B, n, 0, n - 1);

  for ( i = 0; i < n; i++ ) {
      // マージソートとクイックソートの結果を比べる
      if ( A[i].suit != B[i].suit ) stable = 0;
  }

  if ( stable == 1 ) printf("Stable\n");
  else printf("Not stable\n");
  for ( i = 0; i < n; i++ ) {
      printf("%c %d\n", B[i].suit, B[i].value);
  }

  return 0;
}



Measured memory_bytes: 4024
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template<typename T> T in(){
	T res;
	cin >> res;
	return res;
}
template<typename T> vector<T> in(int n){
	vector<T> res(n);
	rep(i,n) res[i] = in<T>();
	return res;
}
template<typename T> vector<vector<T>> in(int h, int w){
	vector<vector<T>> res(h);
	rep(i,h) res[i] = in<T>(w);
	return res;
}

template<typename T> void out(bool a, T F, T S){
	cout << (a ? F : S) << endl;
}
template<typename T> void out(T a){
	cout << a << endl;
}
template<typename T> void out(vector<T> a, bool space = true){
	rep(i,a.size()){
		cout << a[i] << (i + 1 == a.size() ? "\n" : (space ? " " : ""));
	}
}
template<typename T> void out(vector<vector<T>> a){
	rep(i,a.size()){
		out(a[i]);
	}
}

template<typename T> T Add(T a, T b){ return a + b; }
template<typename T> T Sub(T a, T b){ return a - b; }
template<typename T> T Pro(T a, T b){ return a * b; }
template<typename T> T Div(T a, T b){ return a / b; }
template<typename T> T Mod(T a, T b){ return a % b; }

template<typename T>
void solve(T a){
	vector<char> ans;
	rep(i,3) ans.emplace_back(a[i][i]);
	out(ans, false);
}

int main(){
	solve(in<char>(3,3));
}


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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

int bitCount(int x){
	int res = 0;
	while (x > 0) {
		if (x & 1) res++;
		x >>= 1;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		int s,d;
		scanf("%d %d", &s, &d);
		
		int ans = 0;
		if (s < 0 && d < 0) { s = -s; d = -d; swap(s, d);}
		
		if (s < 0) {
			s = -s;
			ans += bitCount(s);
			s = 0;
		}
		
		if (s != d) {
			if (s == 0) {
				s = d;
				ans += bitCount(s);
			}
			else {
				while (s + (s & -s) < d) {
					s += s & -s;
					ans++;
				}
				s = d - s;
				ans += bitCount(s);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3236