from collections import deque

class       snake_case					:




  def __init__(      self     :	Union[str, Any]     , a_     :	str     , a_     :	int     , a_     :	int				)->       None:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				Optional[int]			=		process_name  # process name
       SCREAMING_SNAKE_CASE__				:				Any			=		arrival_time  # arrival time of the process
       # completion time of finished process or last interrupted time
       SCREAMING_SNAKE_CASE__				:				Optional[int]			=		arrival_time
       SCREAMING_SNAKE_CASE__				:				List[Any]			=		burst_time  # remaining burst time
       SCREAMING_SNAKE_CASE__				:				Any			=		0  # total time of the process wait in ready queue
       SCREAMING_SNAKE_CASE__				:				List[Any]			=		0  # time from arrival time to completion time




class       snake_case					:




  def __init__(      self     :	List[str]     , a_     :	int     , a_     :	list[int]     , a_     :	deque[Process]     , a_     :	int     , )->       None:




       """simple docstring"""
       # total number of mlfq's queues
       SCREAMING_SNAKE_CASE__				:				Dict			=		number_of_queues
       # time slice of queues that round robin algorithm applied
       SCREAMING_SNAKE_CASE__				:				Tuple			=		time_slices
       # unfinished process is in this ready_queue
       SCREAMING_SNAKE_CASE__				:				List[str]			=		queue
       # current time
       SCREAMING_SNAKE_CASE__				:				Dict			=		current_time
       # finished process is in this sequence queue
       SCREAMING_SNAKE_CASE__				:				deque[Process]			=		deque()




  def 	__lowercase(      self     :	Tuple				)->       list[str]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				str			=		[]
       for i in range(len(self.finish_queue				)				):
            sequence.append(self.finish_queue[i].process_name				)
       return sequence




  def 	__lowercase(      self     :	Tuple     , a_     :	list[Process]				)->       list[int]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				Tuple			=		[]
       for i in range(len(a_				)				):
            waiting_times.append(queue[i].waiting_time				)
       return waiting_times




  def 	__lowercase(      self     :	Any     , a_     :	list[Process]				)->       list[int]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				List[Any]			=		[]
       for i in range(len(a_				)				):
            turnaround_times.append(queue[i].turnaround_time				)
       return turnaround_times




  def 	__lowercase(      self     :	Any     , a_     :	list[Process]				)->       list[int]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				Optional[int]			=		[]
       for i in range(len(a_				)				):
            completion_times.append(queue[i].stop_time				)
       return completion_times




  def 	__lowercase(      self     :	int     , a_     :	deque[Process]				)->       list[int]:




       """simple docstring"""
       return [q.burst_time for q in queue]




  def 	__lowercase(      self     :	Optional[int]     , a_     :	Process				)->       int:




       """simple docstring"""
       process.waiting_time += self.current_time - process.stop_time
       return process.waiting_time




  def 	__lowercase(      self     :	List[Any]     , a_     :	deque[Process]				)->       deque[Process]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				deque[Process]			=		deque()  # sequence deque of finished process
       while len(a_				) != 0:
            SCREAMING_SNAKE_CASE__				:				Any			=		ready_queue.popleft()  # current process

            # if process's arrival time is later than current time, update current time
            if self.current_time < cp.arrival_time:
                 self.current_time += cp.arrival_time

            # update waiting time of current process
            self.update_waiting_time(a_				)
            # update current time
            self.current_time += cp.burst_time
            # finish the process and set the process's burst-time 0
            SCREAMING_SNAKE_CASE__				:				Tuple			=		0
            # set the process's turnaround time because it is finished
            SCREAMING_SNAKE_CASE__				:				str			=		self.current_time - cp.arrival_time
            # set the completion time
            SCREAMING_SNAKE_CASE__				:				int			=		self.current_time
            # add the process to queue that has finished queue
            finished.append(a_				)

       self.finish_queue.extend(a_				)  # add finished process to finish queue
       # FCFS will finish all remaining processes
       return finished




  def 	__lowercase(      self     :	Union[str, Any]     , a_     :	deque[Process]     , a_     :	int				)->       tuple[deque[Process], deque[Process]]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__				:				deque[Process]			=		deque()  # sequence deque of terminated process
       # just for 1 cycle and unfinished processes will go back to queue
       for _ in range(len(a_				)				):
            SCREAMING_SNAKE_CASE__				:				Tuple			=		ready_queue.popleft()  # current process

            # if process's arrival time is later than current time, update current time
            if self.current_time < cp.arrival_time:
                 self.current_time += cp.arrival_time

            # update waiting time of unfinished processes
            self.update_waiting_time(a_				)
            # if the burst time of process is bigger than time-slice
            if cp.burst_time > time_slice:
                 # use CPU for only time-slice
                 self.current_time += time_slice
                 # update remaining burst time
                 cp.burst_time -= time_slice
                 # update end point time
                 SCREAMING_SNAKE_CASE__				:				Optional[Any]			=		self.current_time
                 # locate the process behind the queue because it is not finished
                 ready_queue.append(a_				)
            else:
                 # use CPU for remaining burst time
                 self.current_time += cp.burst_time
                 # set burst time 0 because the process is finished
                 SCREAMING_SNAKE_CASE__				:				List[Any]			=		0
                 # set the finish time
                 SCREAMING_SNAKE_CASE__				:				int			=		self.current_time
                 # update the process' turnaround time because it is finished
                 SCREAMING_SNAKE_CASE__				:				List[str]			=		self.current_time - cp.arrival_time
                 # add the process to queue that has finished queue
                 finished.append(a_				)

       self.finish_queue.extend(a_				)  # add finished process to finish queue
       # return finished processes queue and remaining processes queue
       return finished, ready_queue




  def 	__lowercase(      self     :	int				)->       deque[Process]:




       """simple docstring"""

       #  all queues except last one have round_robin algorithm
       for i in range(self.number_of_queues - 1				):
            SCREAMING_SNAKE_CASE__			,							SCREAMING_SNAKE_CASE__				:				List[str]			=		self.round_robin(
                self.ready_queue     , self.time_slices[i]				)
       #  the last queue has first_come_first_served algorithm
       self.first_come_first_served(self.ready_queue				)

       return self.finish_queue


if __name__ == "__main__":
      import doctest

      SCREAMING_SNAKE_CASE__		:					List[str]						=					Process("P1", 0, 53)
      SCREAMING_SNAKE_CASE__		:					List[str]						=					Process("P2", 0, 17)
      SCREAMING_SNAKE_CASE__		:					Any						=					Process("P3", 0, 68)
      SCREAMING_SNAKE_CASE__		:					Optional[int]						=					Process("P4", 0, 24)
      SCREAMING_SNAKE_CASE__		:					Optional[Any]						=					3
      SCREAMING_SNAKE_CASE__		:					int						=					[17, 25]
      SCREAMING_SNAKE_CASE__		:					str						=					deque([Pa, Pa, Pa, Pa])

      if len(time_slices) != number_of_queues - 1:
            raise SystemExit(0)

      doctest.testmod(extraglobs={"queue": deque([Pa, Pa, Pa, Pa])})

      SCREAMING_SNAKE_CASE__		:					Union[str, Any]						=					Process("P1", 0, 53)
      SCREAMING_SNAKE_CASE__		:					List[Any]						=					Process("P2", 0, 17)
      SCREAMING_SNAKE_CASE__		:					Optional[Any]						=					Process("P3", 0, 68)
      SCREAMING_SNAKE_CASE__		:					int						=					Process("P4", 0, 24)
      SCREAMING_SNAKE_CASE__		:					Union[str, Any]						=					3
      SCREAMING_SNAKE_CASE__		:					List[Any]						=					[17, 25]
      SCREAMING_SNAKE_CASE__		:					int						=					deque([Pa, Pa, Pa, Pa])
      SCREAMING_SNAKE_CASE__		:					List[str]						=					MLFQ(number_of_queues, time_slices, queue, 0)
      SCREAMING_SNAKE_CASE__		:					Union[str, Any]						=					mlfq.multi_level_feedback_queue()

      # print total waiting times of processes(P1, P2, P3, P4)
      print(
          F"""waiting time:\
        \t\t\t{MLFQ.calculate_waiting_time(mlfq, [Pa, Pa, Pa, Pa])}"""
      )
      # print completion times of processes(P1, P2, P3, P4)
      print(
          F"""completion time:\
        \t\t{MLFQ.calculate_completion_time(mlfq, [Pa, Pa, Pa, Pa])}"""
      )
      # print total turnaround times of processes(P1, P2, P3, P4)
      print(
          F"""turnaround time:\
        \t\t{MLFQ.calculate_turnaround_time(mlfq, [Pa, Pa, Pa, Pa])}"""
      )
      # print sequence of finished processes
      print(
          F"""sequence of finished processes:\
        {mlfq.calculate_sequence_of_finish_queue()}"""
      )




def     _a				(      lowercase__  :			int = 1_00_00_00 ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__				:				str			=		[i - 1 for i in range(limit + 1 )]

     for i in range(2     ,  limit + 1 ):
          if phi[i] == i - 1:
               for j in range(2 * i     ,  limit + 1     ,  lowercase__ ):
                    phi[j] -= phi[j] // i

     return sum(phi[2 : limit + 1] )


if __name__ == "__main__":
      print(solution())



