import random
import time
 
BASE = 3
 
 
class RatioInt(list):
 
    def __init__(self, value=[], base=10):
        assert all(
            val < base for val in value), 'Elements must be less than base. Base = %s' % base
 
        super(RatioInt, self).__init__(reversed(value))
        self.base = base
 
    def __add__(self, other):
        out = [0 for _ in range(max(len(self), len(other)))]
        i = 0
        c = 0
 
        while i < len(out):
            temp = self[i] + other[i] + c
            out[i] = (temp % self.base)
            c = temp // self.base
 
            i += 1
 
        if c:
            out.append(c)
 
        return RatioInt(out, self.base)
 
    def __mod__(self, val):
        '''
        Возвращает val-последних символов.
        '''
        return self[-val:]
 
    def __getitem__(self, key):
        try:
            return super(RatioInt, self).__getitem__(key)
        except IndexError:
            return 0
 
    def __str__(self):
        return ''.join(str(elem) for elem in self) + '(%s)' % self.base
 
 
def timing(func):
    def _f(*args, **kwargs):
        start = time.time()
        out = func(*args, **kwargs)
        print('It took %2.6ss' % (time.time() - start))
        return out
 
    return _f
 
 
@timing
def test_ariphmetic():
    for _ in range(10 ** 5):
        base = random.randint(2, 10)
        a = RatioInt([random.randint(0, base - 1) for _ in range(3)], base)
        b = RatioInt([random.randint(0, base - 1) for _ in range(3)], base)
        a += b
        # print('%s + %s = %s' % (a, b, a + b))
 
 
if __name__ == '__main__':
    test_ariphmetic()
 

aW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQoKQkFTRSA9IDMKCgpjbGFzcyBSYXRpb0ludChsaXN0KToKCiAgICBkZWYgX19pbml0X18oc2VsZiwgdmFsdWU9W10sIGJhc2U9MTApOgogICAgICAgIGFzc2VydCBhbGwoCiAgICAgICAgICAgIHZhbCA8IGJhc2UgZm9yIHZhbCBpbiB2YWx1ZSksICdFbGVtZW50cyBtdXN0IGJlIGxlc3MgdGhhbiBiYXNlLiBCYXNlID0gJXMnICUgYmFzZQoKICAgICAgICBzdXBlcihSYXRpb0ludCwgc2VsZikuX19pbml0X18ocmV2ZXJzZWQodmFsdWUpKQogICAgICAgIHNlbGYuYmFzZSA9IGJhc2UKCiAgICBkZWYgX19hZGRfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgb3V0ID0gWzAgZm9yIF8gaW4gcmFuZ2UobWF4KGxlbihzZWxmKSwgbGVuKG90aGVyKSkpXQogICAgICAgIGkgPSAwCiAgICAgICAgYyA9IDAKCiAgICAgICAgd2hpbGUgaSA8IGxlbihvdXQpOgogICAgICAgICAgICB0ZW1wID0gc2VsZltpXSArIG90aGVyW2ldICsgYwogICAgICAgICAgICBvdXRbaV0gPSAodGVtcCAlIHNlbGYuYmFzZSkKICAgICAgICAgICAgYyA9IHRlbXAgLy8gc2VsZi5iYXNlCgogICAgICAgICAgICBpICs9IDEKCiAgICAgICAgaWYgYzoKICAgICAgICAgICAgb3V0LmFwcGVuZChjKQoKICAgICAgICByZXR1cm4gUmF0aW9JbnQob3V0LCBzZWxmLmJhc2UpCgogICAgZGVmIF9fbW9kX18oc2VsZiwgdmFsKToKICAgICAgICAnJycKICAgICAgICDQktC+0LfQstGA0LDRidCw0LXRgiB2YWwt0L/QvtGB0LvQtdC00L3QuNGFINGB0LjQvNCy0L7Qu9C+0LIuCiAgICAgICAgJycnCiAgICAgICAgcmV0dXJuIHNlbGZbLXZhbDpdCgogICAgZGVmIF9fZ2V0aXRlbV9fKHNlbGYsIGtleSk6CiAgICAgICAgdHJ5OgogICAgICAgICAgICByZXR1cm4gc3VwZXIoUmF0aW9JbnQsIHNlbGYpLl9fZ2V0aXRlbV9fKGtleSkKICAgICAgICBleGNlcHQgSW5kZXhFcnJvcjoKICAgICAgICAgICAgcmV0dXJuIDAKCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICByZXR1cm4gJycuam9pbihzdHIoZWxlbSkgZm9yIGVsZW0gaW4gc2VsZikgKyAnKCVzKScgJSBzZWxmLmJhc2UKCgpkZWYgdGltaW5nKGZ1bmMpOgogICAgZGVmIF9mKCphcmdzLCAqKmt3YXJncyk6CiAgICAgICAgc3RhcnQgPSB0aW1lLnRpbWUoKQogICAgICAgIG91dCA9IGZ1bmMoKmFyZ3MsICoqa3dhcmdzKQogICAgICAgIHByaW50KCdJdCB0b29rICUyLjZzcycgJSAodGltZS50aW1lKCkgLSBzdGFydCkpCiAgICAgICAgcmV0dXJuIG91dAoKICAgIHJldHVybiBfZgoKCkB0aW1pbmcKZGVmIHRlc3RfYXJpcGhtZXRpYygpOgogICAgZm9yIF8gaW4gcmFuZ2UoMTAgKiogNSk6CiAgICAgICAgYmFzZSA9IHJhbmRvbS5yYW5kaW50KDIsIDEwKQogICAgICAgIGEgPSBSYXRpb0ludChbcmFuZG9tLnJhbmRpbnQoMCwgYmFzZSAtIDEpIGZvciBfIGluIHJhbmdlKDMpXSwgYmFzZSkKICAgICAgICBiID0gUmF0aW9JbnQoW3JhbmRvbS5yYW5kaW50KDAsIGJhc2UgLSAxKSBmb3IgXyBpbiByYW5nZSgzKV0sIGJhc2UpCiAgICAgICAgYSArPSBiCiAgICAgICAgIyBwcmludCgnJXMgKyAlcyA9ICVzJyAlIChhLCBiLCBhICsgYikpCgoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIHRlc3RfYXJpcGhtZXRpYygpCg==