Computer Science I Program #6: Priority Hair Salon (Binary Heap)Please check Webcourses for the Due DateRead all the pages before starting to write your codeA new hair salon has opened up near your house and they need a computer science student to helpwith their scheduling. You figure a couple extra bucks can't hurt and take the job!The hair salon has several stylists (no more than 10 working at a time). Each customer arrives at aparticular time and then gets placed in a line to wait for a stylist. (Each stylist has their own waitingline.) The line in which a customer is placed is based on the following:1. If the customer has no preference, she gets placed in the line for the stylist with the fewestwaiting customers. If there's still a tie (multiple stylists have the same number of customerswaiting), then the stylist at the lowest numbered hair-cutting station cuts the customer's hair.2. If the customer has a preferred stylist AND that stylist is working, she gets placed in herpreferred stylist's line, regardless of how big it is. If the customer has a preferred stylist and thatstylist is not working, then the customer gets placed according to rule #1.But as the name suggests, the hair salon for which you work gives priority to certain individualsand doesn't work strictly on a first come first served basis. In particular, each line for each stylistis actually a priority queue instead of a standard queue. Whenever a stylist is free to cut hair, he'llchoose the customer in his line with the highest priority. Here is how priority is determined:1. Each customer has a number of loyalty points. The higher the number of loyalty points, thehigher the priority for the customer.2. If two customers have the same number of loyalty points, and only one of those customers haslabeled this stylist (the one whose line she is in) as their preferred stylist, then that customer getspriority.3. If two customers have the same number of loyal points, and either both or neither prefer thestylist whose line they are in, then the tie is broken by name, in alphabetical order. Thus,"SHELLY" would get preference over "YUAN", if the tie isn't broken by the previous items. Allcustomers will have unique names, so this third rule is guaranteed to completely determine prioritybetween a set of waiting customers.When a customer arrives at the salon, they provide the following information:1. The time in minutes, after the salon opens that they arrive (non-negative integer)2. Their name (uppercase string of letters, length in between 1 and 20, inclusive)3. The name of their preferred stylist (or "NONE" if they don't have a preferred stylist)4. Number of loyalty points (non-negative integer)5. Time of their hair cut, in minutes (positive integer)The last item is important because it also determines the number of loyalty points earned after thecut. In particular, for a m minute haircut, a customer earns m/10 loyalty points, using integerdivision.Finally, in the case that one person completes a haircut at time T for one stylist, and at thatexact time (time T) a person arrives for a haircut in the line for the same stylist, FIRST placethis person in the priority queue for the stylist before determining who will fill the next spotfor the stylist. (So for example, if Sally finishes her haircut with stylist Jerome at time t =1000, and at that time Becky and Michael are waiting for a haircut from Jerome but at timet = 1000, Nellie arrives for a haircut, ADD Nellie to the priority queue with Becky andMichael and THEN choose which person's hair Jerome will cut next.The ProblemYour task will be to write a program that takes in information about arriving customers in the orderin which they come (each one will come at a distinct minute after the salon opens to avoidconcurrency issues), and prints out a log in the order in which the haircuts finish, summarizingeach cut. If two cuts end at the same exact time, then the log for the cut made by the stylist at thelower numbered hair cut station should be printed first.The Input (to be read from standard input)Note: Your program will be run multiple times, using different input cases. Your program shouldjust process one input case. This is different than most of the previous programs.The first line of input will contain two space-separated integers, n (n ≤ 100000), representing thenumber of customers, and m (m ≤ 10), representing the number of stylists working at the salon forthe input case. (No stylist will have the name "NONE".)The following m lines will each contain a single string. The ith (1 ≤ i the name of the hair stylist at the ith styling station. Each of these strings will consist of in between1 and 20 upper case letters. Each stylist is ready to cut hair at time t = 0 minutes after the salonopens.The last n lines of the input case will each contain information about a single customer. The ith (1≤ i ≤ n) of these lines will store the following space-separated information: ti (0 ≤ ti ≤ 109), si, pi, li(0 ≤ li ≤ 105) and mi (0 ≤ mi ≤ 104), representing the time the customer arrives (in minutes) after thesalon opens, the customer's name (a string of in between 1 and 20 uppercase letters that is NOT"NONE", the preferred stylist for this customer (if this string is "NONE", that means there is nopreferred stylist, otherwise the string represents the name of the preferred stylist, who may or maynot be working), the number of loyalty points the customer currently has, and the amount of timein minutes the haircut the customer is requesting will take.These lines of input will in strictly chronologically increasing order. Thus, for all distinct pairs ofintegers i and j with 1 ≤ i The Output (to be printed to standard out)For each customer, print out a single line in the following format:CUSTOMER M L STYLISTWhere CUSTOMER is the name of the customer who got their hair cut, M is the number of minutesafter the salon opened that the haircut was completed, L is the number of loyalty points thecustomer has AFTER the haircut and STYLIST is the name of the stylist who cut the customer'shair.These lines should be ordered by the time after the salon opens that the haircuts complete. If thereare two or more haircuts that complete at the same time, print these lines out in order of thehaircutting station of the stylists, from smallest to largest.Sample Input9 3DAVESANDYBELLA10 JASON SANDY 50 7711 SARAH NONE 0 3015 CYNTHIA MAX 44 8122 RAVI SANDY 30 4227 CHEN SANDY 30 9930 AMY DAVE 5 2531 WENDY SANDY 31 1533 BRIAN NONE 100 1037 MAC SANDY 29 45Sample OutputSARAH 41 3 DAVEAMY 66 7 DAVEJASON 87 57 SANDYCYNTHIA 96 52 BELLAWENDY 102 32 SANDYBRIAN 106 101 BELLACHEN 201 39 SANDYRAVI 243 34 SANDYMAC 288 33 SANDYNote: This sample was generated by hand so there may be an error in it (mental arithmetic error).If so, it will be fixed before the assignment is due.Implementation Restrictions/ Run-Time/Memory Restrictions1. An appropriate structure should be used to store customer information.2. A binary heap structure should be declared and used to implement the priority queues necessaryto solve the problem. This structure should internally have an array of pointers to struct. Thearray itself should ALSO be dynamically allocated. (Whenever the heap fills up, the array sizestoring the heap should be doubled.)3. Appropriate functions should be written for the binary heap structure.4. A statically allocated array of (size 10) binary heap structures should be declared in main tostore the lines for each stylist.5. For full credit, your algorithm must run in O(nlgn) time by implementing O(lg n) operationsfor the binary heap structure.6. You must free all dynamically allocated memory for full credit.7. Note - for arranging the output, you may either output lines as they occur chronologically, orstore all of the output lines in a large array, and then sort that array before outputting all of thelines. (There are multiple ways to solve this issue.)