In this question we will look at a particular parallel primitive called "scan" (also known as "parallel prefix"). We are looking at a "sum-scan" (a scan with addition as the operator). Sum-scan has two variants. In an"exclusive sum-scan", the output at each data element is the sum of all the input elements that came before that element. In an "inclusive sum-scan" the output at each data element is the sum of all the input elements up to and including that element. For instance, the exclusive sum-scan of the vector 1 2 3 4 is [01 3 6], and the inclusive sum-scan of the vector [1 2 3 4 is [1 3 6 10 We will look at three different formulations of scan. In the algorithmic descriptions below, r is the input array, n is the number of items to scan, and d is the step number. . First, the serial algorithm (Algorithm 1) is simple. . The first parallel formulation is from Hillis and Steele (Algorithm 2). This is an inclusive Sum-scan . The second parallel formulation is from Blelloch (Algorithm 3). This is an exclusive sum- scan. It has two phases, first an up-sweep phase, then a down-sweep phase. a) It's important that you be able to interpret algorithms such as those above. Show the step-by-step result of both a Hillis and Steele scan and a Blelloch scan on the input array 1 2 3 456 7 8