#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#include <list>

using namespace std;

/* adds two positive numbers of a positive base under 36*/
/* return "NULL" if either input is bad */
string add(const string& num1,const string& num2,const size_t& base);

/* check is a number is valid input in a given base */
bool isValidNum(const string& num,const size_t& base);

/* returns a copy of num, with no leading zeros */
string killLeadingZeros(const string& num);

/* appends zeros to front */
string addZerosToFront(const string& num, size_t howMany);

/* returns numerical value of char in base */
/* ex { '0' = 0 ... '9' = 9 } , {'A' = 10 ... 'Z' = 36 } */
int toBaseInt(const char c);

/* returns the char value of int in base */
/* ex{ 0 = '0'... 9 = '9'} , { 10 = 'A' ... 36 = 'Z'} */
char toBaseChar(const int i);
int main()
{
	string hex1 = "FFFF";
	string hex2 = "FFFF";
	string hexResult = add(hex1,hex2,16);

	string bin1 = "111";
	string bin2 = "101";
	string binResult = add(bin1,bin2,2);

	string dec1 = "1234567891017181920";
	string dec2 = "98765432123456789";
	string decResult = add(dec1,dec2,10);

	cout << hex1 << " + " << hex2 << " = " << hexResult << endl;
	cout << bin1 << " + " << bin2 << " = " << binResult << endl;
	cout << dec1 << " + " << dec2 << " = " << decResult << endl;


	return 0;
}

int toBaseInt(const char c){
	const string num = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";	
	return num.find(c);
}
char toBaseChar(const int i){
	const string num = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";	
	return num[i % num.size()];
}
bool isValidNum(const string& num,const size_t& base)
{
	const string bases = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";		
	// check if valid digit
	for(size_t pos = 0; pos != num.size(); ++pos){		
		if( unsigned(toBaseInt(num[pos])) > base ) return false;
	}
	return true;
}
string addZerosToFront(const string& num, size_t howMany){
	string str = string(num.size() + howMany,'0');
	for(int pos = howMany; pos != num.size()+ howMany; ++pos) 
		str[pos] = num[pos-howMany];
	return str;
}
string killLeadingZeros(const string& num){
	string str;
	/* quick check */
	if(num[0] != '0') return string(num);
	size_t pos = 1;
	while(num[pos] == '0') ++pos; 
	std::copy(num.begin()+pos,num.end(),std::back_insert_iterator<string>(str));
	return str;
}
string add(const string& num1,const string& num2, const size_t& base){
	if(!isValidNum(num1,base) || !isValidNum(num2,base) || base <= 0 || base > 36) 
		return "NULL";
	
	string topNum = killLeadingZeros(num1);
	string bottomNum = killLeadingZeros(num2);
	
	int sizeDiff = topNum.size() - bottomNum.size();
	
	if(sizeDiff > 0) 
		bottomNum = addZerosToFront(bottomNum,sizeDiff);
	else if(sizeDiff < 0)
		topNum = addZerosToFront(topNum,abs(sizeDiff));
	else /* size are the same */;
	
	
	list<char> result = list<char>();

	bool hasCarry = false;

	/* add digit by digit */
	for(size_t pos = topNum.size()-1; pos != -1; --pos)
	{
		/* add the last digit */
		size_t digitAdded = toBaseInt(topNum[pos]) + toBaseInt(bottomNum[pos]);
		/* add 1 if their is a carry from last addition */
		if(hasCarry){ ++digitAdded; hasCarry ^=1; }
		/* save the last digit of the result */
		result.push_back(toBaseChar(digitAdded % base));

		if(digitAdded >= base) hasCarry ^= true;
	}
	/* check if the left-most digit had a carry */
	if(hasCarry){ result.push_back('1'); }
	
	string strNum;
	/* copy data */
	while(!result.empty()){
		strNum.push_back(result.back());
		result.pop_back();
	}

	return strNum;
}