#include <iostream>
#include <algorithm>
#include <climits>
#include <cmath>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <vector>

using namespace std;

double vectorDistance(vector<double>::iterator first, vector<double>::iterator last, vector<double>::iterator first2) {
  double ret = 0.0;
  while (first != last) {
    double dist = (*first++) - (*first2++);
    ret += dist * dist;
  }
  return ret > 0.0 ? sqrt(ret) : 0.0;
}

int toDecimal(string& s, int b)
{
	int n = s.size();
	int d = 0;
	for(int i = 0; i<n; ++i)
	{
		int digit = s.c_str()[n-1-i] - '0';
		if(s.c_str()[n-1-i] >= 'a' && s.c_str()[n-1-i] <= 'z')
		{
			digit = s.c_str()[n-1-i] - 'a' + 10;
		}
		d += digit * pow(b,i);
	}
	return d;
}

vector<string> split(const string &s, char delim) {
	stringstream ss(s);
	vector<string> elems;
	string item;
	while (getline(ss, item, delim)) {
		elems.push_back(item);
	}
	return elems;
}

int occurences(const string& s, char needle){
	return count(s.begin(), s.end(), '-');
}

void paint( vector<vector<int>>& mat, int x, int y, int c, int f)
{
	if(x < 0 || y < 0 || x >= mat.size() || y>= mat[x].size())
	{
		return;
	}
	if(mat[x][y] != f)
	{
		return;
	}
	mat[x][y] = c;
	paint(mat,x+1,y,c,f);
	paint(mat,x+1,y,c,f);
	paint(mat,x,y+1,c,f);
	paint(mat,x,y-1,c,f);

	paint(mat,x+1,y+1,c,f);
	paint(mat,x+1,y-1,c,f);
	paint(mat,x-1,y+1,c,f);
	paint(mat,x-1,y+1,c,f);
}

template <typename T>
void print_v(vector<T> v)
{
	for(auto& i : v)
	{
		cout << i << " ";
	}
	cout << endl;
}



template <typename T>
void print_mat(const vector<vector<T>>& mat)
{
	for(auto& i : mat)
	{
		print_v(i);
	}
}
template<typename T>
map<T,int> getFreqs(const vector<T>& vs)
{
	map<T,int> freqs;
	for(const auto& v : vs)
	{
		if(freqs.find(v) == freqs.end())
		{
			freqs[v] = 1;
		}
		else
		{
			freqs[v]++;
		}
	}
	return freqs;
}

template<typename T>
void print_freqs(const map<T,int>& f)
{
	for(auto p : f)
	{
		cout << p.first << " " << p.second << endl;
	}
}


template<typename T>
int countPathsDFS(map<T,vector<T>> & ds, const T& from, const T& to, const T& nil)
{
	if(from == to)
	{
		return 1;
	}

	int count = 0;

	for(T& d : ds[from])
	{
		if(d == nil) continue;

		T tmp = d;

		d = nil;
		count += countPaths(ds,tmp,to,nil);
		d = tmp;
	}

	return count;
}




int main()
{
	return 0;
}