#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
using ll = long long;
using P = pair<int,int>;
int main() {
  int n,m;
  cin>>n>>m;
  vector<int> v(n),w(m);
  rep(i,n)cin>>v[i];
  rep(i,m)cin>>w[i];
  int j=0;
  rep(i,n){
    while(j<m&&w[j]<v[i]){
      cout<<w[j]<<" ";
      j++;
    }
    if(v[i]==w[j]){
      j++;
      continue;
    }
    cout<<v[i]<<" ";
  }
  for (; j < m; j++)
  {
    cout<<w[j]<<" ";
  }
  
  cout<<endl;
}
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=(int)(x);i<(int)(y);i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int siz=3e5;
const int inf=1e9;
int main(){
	int N,M; cin>>N>>M;
	int x,y;
	pair<int,int> vp[M+1]; vp[0] = {0, N};
	map<pair<int,int>,bool> mp; mp[vp[0]] = true;
	map<int,vector<int>> record; record[N].push_back(0);
	rep(i,0,M){
		cin>>x>>y;
		vp[i+1] = {x, y};
		record[y].push_back(x);
	}
	sort(vp,vp+M+1);
	for(auto it = record.begin(); it != record.end(); it++){
		sort((it->second).begin(), (it->second).end());
      	//print((it->second),,(it->second).size());
	}
	rep(i,1,M+1){
		pair<int,int> p = vp[i];
		mp[p] = false;
		if(p.second > 0 && !record[p.second-1].empty()){
			auto it = lower_bound(record[p.second-1].begin(), record[p.second-1].end(), p.first);
			if(it != record[p.second-1].begin()){
				mp[p] |= mp[{*(it-1), p.second-1}];
			}
		}
		if(p.second < 2*N && !record[p.second+1].empty()){
			auto it = lower_bound(record[p.second+1].begin(), record[p.second+1].end(), p.first);
			if(it != record[p.second+1].begin()){
				mp[p] |= mp[{*(it-1), p.second+1}];
			}
		}//cout<<p.first<<" "<<p.second<<" "<<mp[p]<<endl;
	}
	int ans = 0;
	for(pair<int,vector<int>> pv:record){
      	if(!pv.second.empty()) ans += mp[{pv.second.back(), pv.first}];
	}
	cout<<ans<<endl;
}