You start with an array A of size N. Initially all elements of the array A are zero. You will be given K positive integers. Let j be one of these integers, you have to add 1 to all A[i], where i ≥ j. Your task is to print the array A after all these K updates are done. 
Note: Indices in updates array are given in 1-based indexing. That is updates[i] are in range [1,N].
Example 1: 
Input:
N = 3, K = 4
1 1 2 3
Output:
2 3 4
Explanation:
Initially the array is {0, 0, 0}. After the
first 1, it becomes {1, 1, 1}. After the
second 1 it becomes {2, 2, 2}. After 2, 
it becomes {2, 3, 3} and 
After 3 it becomes, {2, 3, 4}. 
Example 2: 
Input:
N = 2, K = 3
1 1 1
Output:
3 3 
Explanation:
Initially the array is {0, 0}. After the
first 1, it becomes {1, 1}. After the
second 1 it becomes {2, 2}. After the
third 1, it becomes {3, 3}.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function update() which takes the array A[] and its size N as inputs and make the updates and fill the array A[].
Expected Time Complexity: O(K)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, K ≤ 10^{5
}1^{ }≤ updates[i] ≤ N, for all i from 1 to K.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def update(self, a, n, updates, k):

        # Your code goes here



Solutions:
class Solution:

	def update(self, a, n, updates, k):
		for i in range(k):
			a[updates[i] - 1] += 1
		for i in range(1, n):
			a[i] += a[i - 1]
		return a


class Solution:

	def update(self, a, n, up, k):
		for i in range(0, k):
			a[up[i] - 1] += 1
		for i in range(1, n):
			a[i] += a[i - 1]
		return a


from collections import defaultdict

class Solution:

	def update(self, a, n, updates, k):
		store = defaultdict(lambda : 0)
		for item in updates:
			store[item] += 1
		count = 0
		for i in range(n):
			count += store[i + 1]
			a[i] = count
		return


class Solution:

	def update(self, arr, n, updates, k):
		for j in updates:
			a[j - 1] += 1
		for j in range(1, n):
			arr[j] += arr[j - 1]
		return arr


class Solution:

	def update(self, a, n, updates, k):
		i = 0
		while i < k:
			a[updates[i] - 1] += 1
			i += 1
		i = 1
		while i < n:
			a[i] += a[i - 1]
			i += 1


class Solution:

	def update(self, a, n, updates, k):
		d = [0] * (n + 1)
		d[0] = a[0]
		for i in range(1, n):
			d[i] = a[i] - a[i - 1]
		for j in updates:
			d[j - 1] += 1
			d[n] -= 1
		a[0] = d[0]
		for i in range(1, n):
			a[i] = d[i] + a[i - 1]
		return a


class Solution:

	def update(self, A, n, updates, k):
		countarr = [0] * n
		for i in updates:
			countarr[i - 1] += 1
		A[0] = countarr[0]
		for i in range(1, n):
			A[i] = A[i - 1] + countarr[i]
		return A


class Solution:

	def update(self, a, n, up, k):
		for i in range(k):
			up[i] -= 1
		up.sort()
		c = 0
		i = 0
		j = 0
		l = up[j]
		while i < n:
			while l <= i and j <= k - 1:
				c += 1
				j += 1
				if j == k:
					break
				l = up[j]
			a[i] = c
			i += 1


class Solution:

	def update(self, a, n, u, k):
		for i in range(0, k):
			a[u[i] - 1] += 1
		for i in range(1, n):
			a[i] += a[i - 1]


class Solution:

	def update(self, a, n, updates, k):
		for i in range(len(updates)):
			a[updates[i] - 1] = a[updates[i] - 1] + 1
		update = 0
		for i in range(n):
			update += a[i]
			a[i] = update


class Solution:

	def update(self, a, n, updates, k):
		D = []
		D.append(a[0])
		for i in range(1, len(a)):
			D.append(a[i] - a[i - 1])
		for j in updates:
			D[j - 1] += 1
		a[0] = D[0]
		for i in range(1, len(a)):
			a[i] = D[i] + a[i - 1]


class Solution:

	def update(self, a, n, updates, k):
		temp = [0 for _ in range(n + 1)]
		for u in updates:
			temp[u] += 1
		a[0] = temp[1]
		for i in range(1, len(a)):
			a[i] = a[i - 1] + temp[i + 1]


class Solution:

	def update(self, a, n, updates, k):
		for x in updates:
			a[x - 1] += 1
		c = 0
		for i in range(n):
			c += a[i]
			a[i] = c
		return a


from bisect import bisect_right

class Solution:

	def update(self, a, n, updates, k):
		updates = sorted(updates)
		for i in range(n):
			a[i] = bisect_right(updates, i + 1)


class Solution:

	def update(self, a, n, updates, k):
		self.a = [0 for i in range(1, n)]
		for j in range(k):
			a[updates[j] - 1] += 1
		for m in range(1, n):
			a[m] += a[m - 1]


class Solution:

	def update(self, a, n, updates, k):
		updates.sort()
		delta = 0
		count = 0
		updates_complete = False
		for i in range(n):
			while not updates_complete and updates[count] == i + 1:
				delta += 1
				count += 1
				updates_complete = count == len(updates)
			a[i] = delta


class Solution:

	def update(self, a, n, updates, k):
		for i in range(0, k):
			a[updates[i] - 1] += 1
		for j in range(1, n):
			a[j] = a[j] + a[j - 1]
if __name__ == '__main__':
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, k) = (sz[0], sz[1])
		a = [0 for i in range(n)]
		updates = [int(x) for x in input().strip().split()]
		ob = Solution()
		ob.update(a, n, updates, k)
		print(*a)
		T -= 1