Your friend is in charge of hiring several typists (!!!) for his company. Due to the prestigious nature (!!!) of the job and the tight work schedule, a non-standard process is being followed. The typing exam assigned a (percentile) score to every applicant which for simplicity can be taken to be some integer -- so all you know is that each typist is assigned a unique integral score from 1 to n and for every score s there is a typist with score s. The typists are asked to report on any day among d days (assume days 1 ... d) and they are added to a pool (not a swimming pool) maintained by your friend's team. At the end of every day, the typist with the highest score among those in the pool is selected, removed from the pool and offered a position.

For example, consider the following sequence of activities:
day 1 : scores are 8, 20, 7, 54, 26 => 54 is hired
day 2 : scores are 98, 83, 17, 48, 33, 22, 11 => 98 is hired
day 3: scores are 67, 81, 19 => 83 (from day 2 but still in the pool) is hired
day 4: scores are 5 => 81 is hired
etc.

You got excited hearing this algorithmic problem, however, since you have not been taught online algorithms (yet), you decided to solve an offline version of it.
Let the input to the problem be a sequence of sets of scores : S_1 S_2 ... S_d and the objective is to determine the array Hired[1 ... d]. Being the offline version, imagine that the entire sequence of sets S_1 ... S_d is provided at once. Design an algorithm that runs in O(n) time assuming that there exists a disjoint-set implementation in which MakeSet, Find and Union take O(1) time. It should output a correctly filled array Hired[]. Do not augment your disjoint set with delete() operation. It is safe to assume that d <= n.

Hint: Instead of trying to figure out who would be hired on day 1, on day 2, etc., think of an approach that determines when does the typist with score n get hired, that with score n-1 get hired, etc.
Hint: You may have to store additional fields with every element in your sets. For that you can assume that scores are objects to which you can add suitable fields/members.
Hint: If you need, you can access the scores on any day as S_t[1] ... S_t[m_t] in which m_t denotes the number of typists reporting on the t-th day.