Geek is learning data structures. He wants to learn the trie data structure, but there are a few bit's prerequisites that he must first understand.
Given three bit manipulations functions: XOR, check and setBit.
In XOR function you are given two integers n and m return the xor of n and m.
In check function you are given two integer a and b return 1 if a^{th }bit of b is set otherwise return 0.
In setBit function you are given two integer c and d, set the c^{th }bit of d if not yet set.
Example 1:
Input:
n = 1, m = 2
a = 3, b = 4
c = 5, d = 6
Output: 3 1 38
Explanation: 1 xor 2 = 3, 3^{rd }bit of 4 is set. After setting 5^{th }bit of 6 result is 100110 which in decimal form is 38.
Example 2:
Input: 
n = 7, m = 8
a = 9, b = 10
c = 11, d = 12 
Output: 15 0 2060 
Explanation: 7 xor 8 = 15, 9^{th}^{ }bit of 10 is not set. After setting 11^{th }bit of 12 result is 100000001100 which in decimal form is 2060.
Constraints:
1 <= n <= 10^{5}
1 <= m <= 10^{5}
1 <= a <= 9
1 <= b <= 10^{5}
1 <= c <= 9
1 <= d <= 10^{5}
Your Task:
You don't need to read input or print anything. Your task is to complete three functions XOR(), check() and set().
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Difficulty: MEDIUM
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def XOR(self, n, m):

        # Code here

    def check(self, a, b):

        # Code here

    def setBit(self, c, d):

        # Code here

Solutions:
class Solution:

	def XOR(self, n, m):
		return n ^ m

	def check(self, a, b):
		return b >> a - 1 & 1

	def setBit(self, c, d):
		d = d | 1 << c
		return d


class Solution:

	def XOR(self, n, m):
		return n + m - 2 * (n & m)

	def check(self, a, b):
		if b >> a - 1 & 1 != 0:
			return 1
		else:
			return 0

	def setBit(self, c, d):
		return d | 1 << c


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEnd = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insertAll(self, strs):
		for str in strs:
			self.insert(str)

	def insert(self, ns, ms):
		curr = self.root
		for (n, m) in zip():
			if c not in curr.children:
				curr.children[c] = TrieNode()
			curr = curr.children[c]
		curr.isEnd = True

class Solution:

	def XOR(self, n, m):
		return n ^ m

	def check(self, a, b):
		v = bin(b)[2:][::-1]
		if len(v) < a:
			return 0
		return 1 if v[a - 1] == '1' else 0

	def setBit(self, c, d):
		v = bin(d)[2:][::-1]
		if len(v) < c + 1:
			return d + 2 ** c
		elif v[c] == '0':
			return d + 2 ** c
		else:
			return d


class Solution:

	def XOR(self, n, m):
		return n ^ m

	def check(self, a, b):
		try:
			if bin(b)[-a] == '1':
				return 1
			return 0
		except:
			return 0

	def setBit(self, c, d):
		g = 1
		t = bin(d)[2:]
		if c - len(t) >= 0:
			t = '0' * (c + 1 - len(t)) + t
		t = list(t)
		t[-c - 1] = '1'
		return int(''.join(t), 2)


class Solution:

	def XOR(self, n, m):
		return n ^ m

	def check(self, a, b):
		if b >> a - 1 & 1 == 1:
			return 1
		else:
			return 0

	def setBit(self, c, d):
		if d >> c & 1 == 1:
			return d
		else:
			bi = bin(d)
			bi = bi[2:]
			bi = '0' * (c - len(bi) + 1) + bi
			bi = list(bi)
			bi = bi[::-1]
			bi[c] = '1'
			ans = ''
			for i in bi:
				ans += i
			ans = ans[::-1]
			return int(ans, 2)