[Unlike most problems in my puzzle collection, this problem requires some computer science knowledge. Many years ago, I read a solution to this problem in one of Donald Knuth’s books (I think). The algorithm intrigued me and stuck in my mind.]

Consider the following array operations. Init(N,d) initializes an array of N elements so that each element has value d. Once Init has been called, the following two operations can be applied: For any i such that 0 <= i < N, Get(i) returns the array element at position i and Set(i,v) sets the array element at position i to the value v.

Given any amount of memory you want, implement the three operations so that each operation has an O(1) time complexity.