const { performance } = require('perf_hooks');
function worker(low, dp, sml, login) {
  let gc = e => e.toString(16),
    reg = `(.{${sml}}[\\u${gc(low)}-\\u${gc(dp)}])|(\\D{4})`;
  let start = _ => {
    let dk = performance.now();
    login(reg); return performance.now() - dk;
  }
  let mass = Array.from({ length: 4 }, start).sort();

  return mass[1] + mass[2];
}
function cycle(login, dt) {
  let lw = 0x4e00, up = 0x9fff, mid;
  while (lw < up) {
    mid = (lw + up) >> 1;
    let x = worker(lw, mid, dt, login),
      y = worker(mid + 1, up, dt, login);
    if (Math.abs(x - y) <= 0.0017) return null;
    x < y ? up = mid : lw = mid + 1;
  }
  return String.fromCharCode(lw);
}
function crack(login) {
  let i, t, rs = '';
  for (i = 0; ; ++i) {
    t = cycle(login, i);
    if (!t) break;
    rs += t;
  }
  return rs;
}

function validParentheses(ex) {
	let m = ex
	while (/\(\)/.test(m)){
		m = m.replace(/\(\)/, '')
}
	return m.length === 0
}

function breakPieces(shape) {
  let shapeArray = shape.split('\n').map(row => row.split('').map(char => char === ' ' ? 0 : char));
  shapeArray.push([]);
  shapeArray.unshift([]);

  let pieceNumber = 1;
  mapCells(shapeArray, (cell, rowIndex, colIndex) => {
    if (!shapeArray[rowIndex][colIndex] && markPiece(rowIndex, colIndex)) {
      pieceNumber++;
    }
  });

  let pieces = [];
  while (--pieceNumber > 0) {
    pieces.push(extractPiece(pieceNumber));
  }
  return pieces;

  function mapCells(array, fn) {
    return array.map((row, i) => row.map((cell, j) => fn(cell, i, j)));
  }

  function markPiece(row, col) {
    if (isOutOfBounds(row, col) || shapeArray[row][col] === '*') return false;
    if (shapeArray[row][col]) return true;
    shapeArray[row][col] = pieceNumber;
    [[row - 1, col], [row, col + 1], [row + 1, col], [row, col - 1]].forEach(([r, c]) => {
      if (!markPiece(r, c)) shapeArray[row][col] = '*';
    });
    return shapeArray[row][col] === pieceNumber;
  }

  function extractPiece(pieceNum) {
    return formatPiece(fixPieceCorners(mapCells(shapeArray, (cell, row, col) => ('-|+'.includes(cell) && isAdjacent(row, col)) ? cell : ' ')));

    function isAdjacent(row, col) {
      let count = 0;
      [-1, 0, 1].forEach(dr => [-1, 0, 1].forEach(dc => count += Number(shapeArray[row + dr][col + dc] === pieceNum)));
      return count > 0;
    }

    function fixPieceCorners(shape) {
      const replaceCorner = (row, col) => {
        const vertical = shape[row - 1][col] === '|' || shape[row + 1][col] === '|';
        const horizontal = shape[row][col - 1] === '-' || shape[row][col + 1] === '-';
        return vertical && horizontal ? '+' : vertical ? '|' : '-';
      };
      return mapCells(shape, (cell, row, col) => cell === '+' ? replaceCorner(row, col) : cell);
    }

    function formatPiece(shape) {
      let leftMargin = Infinity;
      return shape.map(row => row.join(''))
        .filter(row => row.trim())
        .map(row => {
          row = row.trimRight();
          leftMargin = Math.min(leftMargin, row.length - row.trim().length);
          return row;
        })
        .map(row => row.substr(leftMargin))
        .join('\n');
    }
  }

  function isOutOfBounds(row, col) {
    return row < 0 || col < 0 || row >= shapeArray.length || col >= shapeArray[row].length;
  }
}

function integerSquareRoot(input) {
  const multiply = (num1, num2) => {
    let product = num1.split('').map(digit => digit * num2);
    for (let i = product.length - 1; i > 0; i--) {
      product[i - 1] += Math.floor(product[i] / 10);
      product[i] %= 10;
    }
    product = product.join('').replace(/^0+/, '');
    return product.length ? product : '0';
  };
  const lessThanOrEqual = (num1, num2) => {
    num1 = num1.padStart(Math.max(num1.length, num2.length), '0');
    num2 = num2.padStart(Math.max(num1.length, num2.length), '0');
    if (num1 === num2) return true;
    for (let i = 0; i < num1.length; i++) {
      if (num1[i] < num2[i]) return true;
      if (num1[i] > num2[i]) return false;
    }
    return false;
  };
  const subtract = (num1, num2) => {
    num1 = num1.padStart(Math.max(num1.length, num2.length), '0');
    num2 = num2.padStart(Math.max(num1.length, num2.length), '0');
    let difference = num1.split('').map((digit, index) => digit - num2[index]);
    for (let i = difference.length - 1; i > 0; i--) {
      if (difference[i] < 0) {
        difference[i] += 10;
        difference[i - 1]--;
      }
    }
    difference = difference.join('').replace(/^0+/, '');
    return difference.length ? difference : '0';
  };

  if (input.length % 2 !== 0) input = '0' + input;
  let result = '0';
  let dop = '0';

  for (let i = 0; i < input.length; i += 2) {
    dop += input[i] + input[i + 1];
    let multRes = multiply(result, '2');
    let j = 0;
    while (lessThanOrEqual(multiply(multRes + j, '' + j), dop) && j < 10) j++;
    result += --j;
    dop = subtract(dop, multiply(multRes + j, '' + j));
  }

  result = result.replace(/^0+/, '');
  return result.length ? result : '0';
}

const combinations = {
  'RR': 'R',
  'GG': 'G',
  'BB': 'B',
  'RG': 'B',
  'GR': 'B',
  'RB': 'G',
  'BR': 'G',
  'GB': 'R',
  'BG': 'R'
};

const expReduce = x => Math.log(x) / Math.log(3);

function triangle(row) {
  const strlen = row.length;

  if (strlen === 1) return row[0];

  const n = Math.floor(expReduce(strlen - 1));
  const needLen = Math.pow(3, n) + 1;

  if (strlen === needLen) return combinations[row[0] + row[strlen - 1]];

  const size = strlen - needLen + 1;
  const firstColor = triangle(row.substring(0, size));
  const secondColor = triangle(row.substring(strlen - size));

  return combinations[firstColor + secondColor];
}

function solution(vdb) {
    if (vdb.length % 2 !== 0) vdb += '_';
    return vdb.match(/.{1,2}/g)|| [];
}

function Archiver() {
    let temperature = null;
    let archive = [];
    Object.defineProperty(this, 'temperature', {
      get: ()=> temperature,
      set: (val)=> {
        temperature = val;
        archive.push({ date: new Date(), val: temperature });
      }
    });
    this.getArchive = ()=>archive;
}

function defaultArguments(func, params) {
  let args = func.toString()
    .replace(/\/\*.*?\*\//g, '')
    .replace(/\/\/.*/gm, '')
    .replace(/\s+/g, '').match(/\(.*?\)/).join('')
    .replace(/[\(\)]/gi, '').split(',');
  function patchedFN(...el) {
    el = el.map(a => { return a == undefined ? 'undefined' : a });
    for (i in params) {
      if (args.indexOf(i) != -1 && (el[args.indexOf(i)] == undefined))
        el[args.indexOf(i)] = params[i]
    }
    el = el.map(x => { return x == 'undefined' ? undefined : x })
    patchedFN.toString = function () {
      return func.toString()
    }
    return el.length != args.length ? NaN : func(...el)
  };
  return patchedFN;
}

function namespace(root, path, value){
  let arrSplittedPath = path.split`.`
  let nameProp = arrSplittedPath.pop()
  let base = root
  arrSplittedPath.map((part) => {
    base[part] = base[part] || {}
    base = base[part]
  })
  if (arguments.length > 2) base[nameProp] = value
  else return base[nameProp]
}

let query = function () {
  const chain = {};
  const whereExp = [];
  const havingExp = [];
  const tunel = row => row;
  let source = [];
  let selector = null;
  let order = [];
  let group = [];

  chain.select = function (s) {
    if (selector != null) throw new Error('Duplicate SELECT');
    selector = s || false;
    return chain;
  };

  chain.from = function () {
    if (source.length > 0) throw new Error('Duplicate FROM');
    source = Array.from(arguments);
    return chain;
  };

  chain.where = function () {
    whereExp.push(Array.from(arguments));
    return chain;
  };

  chain.having = function () {
    havingExp.push(Array.from(arguments));
    return chain;
  };

  chain.groupBy = function () {
    if (group.length > 0) throw new Error('Duplicate GROUPBY');
    group = Array.from(arguments);
    return chain;
  };

  chain.orderBy = function () {
    if (order.length > 0) throw new Error('Duplicate ORDERBY');
    order = Array.from(arguments);
    return chain;
  };

  chain.execute = function () {
    const midle = [];
    const datGroup = [];

    let data = [];
    let cnt = 0;

    if (source.length > 1) {

      source.forEach(() => data.push([]));

      source.forEach((el,i) => {
        data[i] = el.slice(0)
      });

      function tableRecurs(rec, ar) {
        if (rec.length === 0) {
          midle.push(ar.slice(0));
        } else {
          for (let i = 0; i < rec[0].length; i++) {
            ar.push(rec[0][i]);
            tableRecurs(rec.slice(1), ar);
            ar.splice(-1, 1);
          }
        }
      }

      tableRecurs(data, []);

      data = [];
      midle.forEach(row => {
        if (whereExp.every(wher => wher.some(expWher => expWher(row)))) {
          data.push(row);
        }
      });

    } else if (source.length === 1) {

      source[0].forEach(row => {
        if (whereExp.every(wher => wher.some(expWher => expWher(row)))) {
          data.push(row);
        }
      });

    } else data = [];

    if (group.length > 0) {
      const dtMap = new Map();
      const sym = Symbol('system');

      data.forEach(row => {
        let mp = dtMap;

        group.forEach(backGroup => {
          let gr = backGroup(row);
          mp.set(gr, mp.get(gr) || new Map());
          mp = mp.get(gr);
        });

        mp.set(sym, mp.get(sym) || []);
        let arr = mp.get(sym);
        arr.push(row);
        mp.set(sym, arr);
      });

      function recurse(recMap, grp) {
        if (recMap.get(sym) !== undefined) {
          recMap.get(sym).forEach(e => grp.push(e));
        } else {
          for (let [k, v] of recMap) {
            k = /\d+/.test(k) ? Number(k) : k;
            let row = [k, []];
            recurse(v, row[1]);
            grp.push(row);
          }
        }
      }

      recurse(dtMap, datGroup);

      datGroup.forEach(lnUp => { if (havingExp.every(hav => hav.some(expHav => expHav(lnUp)))) midle.push(lnUp) });
      data = midle;
    }

    data = data.map(selector || tunel);
    order.forEach(backOrder => data = data.sort(backOrder));

    return data
  };

  return chain;
}

Array.prototype.sameStructureAs = function (arr) {
  if (this.length !== arr.length) return false
  for (let i = 0; i < this.length; ++i)
    if ((Array.isArray(this[i]) && !this[i].sameStructureAs(arr[i])) ||
       (!Array.isArray(this[i]) && Array.isArray(arr[i]))) return false
  return true
}

function formatDuration(sec) {
  if (sec === 0) return "now";

  const obj = [
    { label: 'year', duration: 365 * 24 * 60 * 60 },
    { label: 'day', duration: 24 * 60 * 60 },
    { label: 'hour', duration: 60 * 60 },
    { label: 'minute', duration: 60 },
    { label: 'second', duration: 1 }
  ];

  let result = [];

  for (let i = 0; i < obj.length; i++) {
    const period = obj[i];
    const val = Math.floor(sec / period.duration);

    if (val > 0) {
      result.push(val + ' ' + period.label + (val === 1 ? '' : 's'));
      sec %= period.duration;
    }
  }

  return result.length > 1 ? result.slice(0, -1).join(', ') + ' and ' + result[result.length - 1] : result[0];
}

function parseMolecule(rec) {
  const El = '[A-Z][a-z]?';
  const fr1 = new RegExp(`(${El})(\\d*)`, 'g');
  const fr2 = new RegExp(`${El}`, 'g');
  const reg = [
    new RegExp(/(\([^)]+\))(\d*)/, 'g'),
    new RegExp(/(\[[^)]+\])(\d*)/, 'g'),
    new RegExp(/(\{[^)]+\})(\d*)/, 'g')
  ]
  result = rec.replace(fr1, (e, st, nm) => st.repeat(nm || 1))
  const srep = (e, st, nm) => st.slice(1, -1).repeat(nm || 1)
  reg.forEach(exp => result = result.replace(exp, srep))
  return (result.match(fr2) || []).reduce((obj, element) => (obj[element] = obj[element] + 1 || 1, obj), {})
}

function orderWeight(str) {
    const sumD = num => num.split('').reduce((acc, digit) => acc + parseInt(digit), 0);

    const stWeights = str.split(' ')
        .sort((numb1, numb2) => {
            const weightDiff = sumD(numb1) - sumD(numb2);
            return weightDiff !== 0 ? weightDiff : numb1.localeCompare(numb2);
        })
        .join(' ');

    return stWeights;
}

function phone(phoneBook, num) {
  const lines = phoneBook.split('\n');
  const phoneRegex = /(\+\d{1,2}-\d{3}-\d{3}-\d{4})/g;
  const nameRegex = /<([^>]*.)>/g;
  const contacts = {};

  lines.forEach(line => {
    if(line.length > 15){

    let phone = '';
    let newStr = line.replace(phoneRegex, (match) => {
      phone = match;
      return '';
    })
    let name = '';
    let adress = newStr.replace(nameRegex, (match) => {
      name = match;
      return '';
    })
    phone = phone.slice(1)
    name = name.slice(1, -1)
    adress = adress.replace(/[\/\\\$:;,!\?\*]/g, '').replace(/[_]/,' ').replace(/  +/g, ' ').trim()

    if(contacts[phone]) contacts[phone] = "Error => Too many people: "+phone
      else contacts[phone] = `Phone => ${phone}, Name => ${name}, Address => ${adress}`

    }
  });

  if (contacts[num]) return contacts[num]
  else return "Error => Not found: "+num
}

  function isGreaterOrEqualString(num1, num2) {
    return num1.length === num2.length ? num1 >= num2 : num1.length > num2.length;
}

function subtractStrings(num1, num2) {
    let flag = 0;
    let digit1, digit2, difference, result = '';

    for (let i = 0; i < num1.length; i++) {
        digit1 = +num1[num1.length - i - 1];
        digit2 = +num2[num2.length - i - 1] || 0;
        difference = digit1 - digit2 - flag;

        if (difference < 0) { difference += 10; flag = 1;}
          else flag = 0;


        result = String(difference) + result;
    }

    while (result[0] === '0' && result.length > 1)
        result = result.slice(1);


    return result;
}

function divideStrings(dividend, divisor) {
    let quotient = '0', remainder = '0';

    for (let i = 0; i < dividend.length; i++) {
        remainder = remainder === '0' ? dividend[i] : remainder + dividend[i];

        let count = 0;
        while (isGreaterOrEqualString(remainder, divisor)) {
            remainder = subtractStrings(remainder, divisor);
            count++;
        }

        quotient = quotient === '0' ? String(count) : quotient + String(count);
    }

    return [quotient, remainder];
}

export function score(dice: number[]): number {
    let score = 0
    const count: {[key: number]: number} = {}

    for (const value of dice) {
        if (count[value]) count[value]++
         else count[value] = 1
    }

    for (const [value, freq] of Object.entries(count)) {
        const val = parseInt(value)

        if (freq >= 3) {
            if (val === 1) score += 1000 + 100 * (freq - 3)
             else score += val * 100

            if (val === 5) score +=  (freq - 3) * 50

        } else {
            if (val === 1) score += 100 * freq
             else if (val === 5) score += 50 * freq
        }
    }

    return score
}

def on_line(points):
    unique_points = set(points)

    if len(unique_points) < 2:
        return True

    unique_x = set(x for x, y in unique_points)
    if len(unique_x) == 1:
        return True

    x1, y1 = list(unique_points)[0]
    x2, y2 = list(unique_points)[1]
    if x2 - x1 == 0:
        slope = None
    else:
        slope = (y2 - y1) / (x2 - x1)

    for x, y in unique_points:
        if slope is None:
            if x != x1:
                return False
        elif y != y1 + slope * (x - x1):
            return False

    return True

def persistence(num):
    count = 0
    while num >= 10:
        product = 1
        for digit in str(num):
            product *= int(digit)
        num = product
        count += 1
    return count

def alphabet_position(text):
    result = []
    for char in text.lower():
        if char.isalpha():
            result.append(str(ord(char) - ord('a') + 1))

    return ' '.join(result)

def duplicate_count(input_string):
    char_count = {}
    duplicates = 0

    input_string = input_string.lower()

    for char in input_string:
        if char.isalnum():
            if char in char_count:
                char_count[char] += 1
                if char_count[char] == 2:
                    duplicates += 1
            else:
                char_count[char] = 1

    return duplicates
     

def find_outlier(integers):
    odds = [num for num in integers if num % 2 != 0]
    evens = [num for num in integers if num % 2 == 0]

    return odds[0] if len(odds) == 1 else evens[0]

def count_bits(n):
    return bin(n).count('1')

def create_phone_number(n):
    phone_number = "({}{}{}) {}{}{}-{}{}{}{}".format(*n)
    return phone_number

def digital_root(n):
    while n > 9:
        n = sum(int(digit) for digit in str(n))
    return n

def square_digits(nm):
    digits = [int(d)**2 for d in str(nm)]

    result = int(''.join(map(str, digits)))

    return result

def even_or_odd(number):
    if number % 2 == 0:
        return "Even"
    else:
        return "Odd"

export class Challenge {
    static solution(rim: number): number {
        if (rim < 0) return 0

        let cnt = 0
        for (let i = 3; i < rim; i++) {
            if (i % 3 === 0 || i % 5 === 0) cnt += i
        }

        return cnt
    }
}

function allContinents(developers) {
    const requiredZones = new Set(['Africa', 'Americas', 'Asia', 'Europe', 'Oceania'])
    const foundZones = new Set()

    for (let developer of developers) {
        if (requiredZones.has(developer.continent)) foundZones.add(developer.continent)
    }

    for (let zone of requiredZones) {
        if (!foundZones.has(zone)) return false
    }

    return true
}

const findSenior = list => {
  const ageMax = list.reduce((maxVal, devp) => Math.max(maxVal, devp.age), 0)
  return list.filter(devp => devp.age === ageMax)
}

const countDevelopers = list => list.filter(dev => dev.language === 'JavaScript' && dev.continent === 'Europe').length;

function bang() {
  try {
    let c;
    c.a = c.b;
  } catch (e) {
    let th = ['th', 'row'].join``;
    e.message = ['Just ', th, ' like this!'].join``;

    (function* () { })()[th](e)
  }
}

function pathFinder(kl){
  if (kl.length === 1) return true
  let mx =  kl.split('\n').map(r=>r.split``),
      m = mx.length-1,
      obArr = [{x:0,y:0,all:0}];
  while(obArr.length){
    const {x,y,all} = obArr.shift();
    const tryArr = [
      [x+1,y],
      [x,y+1],
      [x-1,y],
      [x,y-1]
    ];
    if(x==m && y==m) return true;
    mx[x][y]='W';
    tryArr.forEach(([a,b])=>{
      if(mx[a] && mx[a][b] && mx[a][b] !== 'W'){
        obArr.push({x:a,y:b,all:all+1});
        mx[a][b] = 'W';
      }
    })
  }
  return false;
}

function pathFinder(maze){
  if (maze.length === 1) return true
  let mx =  maze.split('\n').map(r=>r.split``)
  let obArr = [{x:0,y:0,all:0}];
  let m = mx.length-1;
  while(obArr.length){
    const {x,y,all} = obArr.shift();
    if(x==m && y==m) return true;
    mx[x][y]='W';
    [[x+1,y],[x-1,y],[x,y+1],[x,y-1]].forEach(([a,b])=>{
      if(mx[a] && mx[a][b] && mx[a][b] != 'W'){
        obArr.push({x:a,y:b,all:all+1});
        mx[a][b] = 'W';
      }
    })
  }
  return false;
}

function properFractions(num) {
	if (num === 1) return 0
	let res = num, q = num
	for (let j = 2; j <= Math.sqrt(q); j++) {
		if (q % j === 0) {
			res = res / j * (j - 1)
			while (q % j === 0) q /= j
		}
	}
	if (q > 1) res = (q - 1) * res / q
	return res
}

//Fenwick Tree
function treeUpd(i, v, n, tree) {
	while (i < n) {
		tree[i] += v
		i |= i + 1
	}
}
function toSum(m, tree) {
	let sumTree = 0
	while (m >= 0) {
		sumTree += tree[m]
		m &= m + 1
		m--
	}
	return sumTree
}
function maxSum(inpArr, rng) {
	const tree = inpArr.slice(0)
	const len = inpArr.length
	for (let i = 0; i < len; i++) {
		let q = i | (i + 1)
		if (q < len) tree[q] += tree[i]
	}
	let thisMax = Number.NEGATIVE_INFINITY
	for (let [start, end, num] of rng) {
		let sub = num - inpArr[start]
		treeUpd(start, sub, len, tree)
		inpArr[start] = num
		const delta = toSum(end, tree) - toSum(start - 1, tree)
		if (delta > thisMax) thisMax = delta
	}
	return thisMax
}

const toNum = {
    zero: 0,
    one: 1,
    two: 2,
    three: 3,
    four: 4,
    five: 5,
    six: 6,
    seven: 7,
    eight: 8,
    nine: 9,
    ten: 10,
    eleven: 11,
    twelve: 12,
    thirteen: 13,
    fourteen: 14,
    fifteen: 15,
    sixteen: 16,
    seventeen: 17,
    eighteen: 18,
    nineteen: 19,
    twenty: 20,
    thirty: 30,
    forty: 40,
    fifty: 50,
    sixty: 60,
    seventy: 70,
    eighty: 80,
    ninety: 90
};
const toBig = {
  hundred: 100,
  thousand: 1000,
  million: 1000000
};
function parseInt(sym) {
  let splited = sym.split(/ |-/)
  let rd = splited.reduce((ac, el)=> {
    if (toNum[el]) ac += toNum[el]
    if (toBig[el]) ac += toBig[el] * (ac % toBig[el]) - (ac % toBig[el])
        return ac
    },0)
  return rd
}

export function doubles(one:number, sec:number):number {
	let count = 1, flot = 0.0
	while (count <= sec) {
		let os = count + 1.0,
		prom = 1.0,
		mes = 1
		while (mes <= one) {
			prom = prom * os * os
			if (prom > 1e16) break
			flot += 1 / (prom * mes)
			mes++
		}
		count++
	}
	return flot
}

class Wand {
	constructor(zaklinaniya = {}) {
		this.vizov = [];

		Object.assign(this, zaklinaniya);
		const proxy = new Proxy(this, {
			get: (tg, pr) => {
				const val = tg[pr];
				if (typeof val === 'function') {
					return () => {
						tg.vizov.unshift(pr);
						const rs = tg[pr].call(proxy);
						if (tg.vizov.length > MAX_PRIOR_SPELLS) tg.vizov.pop();
						return rs;
					}
				}
				return tg[pr];
			},
		});
		return proxy
	}
	prioriIncantatem() {
		return this.vizov.slice(1);
	}
	deletrius() {
		this.vizov = ['deletrius'];
	}
}

ELEMENTS={'H': 'Hydrogen', 'He': 'Helium', 'Li': 'Lithium', 'Be': 'Beryllium', 'B': 'Boron', 'C': 'Carbon', 'N': 'Nitrogen', 'O': 'Oxygen', 'F': 'Fluorine', 'Ne': 'Neon', 'Na': 'Sodium', 'Mg': 'Magnesium', 'Al': 'Aluminium', 'Si': 'Silicon', 'P': 'Phosphorus', 'S': 'Sulfur', 'Cl': 'Chlorine', 'Ar': 'Argon', 'K': 'Potassium', 'Ca': 'Calcium', 'Sc': 'Scandium', 'Ti': 'Titanium', 'V': 'Vanadium', 'Cr': 'Chromium', 'Mn': 'Manganese', 'Fe': 'Iron', 'Co': 'Cobalt', 'Ni': 'Nickel', 'Cu': 'Copper', 'Zn': 'Zinc', 'Ga': 'Gallium', 'Ge': 'Germanium', 'As': 'Arsenic', 'Se': 'Selenium', 'Br': 'Bromine', 'Kr': 'Krypton', 'Rb': 'Rubidium', 'Sr': 'Strontium', 'Y': 'Yttrium', 'Zr': 'Zirconium', 'Nb': 'Niobium', 'Mo': 'Molybdenum', 'Tc': 'Technetium', 'Ru': 'Ruthenium', 'Rh': 'Rhodium', 'Pd': 'Palladium', 'Ag': 'Silver', 'Cd': 'Cadmium', 'In': 'Indium', 'Sn': 'Tin', 'Sb': 'Antimony', 'Te': 'Tellurium', 'I': 'Iodine', 'Xe': 'Xenon', 'Cs': 'Caesium', 'Ba': 'Barium', 'La': 'Lanthanum', 'Ce': 'Cerium', 'Pr': 'Praseodymium', 'Nd': 'Neodymium', 'Pm': 'Promethium', 'Sm': 'Samarium', 'Eu': 'Europium', 'Gd': 'Gadolinium', 'Tb': 'Terbium', 'Dy': 'Dysprosium', 'Ho': 'Holmium', 'Er': 'Erbium', 'Tm': 'Thulium', 'Yb': 'Ytterbium', 'Lu': 'Lutetium', 'Hf': 'Hafnium', 'Ta': 'Tantalum', 'W': 'Tungsten', 'Re': 'Rhenium', 'Os': 'Osmium', 'Ir': 'Iridium', 'Pt': 'Platinum', 'Au': 'Gold', 'Hg': 'Mercury', 'Tl': 'Thallium', 'Pb': 'Lead', 'Bi': 'Bismuth', 'Po': 'Polonium', 'At': 'Astatine', 'Rn': 'Radon', 'Fr': 'Francium', 'Ra': 'Radium', 'Ac': 'Actinium', 'Th': 'Thorium', 'Pa': 'Protactinium', 'U': 'Uranium', 'Np': 'Neptunium', 'Pu': 'Plutonium', 'Am': 'Americium', 'Cm': 'Curium', 'Bk': 'Berkelium', 'Cf': 'Californium', 'Es': 'Einsteinium', 'Fm': 'Fermium', 'Md': 'Mendelevium', 'No': 'Nobelium', 'Lr': 'Lawrencium', 'Rf': 'Rutherfordium', 'Db': 'Dubnium', 'Sg': 'Seaborgium', 'Bh': 'Bohrium', 'Hs': 'Hassium', 'Mt': 'Meitnerium', 'Ds': 'Darmstadtium', 'Rg': 'Roentgenium', 'Cn': 'Copernicium', 'Uut': 'Ununtrium', 'Fl': 'Flerovium', 'Uup': 'Ununpentium', 'Lv': 'Livermorium', 'Uus': 'Ununseptium', 'Uuo': 'Ununoctium'}

def elemental_forms(inp):
    result=recurse(inp, [], set())
    return [list(i) for i in result]

def recurse(txt, pr, sc):
    if not txt:
        sc.add(tuple(pr))
        return
    for i in range(3):
        elm=txt[:i+1].capitalize()
        if elm in ELEMENTS:
            recurse(txt[i+1:], pr+[f"{ELEMENTS[elm]} ({elm})"], sc)
    return sc

def hamster_me(inp, mes):
    all=0
    symDCT={}
    cash=sorted(set(inp))
    for j in range(len(cash)-1):
        sch=1
        symDCT[cash[j]]=cash[j]+str(sch)
        while chr(ord(cash[j])+sch)<chr(ord(cash[j+1])):
            symDCT[chr(ord(cash[j])+sch)]=cash[j]+str(sch+1)
            sch+=1
        all+=sch
    for j in range(26-all):
        symDCT[chr(ord('a')+(ord(cash[-1])-ord('a')+j)%26)]=cash[-1]+str(j+1)
    res=''.join(symDCT[i] for i in mes)
    return res

from copy import deepcopy

def next_gen(matrix):
    lst=deepcopy(matrix)
    dimY=len(matrix)
    for i in range(0,dimY):
        dimX=len(matrix[i])
        for j in range(0,dimX):
            tp=0
            cnt=0
            for x in range(i-1, i+2):
                for y in range(j-1, j+2):
                    if x<0 or y<0 or x>=len(matrix) or y>=len(matrix[i]) or (x==i and y==j):
                        continue
                    if lst[x][y]==1:
                        cnt+=1
                    tp+=1
            if lst[i][j]==1 and (cnt<2 or cnt>3):
                matrix[i][j]=0
            elif lst[i][j]==0 and cnt==3:
                matrix[i][j]=1
    return matrix

$
=
(
_
=
[
]
,
_
[
0
]
=
(
[
]
+
{
}
)
+
[
]
+
!
[
]
+
[
]
[
[
]
]
,
_
[
1
]
=
(
!
!
[
]
+
[
]
)
[
1
]
,
_
[
2
]
=
_
[
0
]
[
5
]
+
_
[
0
]
[
1
]
+
_
[
0
]
[
3
*
7
]
+
_
[
0
]
[
9
+
9
]
+
_
[
0
]
[
6
]
+
_
[
1
]
+
_
[
0
]
[
4
*
5
]
+
_
[
0
]
[
5
]
+
_
[
0
]
[
6
]
+
_
[
0
]
[
1
]
+
_
[
1
]
,
_
[
3
]
=
_
[
0
]
[
6
]
+
_
[
0
]
[
1
]
+
$
[
1
]
+
_
[
0
]
[
6
]
+
_
[
1
]
+
_
[
0
]
[
5
*
5
]
+
_
[
0
]
[
3
*
7
]
+
$
[
2
]
,
_
[
4
]
=
_
[
0
]
[
3
*
5
]
+
_
[
1
]
+
_
[
0
]
[
1
]
+
(
3
*
7
+
1
)
[
_
[
3
]
]
(
4
*
9
)
+
$
[
0
]
+
(
2
*
8
+
1
)
[
_
[
3
]
]
(
4
*
9
)
+
_
[
0
]
[
9
+
7
]
+
_
[
1
]
+
$
[
0
]
+
_
[
0
]
[
1
]
+
_
[
0
]
[
3
*
7
+
1
]
+
_
[
0
]
[
4
]
,
_
[
5
]
=
`
`
[
_
[
2
]
]
[
_
[
4
]
]
,
_
[
6
]
=
_
[
5
]
(
4
*
9
*
2
)
+
_
[
0
]
[
4
]
+
_
[
0
]
[
2
*
8
+
1
]
+
_
[
0
]
[
2
*
8
+
1
]
+
_
[
0
]
[
1
]
+
_
[
5
]
(
4
*
9
+
8
)
+
_
[
0
]
[
7
]
+
_
[
5
]
(
9
*
9
+
6
*
6
+
2
)
+
_
[
0
]
[
1
]
+
_
[
1
]
+
_
[
0
]
[
2
*
8
+
1
]
+
_
[
0
]
[
9
+
9
+
4
]
+
_
[
5
]
(
3
*
9
+
6
)
,
`
`
[
_
[
0
]
[
2
*
9
]
+
_
[
0
]
[
2
*
8
+
1
]
+
_
[
0
]
[
5
*
5
]
+
_
[
0
]
[
5
]
+
_
[
0
]
[
4
]
]
[
(
9
+
2
)
[
_
[
3
]
]
(
4
*
9
)
+
_
[
0
]
[
5
*
5
]
+
_
[
0
]
[
3
*
7
]
+
_
[
0
]
[
3
*
7
+
1
]
]
(
_
[
6
]
)
)

zeroOrOne=(j,y)=>y[0]
.map(($,I)=>y.map(v=>v[I])
.sort()[j/2|0])

export function going(m: number): number {
  let total = 1, par = 1
  for (let i = m; i > 1; i--) {
    par /= i
    total += par
  }
  let res = total.toString().substring(0, 8)
  return parseFloat(res)
}

export const determinant = (mtx:number[][]): number =>{
  const  reds = (a:number, x: number, i:number) =>{
       const arg = mtx.slice(1).map(f => f.filter(($, c) => c !== i))
       return a + (i % 2 === 0 ? 1 : -1) * x * determinant(arg)
    }
  if (mtx.length === 1) return mtx[0][0]
  else return mtx[0].reduce(reds,0)
}

solarDate=q=>(j=30,--q<186?j=31:q-=6,q-=($=q%j),$+1+", "+"FOKTMSMAADBE"[o=q/j]+"arhiohebzeas"[o])

let fibmemo = {
	0: 0n,
	1: 1n,
	2: 1n,
	3: 2n,
	4: 3n,
	5: 5n,
	6: 8n
}
function fib(fibN) {
	if (fibN < 0 && fibN % 2 === 0) return -fib(Math.abs(fibN))
	else if (fibN < 0 && fibN % 2 !== 0) return fib(Math.abs(fibN))
	else {
		if (fibmemo[fibN] === undefined) {
			if (fibN % 2) {
				let first = fib((fibN - 1) / 2)
				let second = fib((fibN + 1) / 2)
				fibmemo[fibN] = first ** 2n + second ** 2n
			} else {
				let first = fib(fibN / 2 - 1)
				let second = fib(fibN / 2)
				fibmemo[fibN] = (2n * first + second) * second
			}
		}
	}
	return fibmemo[fibN]
}

function maxSum(mass,range){
  let ms = [0],  vse = 0
  for (let i of mass) ms.push(vse += i)
  let res = range.map(([x, y]) => ms[y + 1] - ms[x])
  return Math.max(...res)
}

const maxSum = (ms,dpz) => {
  const rd = (ac, el) => ac + el
  const sumDP = ([bg, fin]) => ms
  .slice(bg, fin + 1)
  .reduce(rd)
  return Math.max(...dpz.map(v => sumDP(v)))
}

const debounce = (fn, delay, immediate) => {
  let timeClosure = Number.NEGATIVE_INFINITY
  return function(){
    let timeNow = Date.now()
    if(timeNow - timeClosure >= delay)
      if(immediate === true) fn.apply(this, arguments)
      else setTimeout(()=>fn.apply(this, arguments),delay)
    timeClosure = timeNow
  }
};

export function uncompress(data: string): number[] {
	let com = data.split(','),
		res: number[] = [];
	let rg = /^(-?\d+)-(-?\d+)(\/(\d+))?$/;
	for (let s = 0; s < com.length; s++) {
		if (rg.test(com[s])) { // for intervals
			let [beg, fin, cnt] = com[s]
				.replace(rg, (_, m, n, o) => m + ' ' + n + (o ? ' ' + o.slice(1) : ''),)
				.split(' ')
				.map(Number);
			if (!cnt) cnt = 1;
			for (let j = beg; j !== fin; j += fin < beg ? -cnt : cnt) res.push(j);
			res.push(fin);
		} else if (com[s].includes('*')) { // for count
			let [num, c] = com[s].replace(/\*/g, ' ').split(' ').map(Number);
			res = res.concat(new Array(c).fill(num));
		} else res.push(+com[s]); // to num
	}
	return res;
}

export function dblLinear(mn:number):number {
    let st = 1
    if (mn === 0) return st
    let collect = new Set()
    collect.add(st)
    while (collect.size <= mn) {
      st++
      if (collect.has((st - 1)/2) || collect.has((st - 1)/3)) collect.add(st)
    }
    return st
}

f
=
[
,
p
,
,
t
,
,
o
,
,
r
,
,
l
,
,
n
,
,
i
,
,
d
,
,
s
,
,
b
]
=
`
s
t
o
p
b
i
l
d
j
n
`
f
=
[
]
[
s
+
o
+
n
+
b
]
[
l
+
n
+
b
+
d
]
(
`
H
e
l
l
o
,

w
o
r
l
d
!
`
[
p
+
r
+
i
+
n
+
t
]
`
`
,
[
]
+
[
]
)

with(Math)circleIntersection=([x,y],[i,j],D)=>(-sin($=2*acos(hypot(i-x,j-y)/D/2))+$)*D**2|0;

const justify = (st, dlina) => {
	let oneWords = st.split(' ')
	let stroks = []
	let lineEnd = oneWords.reduce((ln, word) => {
		if (ln) {
			if (ln.length + word.length + 1 <= dlina) return ln + ' ' + word
			stroks.push(ln)
		}
		return word
	})
	stroks = stroks.map(ln => {
		if (ln.indexOf(' ') >= 0)
			for (let dlinaStroki = ln.length; dlinaStroki < dlina;)
				ln = ln.replace(/ +/g, (probels) => {
					return probels + (dlinaStroki++ < dlina ? ' ' : '')
				})
		return ln
	})
	lineEnd && stroks.push(lineEnd)
	return stroks.join('\n')
}

def elevator_distance(ar):
    # your code here
    myres = 0
    for m in range(len(ar)-1):
        myres += abs(ar[m] - ar[m+1])
    return myres

# return
# masked
# string
def maskify(cardCredit):
    return (len(cardCredit)-4) * "#" + cardCredit[-4:]

def scramble(str1, str2):
    for c in set(str2):
        if str1.count(c) < str2.count(c):
            return False
    return True

def alphanumeric(passwAlphanum):
    return passwAlphanum.isalnum()

function validateBattlefield(base) {
	let cn = 0
	let os = 0
	for (let row = 0; row < base.length; row++) {
		for (let col = 0; col < base.length; col++) {
			if (base[row][col] === 0) continue;
			os++
			if (row !== 0 && col !== 0)
				if (base[row - 1][col - 1] === 1) return false

			if (row !== 0)
				if (base[row - 1][col + 1] === 1) return false

			if (col !== base.length - 1)
				if (base[row][col + 1] === 1) cn++

			if (row !== base.length - 1)
				if (base[row + 1][col] === 1) cn++

		}
	}
	if (cn === 10 && os === 20) return true;
	return false;
}

const lines = {
	'A': ['B', 'CB', 'D', 'E', 'F', 'GD', 'H', 'IE'],
	'D': ['A', 'B', 'C', 'E', 'FE', 'G', 'H', 'I'],
	'G': ['AD', 'B', 'CE', 'D', 'E', 'F', 'H', 'IH'],
	'B': ['A', 'C', 'D', 'E', 'F', 'G', 'HE', 'I'],
	'E': ['A', 'B', 'C', 'D', 'F', 'G', 'H', 'I'],
	'H': ['A', 'BE', 'C', 'D', 'E', 'F', 'G', 'I'],
	'C': ['B', 'AB', 'D', 'E', 'F', 'GE', 'H', 'IF'],
	'F': ['A', 'B', 'C', 'DE', 'E', 'G', 'H', 'I'],
	'I': ['AE', 'B', 'CF', 'D', 'E', 'F', 'GH', 'H']
}
type S = 'A' | 'D' | 'G' | 'B' | 'E' | 'H' | 'C' | 'F' | 'I'

const validVariants = (circle: string, visited: string) => {
	return lines[circle as S].reduce((arr: string[], pos) => {
		let imp = pos.slice(0,1), nast;
		if (pos.length > 1)  nast = pos[1]
		if (visited.indexOf(imp) === -1 &&	(!nast || visited.indexOf(nast) !== -1)) arr.push(imp)
		return arr
	}, [])
}

export const calculateCombinations = (beginCircle: string, length: number): number => {
	if (beginCircle.length > length) return 0
	if (beginCircle.length === length) return 1
	let all = 0
	let atEnd = beginCircle.slice(-1)
	let vozm = validVariants(atEnd, beginCircle)
	if (beginCircle.length + 1 === length) return vozm.length
	for (let newPosition of vozm) {
		all += calculateCombinations(beginCircle + newPosition, length)
	}
	return all
}

const cashFactorial = {}
const minS = (a, b) => a.length < b.length ? a : b.length < a.length ? b : a < b ? a : b
function mulStr(a, b) {
	a = String(a)
	b = String(b)
	let min = minS(a,b)
	let max = min === a ? b : a
	let sArr = max.split('').reverse()
	let result = [], ost = 0
	for (let i = 0; i < sArr.length; i++) {
		let spb = +sArr[i] * min + ost
		let des = spb % 10
		ost = (spb - des) / 10
		result.push(des)
	}
	if (ost) result.push(ost)
	return result.reverse().join('')
}
function factorial(n) {
	if (n < 2) return '1'
	if (!(n in cashFactorial)) {
		let stroka = mulStr(factorial(n - 1), n)
		cashFactorial[n] = stroka
	}
	return cashFactorial[n]
}

import CardChameleonOutput from "./preloaded";

const alb = ['A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K']
const BlackRow = alb.map(el => el + 'C').concat(alb.map(el => el + 'S'), 'XB')
const RedRow = alb.map(el => el + 'D').concat(alb.map(el => el + 'H'), 'XR')
const deckProcess = (arr: string[]) => {
	let bl: string[] = [], rd: string[] = [], ds: string[] = []
	for (let k of arr) {
		BlackRow.includes(k)
		  ? bl.push(k)
		  : rd.push(k)
	}
	while (bl.length)
		ds.unshift(...[rd.pop()!, bl.pop()!]) // to begin once red, once black
	return ds
}
export default class CardChameleon {

	public encrypt(mes: string, secretKey: string[]): string | null {
	if (!mes) return ''
  if(new Set(secretKey).size !== 54) return null
 	if (!/^[A-Z ]+$/.test(mes) ||	!secretKey.every(e => [...BlackRow, ...RedRow].includes(e))) return null
  let tr = ''
	let deck = deckProcess(secretKey)
	for (let sym of mes) {
    let shift = BlackRow[sym === ' ' ? 26 : sym.charCodeAt(0) - 65]
		let rev = deck[deck.indexOf(shift) - 1]
		let x = deck.indexOf(BlackRow[RedRow.indexOf(rev)]) - 1
		let i = RedRow.indexOf(deck[x])
		tr += i === 26 ? ' ' : String.fromCharCode(i + 65);
		[deck[0], deck[x]] = [deck[x], deck[0]];  // swap
		deck = deck.slice(2).concat(deck.slice(0, 2))
	}
	return tr
	}

	public decrypt(mes: string, secretKey: string[]): string | null {
	if (!mes) return ''
	if (new Set(secretKey).size !== 54) return null
	if (!/^[A-Z ]+$/.test(mes) || !secretKey.every(e => [...BlackRow, ...RedRow].includes(e))) return null
	let dck = deckProcess(secretKey), tr = ''
	for (let sym of mes) {
		let shift = dck.indexOf(RedRow[sym === ' ' ? 26 : sym.charCodeAt(0) - 65])
		let c = dck[shift + 1]
		let par = dck.indexOf(RedRow[BlackRow.indexOf(c)]) + 1
		let i = BlackRow.indexOf(dck[par]);
		tr += i === 26 ? ' ' : String.fromCharCode(i + 65);
		[dck[0], dck[shift]] = [dck[shift], dck[0]];
		dck = dck.slice(2).concat(dck.slice(0, 2))
	}
	return tr
	}
}

const razd = (t:number) => {
	let otv = 0
	for (let i = 2; i <= Math.sqrt(t); i++) {
		if (t % i === 0) i === t / i
      ? otv += i
      : otv += i + t / i
	}
	return otv
}

export function buddy(beg: number, lim: number): number[] {
	for (let i = beg; i <= lim; i++) {
		let si = razd(i)
		if (i < si && i === razd(si)) return [i, si]
	}
	return []
}

import re

def increment_string(ss):
    num = re.findall(r'\d+', ss)
    if num:
        s_n = num[-1]
        ss = ss.rsplit(s_n, 1)[0]
        num = str(int(s_n) + 1)
        return ss + '0' * (len(s_n) - len(num)) + num
    return ss + '1'

# fixme
function zeroes($bs, $nm){
  if($bs+$nm === 40) return $bs;
    for($i=2; $i<=$bs; $i++){
      if($bs%$i===0){
        $mI=0;
		    $c=0;
        while($bs%$i === 0){
           $bs=$bs/$i;
           $mI++;
        }
        $ks = floor($nm/$i);
        while($ks>0) {
          $c += $ks;
          $ks = floor($ks/$i);
        }
        $res = floor($c/$mI);
      }
    }
    $rc = $nm + $bs === $nm++ ? 11 : $res;
    return $nm+$bs === $nm++ or $rc;
  }

function land_perimeter($mass) {
        for ($k=0; $k < count($mass); $k++) {
            for ($r=0; $r < strlen($mass[$k]); $r++) {
                if ($mass[$k][$r] === 'X') {
                    $res += 4;
                    $mass[$k][$r+1] !== 'X' ?: $res--;
                    $mass[$k][$r-1] !== 'X' ?: $res--;
                    $mass[$k+1][$r] !== 'X' ?: $res--;
                    $mass[$k-1][$r] !== 'X' ?: $res--;
                }
            }
        }
        return 'Total land perimeter: '.$res;
    }

function loop_size(Node $nd): int
{
    $s = 0;
    while (!isset($nd->loop)) {
        $nd->loop = $s;
        $nd = $nd->getNext();
        $s++;
    }
    return $s - $nd->loop;
}

const loop_size = (nd) => {
	let mass = []
	while (!~mass.indexOf(nd)) {
		mass.push(nd)
		nd = nd.next
	}
	return mass.length - mass.indexOf(nd)
}

function listSquared($m, $n)
{
    $finish = array();
    foreach (range($m, $n) as $val) {
        $totl = 0;
        for ($i = 1; $i < sqrt($val); $i++)
            if ($val % $i === 0)
                $totl += $i * $i + intdiv($val, $i) * intdiv($val, $i);

        if ((int) sqrt($val) * (int) sqrt($val) === $val) $totl += $val;
        if ((int) sqrt($totl) * (int) sqrt($totl) === $totl) $finish[] = [$val, $totl];
    }
    return $finish;
}

function find_uniq($str): string
{
    $res = [];
    foreach ($str as $val) {
        $dubl = array_unique(str_split(strtolower($val)));
        sort($dubl);
        $key = implode('', $dubl);
        $res[$key][] = $val;
    }
    foreach ($res as $vl)
        if (count($vl) == 1) return $vl[0];
}

function compress(mus) {
	let len = mus.length
	let ind = 0
	let compress = []
	let mem, cs, val
	while(ind<len){
		if (ind + 1 < len && mus[ind + 1] === mus[ind]){
			mem = mus[ind]
			cs = 2
			ind += 1
			while (ind < len && mus[ind] == mem){
				ind += 1
				cs += 1
			}
			cs -= 1
			ind -= 1
			compress.push(`${mem}*${cs}`)
		}
		else if (ind + 2 < len && mus[ind + 2] - mus[ind + 1] === mus[ind + 1] - mus[ind]){
			mem = mus[ind]
			val = mus[ind + 1] - mus[ind]
			ind += 2
			while (ind < len && mus[ind] - mus[ind - 1] === val) ind += 1
			ind -= 1
			let v = Math.abs(val)
			if(v===1) compress.push(`${mem}-${mus[ind]}`)
			     else compress.push(`${mem}-${mus[ind]}/${v}`)

		} else {
			compress.push(String(mus[ind]))
		}
		ind += 1
	}

	return compress.join(',')
}

// cycle rotation
//0- [0,0,0,0]  all
//1- [1,1,1,1]  all
//2- [2,4,8,6]  4
//3- [3,9,7,1]  4
//4- [4,6,4,6]  2
//5- [5,5,5,5]  all
//6- [6,6,6,6]  all
//7- [7,9,3,1]  4
//8- [8,4,2,6]  4
//9- [9,1,9,1]  2
function lastDigit(as){
  if(!as.length) return 1

  let x = as.reduceRight((ac,n,ind)=>{
    let one = ac < 4 ? ac : ac % 4 + 4
    let zero = ind === 0 ? n%10 : n<4 ? n : n%4 + 4
    return Math.pow(zero,one)
  }, 1)
  return x % 10
}

squirrel=(x,H,$)=>+(a=(x*x+$*$)**.5*H/x).toFixed(4)

removeZeros=$=>eval('['+/[^0,].*[^0,]/.exec($)+']')

sd=U=>+(""+U).replace(/\d/g,$=>$*$)

// cash
let primeCashe = []

// the sieve of Eratosthenes
let countPrimes2 = function (n) {
	let s = new Uint8Array(n), res = 0
	for (let y=2; y<n; y++) {
		if (s[y]) continue
		res++
		primeCashe[y] = res
    let qr = y*y
		for (let l=qr; l<n; l+=y) s[l]=1
	}
};
//for small number
const isPrime = (n) => {
	if (n < 2) return 0
	if (n === 2 || n === 3) return 1
	if (n % 6 !== 1 && n % 6 !== 5) return 0
	let sqr = Math.floor(Math.sqrt(n))
	for (let i = 5; i <= sqr; i += 6)
		if (n % i === 0 || n % (i + 2) === 0) return 0
	return 1
}
function countPrimes(min, max) {
	if (primeCashe.length === 0) countPrimes2(20000010) //one time -> cash
	let c = 0
	if (max < 1000) {
		for (let i = min; i <= max; i++) {
			if (isPrime(i)) c++
		}
		return c
	}
let shift = 1 // for correction
	let maxAr = max
	while (!primeCashe[maxAr]) {maxAr++; shift =0}
	let minAr = min
	while (!primeCashe[minAr]) minAr++;
	c = shift + primeCashe[maxAr] - primeCashe[minAr]
	return c
}

function genfib(){
  let gen = fibs()
  return function(){
    return gen.next().value
  }
}
function* fibs(){
  let mfn1 = 1
  let mfn2 = 0
  while (true){
    let current = mfn2
    mfn2 = mfn1
    mfn1 = mfn1 + current
    yield current
  }
}

const isPrime = (n: number) => {
  if(n === 2 || n === 3) return 1
  if(n % 6 !== 1 && n % 6 !== 5) return 0
  let sqr = Math.floor(Math.sqrt(n))
  for(let i = 5; i <= sqr; i += 6)
    if(n % i === 0 || n % (i + 2) === 0) return 0
  return 1
}
export function sumOfDivided(lst: number[]): number[][] {
    let cBig: number = Math.max.apply(null, lst.map(Math.abs))
    let isP: number[][] = []
    for (let i = 2; i <= cBig; i++)
      if (isPrime(i)) {
        let filt = lst.filter(n => !(n % i))
        let total = filt.reduce((tot, t) => tot + t, 0)
        if (filt.length) isP.push([i, total])
      }
    return isP
}

function smallest(fc) {
	let resObj = [fc, 0, 0]
	let liter = fc.toString()
	for (let i = 0; i < liter.length; i++) {
		let cuted = liter.slice(0, i) + liter.slice(i + 1)// cut one sym
		for (let s = 0; s <= cuted.length; s++) {
			let fndNum = +(cuted.slice(0, s) + liter[i] + cuted.slice(s))
			if (resObj[0] > fndNum) resObj = [fndNum, i, s]
		}
	}
	return resObj
}

function validParentheses(ns) {
	let s = ns
	while (/\(\)/.test(s)){
		s = s.replace(/\(\)/, '')
}
	return s.length === 0
}

const maxSequence = function(array){
  let min = res = total = 0, i;
  for (let j = 0; j < array.length; ++j) {
    total += array[j]
    min = Math.min(total, min)
    res = Math.max(res, total - min)
  }
  return res
}

function pickPeaks($arr) {
    $res = array("pos" => array(), "peaks" => array());
    $s = -1;
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] > $arr[$i - 1]) {
            $s = $i;
        } else if ($arr[$i] < $arr[$i-1] && $s !== -1) {
            array_push($res["pos"], $s);
            array_push($res["peaks"], $arr[$s]);
            $s = -1;
        }
    }
    return $res;
}

function generateHashtag($str) {
    $b=trim($str);
    if(strlen($b) == 0)return false;
    $b = "#" . preg_replace_callback('|\w\S*|', function($m){
    	return ucfirst(strtolower($m[0]));
    }, $b);
    $b = str_replace(" ", "",$b);
    if($str && strlen($b) <= 140){
      return $b;
    }
    return false;
}

let q = '(?:0|11)'
let q2 = '(?:1|00)'
let n = q + q2
let m = q2 + q
let reg = '^(?:0|1(1|0('+n+')*(10|'+q+'01))(01*0(0|1('+m+')*(01|'+q2+'10)))*1)+$'
// Write a regular expression to detect whether a binary number is divisible by 7
// It won't be accepted if you code something else like Function
let solution = new RegExp(reg)

function human_readable($seconds) {
  if ( $seconds < 0 || $seconds > 360000 ) {
    return null;
  }

  $hours = floor( $seconds / 3600 );
  $seconds -= $hours * 3600;
  if ( $hours < 10 ) {
    $hours = '0' . $hours;
  }

  $minutes = floor( $seconds / 60 );
  $seconds -= $minutes * 60;
  if ( $minutes < 10 ) {
    $minutes = '0' . $minutes;
  }

  if ( $seconds < 10 ) {
    $seconds = '0' . $seconds;
  }

  return $hours . ':' . $minutes . ':' . $seconds;
}

const balance = (sm,_,a) => a.indexOf(sm) === a.lastIndexOf(sm) ? "(" : ")"
function duplicateEncode(word) {
  let arr = word.toLowerCase().split`` // to lower and split to array
  let r = arr.map(balance)
  return r.join``
}

const balance = (sm:string,_:number,array:string[]) => array.indexOf(sm) === array.lastIndexOf(sm) ? "(" : ")"
export function duplicateEncode(word: string) {
  let array:string[] = word.toLowerCase().split('') // to lower and split to array
  let res:string[] = array.map(balance)
  return res.join('')
}

function closest(numStr) {
  if(numStr === '') return []
  let whDif = []
  let arrNum = numStr.split(' ') // to array
  let arrPair = arrNum.map(n => n.split('').map(d => parseInt(d)))// to arr[arr]
  let nb = arrNum.map(s => parseInt(s)) // to num
  let wh = arrPair.map(n => n.reduce((acc, el) => acc += el, 0)) // reduce to weigths
  let sortWh = wh.slice().sort((a, b) => a - b) // sort
  for(let i = 0; i < sortWh.length - 1; i++) {
    let dif = sortWh[i + 1] - sortWh[i]
    whDif.push(dif)
  }
  let ind = whDif.indexOf(Math.min(...whDif))
  let arrWh = [sortWh[ind], sortWh[ind + 1]]
  let whInd = arrWh[0] === arrWh[1]
    ? [wh.indexOf(arrWh[0]), wh.indexOf(arrWh[1], wh.indexOf(arrWh[0]) + 1)]
    : [wh.indexOf(arrWh[0]), wh.indexOf(arrWh[1])]

  return [
    [
      arrWh[0],
      whInd[0],
      nb[whInd[0]]
    ],
    [
      arrWh[1],
      whInd[1],
      nb[whInd[1]]
    ]
  ]
}

def likes(srcStr):
    res = ""
    if (len(srcStr) == 0):
        res = "no one likes this"
    elif (len(srcStr) == 1):
        res = str(srcStr[0]) + " likes this"
    elif (len(srcStr) > 1 and len(srcStr) < 4):
        for name in range(0, len(srcStr) - 1):
            res = res + srcStr[name] + ", "
        res = res[:-2]
        res = res + " and " + str(srcStr[len(srcStr) - 1]) + " like this"
    else:
        for name in range(0, 2):
            res = res + srcStr[name] + ", "
        res = res[:-2]
        res = res + " and " + str(len(srcStr)-2) + " others like this"
    return res

function countKprimes($k, $beg, $fin) {
    $arr = array();
    for($i = $beg; $i <= $fin; $i++){
        if(FactorsK($i) == $k) $arr[] = $i;
    }
    return $arr;
}
function FactorsK($n){
    if ($n < 1) return 0;
    $sc = 0;
    while ($n%2 == 0){
        $n /= 2;
        $sc++;
    }
    for ($i = 3; $i <= sqrt($n); $i+=2) {
        while($n%$i == 0){
            $n /= $i;
            $sc++;
        }
    }
    return ($n > 2) ? $sc+1 : $sc;
}
function puzzle($s) {
    $prim1 = countKprimes(1, 1, $s);
    $prim3 = countKprimes(3, 1, $s);
    $prim7 = countKprimes(7, 1, $s);
    $sc = 0;
    for($a = 0; $a < count($prim1); $a++){
        for($b = 0; $b < count($prim3); $b++){
            for($c = 0; $c < count($prim7); $c++){
                if( $prim1[$a] + $prim3[$b] + $prim7[$c] == $s )
                    $sc += 1;
            }
        }
    }
    return $sc;
}

function is_prime(int $num): bool {
  if ($num < 2) {
     return false;
  }
  if ($num === 2 || $num === 3) {
     return true;
  }
  if($num % 6 !== 1 && $num % 6 !== 5) return false;
  $sqr = floor(sqrt($num));
  for($i = 5; $i <= $sqr; $i += 6){
    if($num % $i === 0 || $num % ($i + 2) === 0) return false;
  };
  return true;
}

function sumIntervals(dp) {
	let dpz = dp.sort((a, b) => a[0] - b[0])
	let lenc = 0
	let lc = Number.NEGATIVE_INFINITY
	for (let[one, two] of dpz) {
		let per = one < lc ? Math.min(two, lc) - one : 0
		lc = Math.max(two, lc)
		lenc += two - one - per
	}
	return lenc
}

isCheck=j=>(p='        ',t=j.map(b=>b.join``).join(p),f=(g,...a)=>a.map(n=>[g,[...p].map((y,i)=>n*i+n)]),[[/♟/,[-15,-17]],[/♞/,[-33,-31,-18,-14,14,18,31,33]],...f(/^ *[♝♛]/,17,15,-17,-15),...f(/^ *[♜♛]/,1,-1,-16,16)].some(([o,u])=>o.test(u.map(v=>t[t.indexOf('♔')+v]).join``)))

const KING = '♔'
const QUEEN = '♛'
const BISHOP = '♝'
const KNIGHT = '♞'
const ROOK = '♜'
const PAWN = '♟'
const EMPTY = ' '

function kingIsInCheck(chessBoard) {
	for (let i = 0; i < 8; i++) {
		for (let j = 0; j < 8; j++) {
			if (chessBoard[i][j] == KING) {

				if (checkKnight(chessBoard, KNIGHT, i, j))
					return true;

				if (checkPawn(chessBoard, PAWN, i, j))
					return true;

				if (checkRock(chessBoard, ROOK, i, j))
					return true;

				if (checkBishop(chessBoard, BISHOP, i, j))
					return true;

				if (checkQueen(chessBoard, QUEEN, i, j))
					return true;
			}
		}
	}
	return false;
}
function checkCondition(i, j) {
	return i >= 0 && i < 8 && j >= 0 && j < 8;
}
function checkKnight(board, c, i, j) {
	// All possible moves of the knight
	let x = [2, 2, -2, -2, 1, 1, -1, -1];
	let y = [1, -1, 1, -1, 2, -2, 2, -2];

	for (let k = 0; k < 8; k++) {
		let m = i + x[k];
		let n = j + y[k];
		if (checkCondition(m, n) && board[m][n] == c)
			return true;
	}
	return false;
}
function checkPawn(board, c, i, j) {
	let lookFor;
	lookFor = c;
	if (checkCondition(i - 1, j - 1)
		&& board[i - 1][j - 1] == lookFor)
		return true;
	if (checkCondition(i - 1, j + 1)
		&& board[i - 1][j + 1] == lookFor)
		return true;
	return false;
}
function checkRock(board, c, i, j) {

	// Check downwards
	let k = 0;
	while (checkCondition(i + ++k, j)) {
		if (board[i + k][j] == c)
			return true;
		if (board[i + k][j] != EMPTY)
			break;
	}

	// Check upwards
	k = 0;
	while (checkCondition(i + --k, j)) {
		if (board[i + k][j] == c)
			return true;
		if (board[i + k][j] != EMPTY)
			break;
	}

	// Check right
	k = 0;
	while (checkCondition(i, j + ++k)) {
		if (board[i][j + k] == c)
			return true;
		if (board[i][j + k] != EMPTY)
			break;
	}

	// Check left
	k = 0;
	while (checkCondition(i, j + --k)) {
		if (board[i][j + k] == c)
			return true;
		if (board[i][j + k] != EMPTY)
			break;
	}
	return false;
}
function checkBishop(board, c, i, j) {
	// Check the lower right diagonal
	let k = 0;
	while (checkCondition(i + ++k, j + k)) {
		if (board[i + k][j + k] == c)
			return true;
		if (board[i + k][j + k] != EMPTY)
			break;
	}

	// Check the lower left diagonal
	k = 0;
	while (checkCondition(i + ++k, j - k)) {
		if (board[i + k][j - k] == c)
			return true;
		if (board[i + k][j - k] != EMPTY)
			break;
	}

	// Check the upper right diagonal
	k = 0;
	while (checkCondition(i - ++k, j + k)) {
		if (board[i - k][j + k] == c)
			return true;
		if (board[i - k][j + k] != EMPTY)
			break;
	}

	// Check the upper left diagonal
	k = 0;
	while (checkCondition(i - ++k, j - k)) {
		if (board[i - k][j - k] == c)
			return true;
		if (board[i - k][j - k] != EMPTY)
			break;
	}

	return false;
}
function checkQueen(board, c, i, j) {
	if (checkBishop(board, c, i, j) || checkRock(board, c, i, j))
		return true;
	return false;
}

function balancedParens(n, ks) {
  if(n === 0) return ''
  if(ks < 0) return null
  let ind = ks + 1n
  let ln = new Array(n + 1).fill(0n)
  let matrix = new Array(2 * n + 1).fill(0)
  for(let i = 0; i <= matrix.length - 1; i++) matrix[i] = [...ln]
  matrix[0][0] = 1n
  for(let i = 0; i < n * 2; ++i) {
    for(let j = 0; j <= n; ++j) {
      if(j + 1 <= n) matrix[i + 1][j + 1] += matrix[i][j]
      if(j > 0) matrix[i + 1][j - 1] += matrix[i][j]
    }
  }
  if(ind > matrix[2 * n][0]) return null

  let res = ''
  let shift = 0

  for(let i = n * 2 - 1; i >= 0; --i) {
    if(shift + 1 <= n && matrix[i][shift + 1] >= ind) {
      res += '('
      ++shift
    } else {
      res += ')'
      if(shift + 1 <= n)
        ind = ind - BigInt(matrix[i][shift + 1])
      --shift
    }
  }
  return res
}

function ipsBetween(fs, sc) {
	const red = (acc, s) => acc*256+s
	const convert = (IP) => IP.split('.')
		.map(nl => parseInt(nl))
		.reduce(red)
	return convert(sc) - convert(fs);
}

function squareDigitsSequence(ch, ar = []) {
	const sqr = (x, q) => x + q * q
  ar.push(ch)
  ch = String(ch)
    .split``
    .reduce(sqr, 0)
  if (ar.includes(ch)) {
    return ++ar.length;
  }
  return squareDigitsSequence(ch, ar);
}

palindrome=p=(n,[v,...g])=>g!=![]?v+p(n-2,g)+v:v.repeat(n)

export function* fibonacciSequence(): Iterator<number>{
  let mfn1 = 1
  let mfn2 = 1
  while (true){
    let current = mfn2
    mfn2 = mfn1
    mfn1 = mfn1 + current
    yield current
  }
}

const arrCreate = (a: number, b: number): number[] => {
  const n = b - a + 1
  return Array.from(Array(n).keys()).map(x => x + a)
}
export function josephusSurvivor(num: number, kl: number): number {
  return arrCreate(1, num).reduce((elem, dl) => (elem + kl - 1) % dl + 1)
}

checkRange=(m,x,y)=>m.map(h=>e+=x>h==h>y,e=0)|e

function nextBigger(noBig) {
	let splited = noBig.toString().split``.map(el => +el)
	let leng = splited.length - 1
	for (let i = leng; i > 0; i--) {
		if (splited[i] > splited[i - 1]) {
			let b = splited.slice(i)
			let a = splited.slice(0, i - 1)
			let D = splited[i - 1]
			let max = b.filter(el => el > D).sort()[0]
			b[b.indexOf(max)] = D
			D = [...a, max, ...b.sort()].join``
			return Number(D)
		}
	}
	return -1;
}

const beth = (el, ind, par) => {
	if ((el === par[ind + 1] - 1) && (el === par[ind - 1] + 1)) return true
	return false
}
const solution = spisok =>{
	const SP = '@'
  const reg = new RegExp(`(,${SP})+,`, 'g')
return spisok.map((num, i, arr) => beth(num, i, arr) ? SP : num)
			.toString()
			.replace(reg, '-');
}

function balancedParens(n) {
	const combination = []
	const recFn = (str, strt, end) => {
		if (n === end) return combination.push(str)
		const flagStart =  n > strt, flagEnd = strt > end
		flagStart && recFn(str + '(', strt + 1, end)
		flagEnd   && recFn(str + ')', strt, end + 1)
	}
	recFn('', 0, 0)
	return combination
}

class Thing {
	constructor(name) {
		this.name = name;
    this.is_not_a = new Proxy(this, {
			get: (target, name) => {
				const propName = `is_a_${name}`;
				Reflect.defineProperty(target, propName, { value: false });
				return target[propName];
			}
		});
		this.is_a = new Proxy(this, {
			get: (target, name) => {
				if (typeof n === 'symbol') {
					return target[n];
				}
				const propName = `is_a_${name}`;
				Reflect.defineProperty(target, propName, { value: true });
				return target[propName];
			}
		});
    this.has = (nm) => new Proxy(this, {
			get: (target, name) => {
				let znachenie;
				if (nm > 1) {
					const part = name.substring(0, name.length - 1);
					znachenie = new Array(nm).fill(part).map(n => new Thing(n));
					znachenie.each = (fn) => {
						let native = fn.toString();
						const arrowIndex = native.indexOf('=>');
						const allArg = native.substring(0, arrowIndex - 1);
						native = `${allArg} => ${allArg}.${native.substring(arrowIndex + 3)}`;
						const compiled = eval(native);
						znachenie.forEach(compiled);
					}
				} else {
					znachenie = new Thing(name);
				}
				Reflect.defineProperty(target, name, { value: znachenie });
				return target[name];
			}
		});
    this.having = this.has
    this.is_the = new Proxy(this, {
			get: (target, name) => {
				return new Proxy(target, {
					get: (obj, proxValue) => {
						Reflect.defineProperty(obj, name, { value: proxValue });
						return target;
					}
				});;
			}
		});
    this.and_the = this.is_the
    this.being_the = this.is_the

		this.can = new Proxy(this, {
			get: (target, name) => {
				const proxyFunc = (solo, twice) => {
					let arrMatch;
					let reg = /\${(\w+)}/g;
					let userFn = twice ? twice : solo;
					let isProp = twice ? solo : null;
					let native = userFn.toString();
					let endFn = native;
					while (arrMatch = reg.exec(native)) {
						const match = target[arrMatch[1]];
						if (match) endFn = endFn.replace(arrMatch[0], match);
					}
					endFn = eval(endFn);
					if (isProp) {
						endFn = new Proxy(endFn, {
							apply: (evalFunction, thisArg, argsF) => {
								const reflValue = target[isProp] ? target[isProp] : new Array();
								reflValue.push(evalFunction.apply(thisArg, argsF))
								Reflect.defineProperty(target, isProp, { value: reflValue });
								return target;
							}
						});
					}
					Reflect.defineProperty(target, name, { value: endFn });
				};
				return proxyFunc;
			}
		});

    }
}

f=
''
[
`\
c\
o\
n\
c\
a\
t`
][
'\
b\
i\
n\
d'
]
`\
H\
e\
l\
l\
o\
,\
 \
w\
o\
r\
l\
d\
!`

// The answer to everything, huh?
guess=42

function* alpha(individ) {
  let base = individ/100000
  let mini = 1.0000000000000001e-7
  while(1){
    base = base - mini
    yield base
  }
}
let gen = alpha(guess)
Math = Object.create(Math, {
	random: {
		value: ()=>gen.next().value
	}
})

Math.random.toString = function () {
	return `function random() { [native code] }`;
};

Object.freeze(Math);
//(function(){

var guess = 10
Math.floor = () => { return 2**2+2*3 }

function GrεεκL33t(stroka) {
	let toSymb = {
		a: "α",	b: "β",	d: "δ",	e: "ε",	i: "ι",
		k: "κ",	n: "η",	o: "θ",	p: "ρ",	r: "π",
		t: "τ",	u: "μ",	v: "υ",	w: "ω",	x: "χ",
		y: "γ"
	}
	return stroka.toLowerCase()
		.split('')
		.map(el => toSymb[el] || el)
    .join('')
}

function removeZeros(array) {
  let len = array.length
  let res = [];
  let zer = [];
  let zcount = 0;
  let rcount = 0;
  for(let i=0; i<len; i++){
    let m1 = array[i]
    if(m1===0 || m1==='0') {zer[zcount] = m1; zcount++ }
    else {res[rcount] = m1; rcount++ }
  }

  for(let i=0; i<zer.length; i++){
    res[rcount] = zer[i]
    rcount++
  }
return res
}

export const sumPairs = (ints: number[], s: number): [number, number] | void => {
  if(ints.length < 2) return undefined
  let objSet = new Set()
  objSet.add(ints[0])
  let len = ints.length
  for(let i = 1; i < len; ++i) {
    let needed = s - ints[i]
    if(objSet.has(needed)) {
      return [needed, ints[i]]
    }
    objSet.add(ints[i])
  }
  return undefined
}

export const divisibleByFive = /^(0+|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)+$/
//

type items = number | string
export const josephus = (items: items[], k: number): items[] => {
 let oldArr: items[] =[...items]
 let midArr: items[] = []
 let cnt = items.length
 let i = 0
 let arr: items[] = []
 while(cnt>0){
   arr = arr.concat(oldArr.filter((el,ind)=>{
      i++
     if(i % k === 0) return true
      else{
          midArr.push(el)
          return false
         }
   }))
 oldArr =  [...midArr]
 midArr = []
 cnt=oldArr.length
 }
  return arr
}

interface INum {
    [key: number]: number
}
export const primeFactors = (n:number): string => {
  let numDiv: number[] = [], obj: INum = {}, res = ''

  function recursiv(n: number): void {
    if(n > 1) {
      for(let i = 2; i <= n; i++) {
        if(n % i === 0) {
          numDiv.push(i)
          recursiv(n / i)
          break
        }
      }
    }
  }

  recursiv(n)
  numDiv.map(x => {
    obj[x] ? obj[x]++ : obj[x] = 1
  })
  for(let num in obj) {
    obj[num] === 1 && (res += '(' + num + ')')
    obj[num] > 1 && (res += '(' + num + '**' + obj[num] + ')')
  }
  return res
}

export function revRot (s: string, sz: number): string {
  if(sz <= 0 || s == '' || sz > s.length) return ''
  const fPow = (a: number, c: string) => a + Math.pow(+c, 3)
  const arr = []
  const sim = s.split('')
  while(sim.length >= sz) arr.push(sim.splice(0, sz))

  const final = arr.map(el => {
    const powSum = el.reduce(fPow, 0)
    if(+powSum % 2) {
      el.push(el[0])
      el.shift()
      return el.join('')
    } else {
      return el.reverse().join('')
    }
  })
  return final.join('')
}

const isprime = (n: number) => {
  if(n === 2 || n === 3) return 1
  if(n % 6 !== 1 && n % 6 !== 5) return 0
  let sqr = Math.floor(Math.sqrt(n))
  for(let i = 5; i <= sqr; i += 6)
    if(n % i === 0 || n % (i + 2) === 0) return 0
  return 1
}

export const gap = (g: number, m: number, n: number): number[]|null => {
  let para = []
  para[0] = 0, para[1] = 0
  let first = 0
  if(m >= n) return para
  for(let i = m; i <= n; i++) {
    if(isprime(i)) {
      if(first === 0) first = i
      else if(i - first === g) {
        para[0] = first
        para[1] = i
        return para
      } else first = i
    }
  }
  if(para[0] === para[1]) return null
  return para
}

export function narcissistic(val: number): boolean {
  let arr = String(val).split('')
  let arrExp = arr.map(el => Math.pow(+el, arr.length))
  let sum = arrExp.reduce((ac,v)=> ac + v, 0)
  return val === sum
}

type br = '(' | '{' | '['
export function validBraces(braces: string): boolean{
  let matches = { '(':')', '{':'}', '[':']' }
  let stack:br[] = []
  let curChar:br

  for (let i=0; i<braces.length; i++) {
    curChar = braces[i] as br
    if (matches[curChar]) stack.push(curChar)
    else if (curChar !== matches[stack.pop()!]) return false
  }
  return stack.length === 0
}

const recoverSecret = (triArr) => {
  const check = (bool, trip) => trip.indexOf(candidat) > 0 ? false : bool
  let totalSymbols = 3 * triArr.length
  let res = '', candidat
  while (totalSymbols > 0) {
    for (let tri of triArr) {
      if (tri.length === 0) continue
      candidat = tri[0]
      if (!triArr.reduce(check, true)) continue
      res += candidat
      triArr.map( el => {
        if (el.indexOf(candidat) === 0) {
          totalSymbols--
          el.shift()
        }
      })
      break
    }
  }
  return res
}

export function beeramid(bonus: number, price: number): number {
  let result: number = 0
  let moneyBon = bonus
  for(let i = 1; i <= bonus; i++) {
    moneyBon = moneyBon - ((i ** 2) * price)
    if(moneyBon >= 0) {
      result += 1
    }
  }
  return result
}

var beeramid = function(bonus, price) {
  if (bonus < price) return 0
  let total = Math.floor(bonus / price)
  if(total < 5 ) return 1
  let level = 1
  let used = 1
  while((total-used) > 0){
    total = total-used
    used = (level + 1)**2
    if(total-used >= 0) level++
  }
  return level
}

device.decode = function (st) {
  let innerKey = device.encode ('a'.repeat(66))
  let period = innerKey.length
  let arr = st.split('')
  let par = arr.map( (symb,i) =>
    ~innerKey.indexOf(symb)
      ? innerKey[(innerKey.indexOf(symb) - i + period - 1) % period ]
      : symb
  )
  return par.join('')
}

let code = {}

function frequencies(str) {
  let chastota = {}
  for(let i in str) chastota[str[i]] === undefined ? chastota[str[i]] = 1 : chastota[str[i]]++
  return Object.entries(chastota)
}

function sorting(freqs) {
  let newfreqs = freqs.map(el=>[...el])
  let tuples = newfreqs.map(el=>el.reverse())
  return tuples.sort()
}

function makeNode(arr) {
  while(arr.length > 1) {
    let tw = [arr[0][1], arr[1][1]]
    let rst = arr.slice(2, arr.length)
    let fr = arr[0][0] + arr[1][0]
    arr = rst
    end = [fr, tw]
    arr.push(end)
    arr.sort()
  }
  return arr[0][1]
}

function recursNode(node, pat) {
  if(typeof (node) == typeof (''))
    code[node] = pat
  else {
    recursNode(node[0], pat + '0')
    recursNode(node[1], pat + '1')
  }

}

function encode(freqs, s) {
  if(freqs.length <= 1) return null
  if(s==='') return ''
  let pat = ''
  let sort = sorting(freqs)
  let tree = makeNode(sort)
  let res = recursNode(tree, pat)
  let output = ''
  for(el in s) output += code[s[el]]
  return output
}

function decode(freqs, bits) {
  if(freqs.length <= 1) return null
  if(bits==='') return ''
  let sort = sorting(freqs)
  let tree = makeNode(sort)
  let output = ''
  let p = tree
  for(let bit in bits) {
    if(bits[bit] == '0') p = p[0]
    else{
      p = p[1]
    }
    if(typeof (p) == typeof ('')) {
      output += p
      p = tree
    }
  }
  return output
}

const getReg = n => {
  const line = `${n}`.repeat(3)
  const diagonal1 = `${n}..`.repeat(2)+`${n}`
  const  vertikal = `${n}...`.repeat(2)+`${n}`
  const diagonal2 = `${n}....`.repeat(2)+`${n}`
  return new RegExp(`${line}|${diagonal1}|${vertikal}|${diagonal2}`)
}
function isSolved(board) {
  let line = board.join('#').replace(/,/g,'');
  const reg1 = getReg(1)
  const reg2 = getReg(2)
  if(reg1.test(line)) return 1;
  if(reg2.test(line)) return 2;
  if(/0/.test(line)) return -1;
  return 0;
}

// assign your RegExp to REGEXP
const REGEXP = /^(?=.*[A-Z])(?=.*[a-z])(?=.*[0-9])[a-zA-Z0-9]{6,}$/;

const all = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".split('')
const SHIFT = 13
const DIV = all[SHIFT-1]
const repl = sym => String.fromCharCode(sym.charCodeAt(0) + (sym.toLowerCase() <= DIV ? SHIFT : -SHIFT))
function rot13(message) {
    return message.replace(/[a-z]/gi, repl);
}

const spiralize = n => {
  return Array(n)
    .fill(Array(n).fill(0))
    .map((row, rowIndex) =>
      row.map((_, colIndex) => logic(colIndex, rowIndex, n))
    )
}

const logic = (colIndex, rowIndex, n) => {
  const top = (rowIndex < n / 2 && rowIndex % 2 === 0 && colIndex >= rowIndex - 2 && colIndex <= n - rowIndex - 1)
  const bottom = ((n - rowIndex) % 2 === 1 && colIndex > n - rowIndex - 1 && colIndex < rowIndex)
  const left = (colIndex % 2 === 0 && rowIndex > colIndex + 1 && rowIndex < n - colIndex)
  const right = ((n - colIndex) % 2 === 1 && rowIndex > n - colIndex - 1 && rowIndex <= colIndex)
  if(top || bottom || left || right) return 1
  return 0
}

reverse=a=>a.map(a.pop,[...a])

const symbols = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/='
String.prototype.toBase64 = function() {
  let code = ''
  const len = this.length
  for(let i = 0; i < len; i++) {
    const bin = '00000000' + this.charCodeAt(i).toString(2)
    code += bin.substring(bin.length - 8) // с конца 8символов
  }
  if(len % 3 === 1) {
    code += '0000000000000000'
  } else if(len % 3 === 2) {
    code += '00000000'
  }
  let result = ''
  for(let i = 0; i < code.length; i += 6) {
    const n = parseInt(code.substring(i, i+6), 2)
    result += symbols[n]
  }
  return result
}

String.prototype.fromBase64 = function() {
  let code = ''
  for(let i = 0; i < this.length; i++) {
    const str = '000000' + symbols.indexOf(this[i]).toString(2)
    code += str.substring(str.length - 6)
  }
  let result = ''
  for(let i = 0; i < code.length; i += 8) {
    const str = parseInt(code.substring(i, i + 8), 2)
    result += String.fromCharCode(str)
  }
  return result
}

const countOnes = (left, right) => {
  const ds = n => {
    let bt = 0
    for(let i = 0; i < 30; ++i){
      const left1 = 1 << i
      const left2 = 2 << i
      const delim = (n + 1) / left2
      const floor = Math.floor(delim)
      const param = Math.max(0, (delim - floor) * left2 - left1)
      bt += floor * left1 + param
    }
    return bt
  }
  return ds(right) - ds(left - 1)
}

function sumStrings (a, b) {
  let res = '', c = 0
  let aa = a.split('')
  let bb = b.split('')
  while (aa.length || bb.length || c) {
    c += (parseInt(aa.pop()) || 0) + (parseInt(bb.pop()) || 0)
    res = c % 10 + res
    c = c > 9
  }
  return res.replace(/^0+/, '')
}

function solution(input, markers) {
  let splited = input.split('\n')
  let size = splited.length
  for ( let i = 0; i < size; i++) {
    let ch = splited[i].split('');
    let cSize = ch.length
    for ( let j = 0; j < cSize; j++) {
      if ( ch[j] === markers[0] || ch[j] === markers[1]) {
        splited.splice(i, 1, splited[i].slice(0, j-1))
      }
    }
  }
  return splited.join('\n')
}

function solution(input, markers) {
  let splited = input.split('\n')
  let size = splited.length
  for ( let i = 0; i < size; i++) {
    let ch = splited[i].split('');
    let cSize = ch.length
    for ( let j = 0; j < cSize; j++) {
      if ( ch[j] === markers[0] || ch[j] === markers[1]) {
        splited.splice(i, 1, splited[i].slice(0, j-1))
      }
      else if ( !splited[i].includes(markers[0])) {
      }
    }
  }
  return splited.join('\n')
}

// Regular expression that matches binary inputs that are multiple of 3
const multipleOf3Regex = /^(0*(1(1|(01*0)+1))*)*$/;

export class Kata {
  static dnaStrand(dna: string) {
    const para = {
      A: 'T',
      T: 'A',
      G: 'C',
      C: 'G'
    }
    return dna.split("").reduce((p, c) => p + para[c as dna], "");
  }
}
type dna = 'A' | 'T' | 'G' | 'C'

function findOdd(A) {
  let res = {};
  A.forEach(k => {
    res[k] = res[k] ? res[k] + 1 : 1;
  });
  return +Object.keys(res)
    .find(key => res[key] % 2 === 1);
}

export const findOdd = (xs: number[]): number => {
  if(xs.length === 1) return xs[0]
  const cNum:number[] = []
  for(let mn=0; mn<xs.length; mn++){
    let el = xs[mn]
    if(!cNum.includes(el)){
      let c = 0
      for(let i = mn; i<xs.length; i++) if(xs[i] === el) c++
      if (c & 1) return el
        else cNum.push(el)
    }
  }
  return 0
}

export const isPangram = (phrase: string): boolean =>{
  let unic = phrase.toLowerCase().match(/[a-z]/g)
  return new Set(unic).size === 26
}

export class Kata {
  static validatePin(pin: string): boolean {
    if(!(pin.length===6 || pin.length===4)) return false
    return pin.match(/[^0-9]/gi) ? false : true
  }
}

export function reverseWords(str: string): string {
  return str
    .split(' ')
    .map(hlp)
    .join(' ');
}
const hlp = (s:string) => s.split('').reverse().join('')

export function isTriangle(a: number, b: number, c: number): boolean {
  return (a+b>c && b+c>a && c+a>b) ? true : false;
}

export function isValidWalk(walk: string[]) {
  if(walk.length !== 10) return false
  let x = 0;
  let y = 0;
  walk.map(str => ({x, y}=direct(str as s,x,y)) )
  return (x===0 && y===0)
}
function direct(s:s,x:number,y:number):xy{
  const ob:ob = {
    n:{x,y:y+1},
    s:{x,y:y-1},
    e:{x:x-1,y},
    w:{x:x+1,y}
  }
  return ob[s]
}
type s = 'n' | 's' | 'e' | 'w'
type xy = {
  x:number
  y:number
}
type ob = {
  n:xy
  s:xy
  e:xy
  w:xy
}

function topThreeWords(text) {
  const myArr = []
  let mdText = text.toLowerCase().split` `.map(l=>{
    if (l===`'`) return ''
    return l.replace(/[^'a-z]/gi,'')
  }).filter(e=>e)
  const par = mdText.reduce((a,x)=>(a[x]=a[x]?a[x]+1:1,a),{})
  for (let i in par) myArr.push([i,par[i]])

  return myArr.sort((a,b)=>b[1]-a[1]).slice(0,3).map(e=>e[0])
}

let exclude=["the","of","in","from","by","with","and", "or", "for", "to", "at", "a"];

function replExclude(e) {
  return e.length > 30
    ? e.split('-')
        .filter(a=>!~exclude.indexOf(a))
        .map(a=>a[0])
        .join('')
        .toUpperCase()
    : e.replace(/-/g,' ');
}

function tagA(e,pt) {
  pt = e=='home' ? '/' : '/' + pt.slice(1).join('/') + '/';
  return '<a href="' + pt + '">' + replExclude(e).toUpperCase() + '</a>';
}

function span(e) {
  return '<span class="active">' + /[^\.]+/.exec(replExclude(e))[0].toUpperCase() + '</span>';
}

function generateBC(url, separator) {

  url = url.replace(/(https?:\/\/)?.*?\/?/,'')
    .replace(/[#\?].*/,'')
    .split('/').filter(a=>a!='')
    .slice(1);

  if (url.length && url[url.length-1].match('^index\..*')) url.pop();

  url.unshift('home');

  url = url.map(function(e,i) {
    return i == url.length-1 ? span(e) : tagA(e,url.slice(0,i+1));
  });

  return url.join(separator);
}

function multiply(a,b) {
  let aa = Array.from(a.replace(/^0*/,'')).reverse();
  let bb = Array.from(b.replace(/^0*/,'')).reverse();
  let c = Array(aa.length + bb.length).fill(0);


  function more(i,vl) {
    for(vl += c[i]; vl > 0; vl = ~~(vl/10) + c[++i])
      c[i] = vl % 10;
  }

  aa.forEach((v1,i)=>bb.forEach((v2,j)=>more(i+j, v1*v2)));
  return c.reverse().join('').replace(/^0*(?=\d)/,'');
}

function hamming (n) {
  var seq = [1];
  var i2 = 0, i3 = 0, i5 = 0;
  for (let i = 1; i < n; i++) {
    let x = Math.min(2 * seq[i2], 3 * seq[i3], 5 * seq[i5]);
    seq.push(x);
    if (2 * seq[i2] <= x) i2++;
    if (3 * seq[i3] <= x) i3++;
    if (5 * seq[i5] <= x) i5++;
  }
  return seq[n-1];
}

const snail = array => {
  let rs;
  while (array.length) {
    rs = (rs ? rs.concat(array.shift()) : array.shift());
    for (var i = 0; i < array.length; i++)
      rs.push(array[i].pop());
    rs = rs.concat((array.pop() || []).reverse());
    for (var i = array.length - 1; i >= 0; i--)
      rs.push(array[i].shift());
  }
  return rs;
}

function sum(num){
  let ps = new Array(num+1).fill(0)
  ps[0] = 1
  let cnt = 0
  for (let i = 1; i < num+1; i++) {
    cnt = 0
    for (let j = i; j < num+1; j++) {
      ps[j] += ps[cnt]
      cnt++
    }
  }
  return ps[num]
}

function productFib(prod) {
  let pr = [0, 1];
  for (let i = 0; pr[i + 1] < prod; i++) pr.push(pr[i] + pr[i + 1]);
  for (let j = 0; j < pr.length; j++) {
    if (pr[j] * pr[j + 1] === prod) return [pr[j], pr[j + 1], true];
    if (pr[j] * pr[j + 1] !== prod && pr[j] * pr[j + 1] > prod)
      return [pr[j], pr[j + 1], false];
  }
}

function unStr (str, fc) {
  let pr = [];
  str.split('').reduce((prev, cur)=> {
    if (prev === 0) {
      pr.push(cur);
      return fc - 1;
    }
    return prev - 1;
  }, fc - 1)
  return pr.join('');
}

function shLength (str) {
  let par = str.split('').reduce((prev, cur) => {
    if (cur === prev.char) {
      prev.length = prev.length + 1;
    } else {
      if (prev.length < prev.shLen) {
        prev.shLen = prev.length;
      }
      prev.char = cur;
      prev.length = 1;
    }
    return prev;
  }, {
    char: null,
    length: Infinity,
    shLen: Infinity
  });
  return (par.length < par.shLen) ?  par.length : par.shLen;
}

function decodeBits (bits) {
  bits = bits.substring(bits.indexOf('1'), bits.lastIndexOf('1') + 1);
  bits = unStr(bits, shLength(bits));
  return bits.replace(/0000000/g, '   ')
    .replace(/000/g, ' ')
    .replace(/111/g, '-')
    .replace(/1/g, '.')
    .replace(/0/g, '');
}

let decodeMorse = morseCode => {
  return morseCode.trim().split('   ')
    .map(s => s.split(' ')
               .map(c => MORSE_CODE[c])
               .join(''))
    .join(' ');
}

function add(a, b) {
  let res = '', c = 0;
  let aa = a.split("");
  let bb = b.split("");
  while (aa.length || bb.length || c) {
    c += ~~aa.pop() + ~~bb.pop();
    res = (c % 10) + res;
    c = c > 9;
  }
  return res;
}

function rgb(r, g, b){
  return to16(r) + to16(g) + to16(b);
}

function to16(r_g_b) {
  if (r_g_b <= 0) return "00";
  if (r_g_b > 255) return "FF";
  let res = r_g_b.toString(16).toUpperCase();
  return res.length===1 ? "0"+res : res

}

const expandedForm = num =>
  num
    .toString()
    .split('')
    .reverse()
    .map((a, i) => a * Math.pow(10, i))
    .filter(a => a > 0)
    .reverse()
    .join(' + ');

const fl = s => Object.entries(s).map(item => item.join()).sort().join()
function deepCompare(obj1, obj2) {
  if (!obj1 || !obj2) return obj1 === obj2;
  return fl(obj1) === fl(obj2);
};

function towerBuilder(nFloors) {
  return [...Array(nFloors)].map(
    (_, i) =>
      " ".repeat(nFloors - 1 - i) + "*".repeat(i * 2 + 1) + " ".repeat(nFloors - 1 - i)
  );
}

function digPow(n, p) {
  let par =
    n
      .toString()
      .split('')
      .reduce((acc, cur, i, arr) => acc + Math.pow(Number(arr[i]), p + i), 0) / n;
  return ('' + par).includes('.') ? -1 : par;
}

decodeMorse = function(morseCode) {
  return morseCode
    .split(' ')
    .map((z, i) => (MORSE_CODE[z] != undefined ? MORSE_CODE[z] : 1))
    .join('')
    .replace(/11/g, ' ')
    .replace(/1/g, ' ')
    .trim();
};

const sorter = s => s.split('').sort().join('')
function anagrams(word, words) {
  word = sorter(word)
  return words.filter(v => word == sorter(v));
}

function findMissingLetter(array) {
  const lit = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
  for(var i = 0; i < array.length; i++) {
    fIndx = lit.indexOf(array[i].toLowerCase())
    if(array[0] === array[0].toUpperCase()) {
      if(lit[fIndx + 1].toUpperCase() !== array[i + 1]) {
        return lit[fIndx + 1].toUpperCase()
      }
    } else if(array[0] === array[0].toLowerCase()) {
      if(lit[fIndx + 1] !== array[i + 1])
        return lit[fIndx + 1].toLowerCase()
    }
  }
}

function getCount(str) {
  return (str.match(/[aeiou]/ig)||[]).length;
}

function arrayDiff(a, b) {
  return [...a].filter(x => !b.includes(x))
}

function descendingOrder(n){
  return +(String(n)).split('').sort().reverse().join('')
}

function disemvowel(str) {
  return str.replace(/[aeuio]/gi,'');
}

function printerError(s) {
  return `${s.replace(/[a-m]/gi, "").length}/${s.length}`
}

function rowSumOddNumbers(n) {
	return Math.pow(n, 3);
}

function friend(friends){
  return friends.filter(num => num.length === 4)
}

function filter_list(l) {
  return l.filter(v => typeof v == "number")
}

String.prototype.toJadenCase = function () {
    return this.split(' ').
    map(w => w[0].toUpperCase() + w.slice(1)).join(' ');
};

function multiply(a, b){
  return a * b
}