#!/usr/bin/env ruby


class Item
  attr_accessor :word, :type, :link
  def initialize word, type
    @word = word
    @type = type
    @link = nil
  end
end

class MockShiftReduceParser
  attr_accessor :state

  def initialize
    @state = nil
    
    @a = {}
    @a[nil] = {}
    @a[nil][nil] = 'S'
    @a[nil]['f'] = 'S'
    @a[nil]['l'] = 'S'
    @a[nil]['r'] = 'illegal'

    @a['f'] = {}
    @a['f']['f'] = 'S' # FIXME conflict
    @a['f']['l'] = 'S'
    @a['f']['r'] = 'R'

    @a['l'] = {}
    @a['l']['f'] = 'L'
    @a['l']['l'] = 'S'
    @a['l']['r'] = 'illegal'

    @a['r'] = {}
    @a['r']['f'] = 'illegal'
    @a['r']['l'] = 'illegal'
    @a['r']['r'] = 'illegal'
  end

  def advance type
    if    !@state 
      @state = type
      puts "-/- -> S -> #{@state}"
      return
    end
    action = @a[@state][type]
    prev_state = @state
    if action == 'S'
      @state = type
    elsif action == 'L' or action == 'R'
      @state = 'f'
    end
    puts "#{prev_state}/#{type} -> #{action} -> #{@state}"

    return action
  end
end


parser = MockShiftReduceParser.new

items = []
head = nil
stack = []

while line = STDIN.gets
  word, type = line.split
  item = Item.new word, type
  items << item
  stack << item

  head = item if !head

  action = parser.advance item.type
  if action == "S"
    head = item
  elsif action == "R"
    _ = stack.pop
    _.link = head
  elsif action == "L"
    head = item
    puts stack.size
    del = []
    stack.each_with_index { |i,j|
      if i.type == 'l'
        i.link = head
        del << j
      end
    }
    del.reverse.each { |d| stack.delete_at(d) }
    puts stack.size
  end
end

stack.each { |i| i.link = head }

puts "---"
items.each { |j| if j.link then puts "#{j.word} #{j.link.word}" else puts "#{j.word} ?" end }