module treap                        !モジュールdictionaryに含まれている
  implicit none
  type node
    type(node), pointer :: left => null(), right => null()
    character(10) :: key            !文字数．必要に応じて型も変更
    integer :: val
    integer :: pri                  ! min-heap
    integer :: cnt = 1
  end type node

  contains

  subroutine update(root)           ! 1つ上の段のcnt
    implicit none
    type(node), pointer, intent(in) :: root
    root%cnt = my_count(root%left) + my_count(root%right) + 1
  end subroutine update

  function my_count(root)           ! cntを与える
    implicit none
    type(node), pointer, intent(in) :: root
    integer :: my_count
    if (associated(root)) then      ! rootが空なら偽
      my_count = root%cnt
    else
      my_count = 0
    end if
  end function my_count

  function rotate_ccw(root)         !左回転
    implicit none
    type(node), pointer, intent(in) :: root
    type(node), pointer :: tmp, rotate_ccw
    if (.not. associated(root%right)) stop 1   ! rightが空なら真
    tmp => root%right
    root%right => tmp%left
    tmp%left => root
    rotate_ccw => tmp
    call update(root)
    call update(tmp)
  end function rotate_ccw

  function rotate_cw(root)          !右回転
    implicit none
    type(node), pointer, intent(in) :: root
    type(node), pointer :: tmp, rotate_cw
    if (.not. associated(root%left)) stop 1
    tmp => root%left
    root%left => tmp%right
    tmp%right => root
    rotate_cw => tmp
    call update(root)
    call update(tmp)
  end function rotate_cw

  recursive function insert(root, key, val, pri) result(res)   !挿入
    implicit none
    type(node), pointer, intent(in) :: root
    integer, intent(in) :: pri
    character(10), intent(in) :: key
    integer, intent(in) :: val
    type(node), pointer :: res

    if (.not. associated(root)) then          !rootが空なら真
      allocate(res)
      res%key = key
      res%pri = pri
      res%val = val
    else
      res => root
      if (key > root%key) then
        root%right => insert(root%right, key, val, pri)
        call update(root)
        if (root%pri > root%right%pri) then
          res => rotate_ccw(res)
        end if
      else
        root%left => insert(root%left, key, val, pri)
        call update(root)
        if (root%pri > root%left%pri) then
          res => rotate_cw(res)
        end if
      end if
    end if
  end function insert

  recursive function erase(root, key) result(res)   !削除するものを葉に追い詰めていく
    implicit none
    type(node), pointer, intent(in) :: root
    character(10), intent(in) :: key
    type(node), pointer :: res, tmp

    if (.not. associated(root)) then          !空なら真
      print *, "Erase failed"
      stop 1
    end if

    if (key < root%key) then
      root%left => erase(root%left, key)
      res => root
    else if (key > root%key) then
      root%right => erase(root%right, key)
      res => root
    else                                       !削除するkeyを見つけた
      if ((.not. associated(root%left)) .or. (.not. associated(root%right))) then     !子が１人以下
        tmp => root
        if (.not. associated(root%left)) then
          res => root%right
        else
          res => root%left
        end if
        deallocate(tmp)
      else                                      !子が２人なら回転してやり直す
        if (root%left%pri < root%right%pri) then
          res => rotate_ccw(root)
          res%left => erase(res%left, key)
        else
          res => rotate_cw(root)
          res%right => erase(res%right, key)
        end if
      end if
    end if
    if (associated(res)) call update(res)
  end function erase

  recursive function find_node(root, key) result(res)   !keyの入ったnodeを探す
    implicit none
    type(node), pointer, intent(in) :: root
    character(10), intent(in) :: key
    type(node), pointer :: res
    if (.not. associated(root)) then
      res => null()
    else if (root%key == key) then
      res => root
    else if (key < root%key) then
      res => find_node(root%left, key)
    else
      res => find_node(root%right, key)
    end if
  end function find_node

  recursive function kth_node(root, k) result(res)   !k番目のノードを与える
    implicit none
    type(node), pointer, intent(in) :: root
    integer, intent(in) :: k
    type(node), pointer :: res
    if (.not. associated(root)) then
      res => null()
    else if (k <= my_count(root%left)) then
      res => kth_node(root%left, k)
    else if (k == my_count(root%left) + 1) then
      res => root
    else
      res => kth_node(root%right, k - my_count(root%left) - 1)
    end if
  end function kth_node

  recursive subroutine delete_all(root)          !全消去
    implicit none
    type(node), pointer, intent(inout) :: root
    if (.not. associated(root)) return

    call delete_all(root%left)
    call delete_all(root%right)
    deallocate(root)
    nullify(root)
  end subroutine delete_all

  recursive subroutine inorder(root, keys, vals, counter)
    implicit none
    type(node), pointer, intent(in) :: root
    character(10), intent(inout) :: keys(:)
    integer, intent(inout) :: vals(:)
    integer, intent(inout) :: counter
    if (.not. associated(root)) return

    call inorder(root%left, keys, vals, counter)
    counter = counter + 1
    keys(counter) = root%key
    vals(counter) = root%val
    call inorder(root%right, keys, vals, counter)
  end subroutine inorder
end module treap

module dictionary
  use treap
  implicit none

  type dict
    type(node), pointer :: root => null()
    integer :: randstate = 1231767121
    ! contains
    ! final :: destruct_dict
  end type dict

  contains

  pure function xorshift32(i)           !乱数生成
    implicit none
    integer(4), intent(in) :: i
    integer(4) :: xorshift32
    if (i == 0) then
      xorshift32 = 1231767121
    else
      xorshift32 = i
    end if
    xorshift32 = ieor(xorshift32, ishft(xorshift32, 13))
    !ieorは排他的論理和．各ビットについて，片方のみが1なら1を，そうでなければ0を返す．
    xorshift32 = ieor(xorshift32, ishft(xorshift32, -17))
    !ishiftは循環桁上げなしの論理シフト．正なら左にずらす．空いてる桁には0を入れる．
    xorshift32 = ieor(xorshift32, ishft(xorshift32, 15))
  end function xorshift32

  function get_val(t, key)          !入力されたkeyをもつ辞書のvalを返す．
    implicit none
    type(dict), intent(in) :: t
    character(10), intent(in) :: key
    type(node), pointer :: nd
    integer :: get_val
    nd => find_node(t%root, key)
    if (.not. associated(nd)) then          !ndが空なら真
      stop 105
    end if
    get_val = nd%val
  end function get_val

  function exists(t, key)           !入力されたkeyをもつ辞書があれば真を返す．
    implicit none
    type(dict), intent(in) :: t
    character(10), intent(in) :: key
    type(node), pointer :: nd
    logical :: exists
    nd => find_node(t%root, key)
    exists = (associated(nd))
  end function exists

  subroutine insert_or_assign(t, key, val)
    !同じkeyをもつ辞書がなければランダムなpriを与えて挿入，あればvalを割り当てる
    implicit none
    type(dict), intent(inout) :: t
    character(10), intent(in) :: key
    integer, intent(in) :: val
    type(node), pointer :: nd
    nd => find_node(t%root, key)
    if (associated(nd)) then
      nd%val = val
    else  ! This implementation is not optimal
      t%root => insert(t%root, key, val, t%randstate)
      t%randstate = xorshift32(t%randstate)
    end if
  end subroutine insert_or_assign

  subroutine remove(t, key)          !同じkeyをもつ辞書を削除
    implicit none
    type(dict), intent(inout) :: t
    character(10), intent(in) :: key
    t%root => erase(t%root, key)
  end subroutine remove

  function get_kth_key(t, k)          !k番目の辞書を得る
    implicit none
    type(dict), intent(in) :: t
    integer, intent(in) :: k
    type(node), pointer :: res
    character(10) :: get_kth_key
    if (k < 1 .or. k > my_count(t%root)) then
      print *, "get_kth_key failed"
      stop 2
    else
      res => kth_node(t%root, k)
      get_kth_key = res%key
    end if
  end function get_kth_key

  subroutine get_keys_vals(t, keys, vals, n)    !nは項目数，keyおよびvalを順番に羅列
    implicit none
    type(dict), intent(in) :: t
    integer, intent(in) :: n
    character(10), intent(out) :: keys(n)
    integer, intent(out) :: vals(n)
    integer :: counter
    if (my_count(t%root) /= n) stop 5
    counter = 0
    call inorder(t%root, keys, vals, counter)
  end subroutine get_keys_vals

  function get_size(t)                    !辞書の項目数
    implicit none
    type(dict), intent(in) :: t
    integer :: get_size
    get_size = my_count(t%root)
  end function get_size

  subroutine destruct_dict(t)            !辞書の全削除
    implicit none
    type(dict), intent(inout) :: t
    call delete_all(t%root)
  end subroutine destruct_dict

end module dictionary

program ABC155_C
  use dictionary
  character(10),allocatable::s(:)
  integer,allocatable::cnts(:)
  integer::i,N,mc,k
  type(dict)::cnt
  read(*,*)N
  allocate(s(N),cnts(N))
  do i=1,N
     read(*,*)s(i)
     if(exists(cnt,s(i))) then
        call insert_or_assign(cnt,s(i),1+get_val(cnt,s(i)))
     else
        call insert_or_assign(cnt,s(i),1)
     end if
  end do
  k=get_size(cnt)
  call get_keys_vals(cnt,s(1:k),cnts(1:k),k)
  mc=maxval(cnts(1:k))
  do i=1,k
     if(cnts(i)==mc) then
        write(*,*)trim(s(i))
     end if
  end do
end program ABC155_C

Measured memory_bytes: 14208