#!/usr/bin/env python

import sys
import os
import time
import termios
import select
import threading

def dbg(s, *arg):
	sys.stderr.write(s.format(*arg) + os.linesep)
	sys.stdout.flush()

def out(s):
	sys.stdout.write(s)

def flush():
	sys.stdout.flush()

def has(o, p):
	t = type(o)
	if t == list:
		return p < len(o)
	elif t == dict:
		return p in o
	return hasattr(o, p)

def set(o, p, v):
	t = type(o)
	if t == list and has(o, p):
		o[p] = v
	elif t == dict:
		o[p] = v
	else:
		setattr(o, p, v)

def get(o, p, v=None):
	t = type(o)
	if t == list:
		return o[p] if has(o, p) else v
	elif t == dict:
		return o.get(p, v)
	return getattr(o, p, v)

class Empty:
	def __init__(self, pcls=None):
		if pcls:
			dic_to_cls( cls_to_dic(pcls), self )

def cls_to_dic(c):
	ks = filter( lambda k: not k.startswith('_'), dir(c) )
	return dict( map( lambda k: ( k, getattr(c, k) ), ks ) )

def dic_to_cls(d, c=None):
	if not c:
		c = Empty()
	map( lambda (k, v): setattr(c, k, v), d.items() )
	return c

def extends(pcls, c=None):
	if not c:
		c = Empty()
	dic_to_cls( cls_to_dic(pcls), c )
	return c

def gval(init_v=None):
	e = Empty()
	e.v = init_v
	return lambda v='get': e.v if v == 'get' else setattr(e, 'v', init_v if v == 'reset' else v)

def rlock(rl=None):
	if not rl:
		rl = threading.RLock()
	e = extends(rl) # for e.acquire, e.release
	e.rl = rl
	e.lock = rl.acquire
	e.unlock = rl.release
	return e

def lock_wrap(f, rl=None):
	if not rl:
		rl = rlock()
	e = extends(rl)
	def wrap_f(*args):
		rl.lock()
		r = f(*args)
		rl.unlock()
		return r
	e.f = wrap_f
	return e

hz_to_sec = lambda hz: 1.0 / hz if hz > 0 else 0
sec_to_hz = lambda sec: 1.0 / sec if sec > 0 else 0

def sleep(sec):
	time.sleep(sec)

def sleep_hz(hz):
	time.sleep( hz_to_sec(hz) )

def timer_new(f=None, args=[], sec=0, repeat=False):
	e = Empty()
	e.obj = None
	e.f = f
	e.args = args
	e.sec = sec
	e.repeat = repeat

	def timer_f():
		e.obj = None
		if e.f:
			e.f( *e.args )
		if e.repeat:
			start( repeat=True )
	def start(f=None, args=[], sec=-1, repeat=False):
		cancel()
		if f:
			e.f = f
			e.args = args
		if sec >=0 :
			e.sec = sec
		e.repeat = repeat
		e.obj = threading.Timer( e.sec, timer_f )
		e.obj.start()
	e.start = start

	def cancel():
		if e.obj:
			e.obj.cancel()
			e.obj = None
	e.cancel = cancel
	return e

def th_loop(f, args=[], hz=0, sta=True):
	e = Empty()
	e.hz = hz
	e.run = sta
	ev = threading.Event()
	def loop():
		while not ev.wait( hz_to_sec(e.hz) ):
			# sec == 0 when hz == 0
			if e.run:
				f( *args )
	th = threading.Thread( target=loop )
	th.daemon = True
	e.stop = lambda: set(e, 'run', False)
	e.start = lambda: set(e, 'run', True)
	e.kill = ev.set
	e.join = th.join
	e.kill_join = lambda: ( e.kill(), e.join() )[-1]
	th.start()
	return e

def flicker(hz=1.0, f=None, args=[], sta=False):
	def th_f():
		set(e, 'v', not e.v)
		if has(e, 'f'):
			e.f( *e.args )

	e = extends( th_loop(th_f, [], hz*2, sta) )
	e.v = False
	e.get = lambda: e.v
	e.f = f
	e.args = args
	e.set_hz = lambda hz: set(e, 'hz', hz*2)
	return e

def term_raw(sigint=True):
	fd = sys.stdin.fileno()
	a = termios.tcgetattr(fd)
	bak = a[:]
	f = termios.ECHO | termios.ECHONL | termios.FLUSHO | termios.ICANON | termios.IEXTEN
	if not sigint:
		f |= termios.ISIG
	a[3] &= ~f
	termios.tcsetattr(fd, termios.TCSADRAIN, a)
	return lambda : termios.tcsetattr(fd, termios.TCSADRAIN, bak)

def readable(fd, tmout=None):
	(r, _, _) = select.select( [fd], [], [], tmout )
	return r

def getkey(tmout=None):
	fd = sys.stdin.fileno()
	return os.read(fd, 1) if readable(fd, tmout) else ''

esc = lambda s: chr(0x1b) + '[' + s
esc_ex = lambda d, v: esc( '?{}{}'.format(d, 'h' if v else 'l' ) )

DIRS = ( U, D, L, R ) = 'udlr'
bak_dir = lambda d: { U: D, D: U, L: R, R: L }.get(d)
step_to = lambda x, y, d: { U: (x, y-1), D: (x, y+1), L: (x-1, y), R: (x+1, y) }.get( d, (x, y) )

def keydir(tmout=None):
	ctl = lambda s: chr( 1 + ord(s) - ord('a') )
	lst = [ # up, down, left, right
		[ esc('A'), esc('B'), esc('D'), esc('C') ], # allow
		[ ctl('p'), ctl('n'), ctl('b'), ctl('f') ], # emacs
		[ 'k', 'j', 'h', 'l' ], # vi
	]
	d = dict( sum( map( lambda k4: zip(k4, DIRS), lst ), [] ) )
	d.update({ ctl('a'): L, ctl('e'): R}) # emacs
	d.update({ '\n': U, '\t': 'U', ' ': 'U' })
	keys = d.keys()
	buf = getkey(tmout)
	while buf and any( map( lambda k: k.startswith(buf), keys ) ):
		if buf in keys:
			return d.get(buf)
		buf += getkey(tmout)
	return ''

cls = lambda : out( esc('2J') )
loc = lambda x, y: out( esc( '{};{}H'.format(y+1, x+1) ) )
rev = lambda v: out( esc( '7m' if v else '0m' ) )
cursor = lambda v: out( esc_ex(25, v) )
cursor_save = lambda : out( esc('s') )
cursor_load = lambda : out( esc('u') )
screen_save = lambda : out( esc_ex(47, 1) )
screen_load = lambda : out( esc_ex(47, 0) )

BW = '-bw' in sys.argv

def color(v):
	if BW:
		return
	lst = [ 'black', 'red', 'green', 'yellow', 'blue', 'magenta', 'cyan', 'white' ]
	if v in lst:
		out( esc( '{}m'.format( 30 + lst.index(v) ) ) )

def show(x, y, s, col, r):
	loc(x, y)
	rev(r)
	nx = x + len(s)
	if col == 'trans':
		loc(nx, y)
	else:
		color(col)
		out(s)
	return nx

lock_show = lock_wrap( show )

def sum_show_lst(lst):
	# lst = [ (s, col, r), (s, col, r) ... ]

	if len(lst) <= 1:
		return lst

	a = (s, col, r) = lst[0]
	lst = sum_show_lst( lst[1:] )
	(s_, col_, r_) = lst[0]
	return [ (s + s_, col, r) ] + lst[1:] if col == col_ and r == r_ else [a] + lst

split_show_lst = lambda lst: sum( map( lambda (s, col, r): map( lambda c: (c, col, r), s ), lst ), [] )

lock_shows = lambda x, y, lst: reduce( lambda x, (s, col, r): lock_show.f(x, y, s, col, r), sum_show_lst(lst), x )

def over_show_lst(l, h):
	get_col = lambda (s, col, r): col
	f = lambda l, h: l if get_col(h) == 'trans' else h

	l = split_show_lst(l)
	h = split_show_lst(h)
	n = max( len(l), len(h) )
	apd = [ (' ', 'trans', False) ] * n
	l = ( l + apd )[:n]
	h = ( h + apd )[:n]
	o = map( lambda (l, h): f(l, h), zip(l, h) )
	return sum_show_lst(o)

trans_to_spc_show_lst = lambda lst: map( lambda (s, col, r): (' ' * len(s), '', False) if col == 'trans' else (s, col, r), lst )

def bit_w(v): # only positive value
	w = 0
	while v:
		v >>= 1
		w += 1
	return w

loop_xy = lambda w, h, f: sum( map( lambda y: map( lambda x: f(x, y), range(w) ), range(h) ), [] )

lst_xy = lambda w ,h: loop_xy( w, h, lambda x, y: (x, y) )

chk_xy = lambda x, y, w, h: x in range(w) and y in range(h)

into_x = lambda x, iw, ow: max( min( ow - iw, x ), 0 )
into_xy = lambda x, y, iw, ih, ow, oh: ( into_x(x, iw, ow), into_x(y, ih, oh) )

def arr_xy_new(w, h, v):
	e = Empty()
	e.data = data = map( lambda _: [ v ] * w, range(h) )
	e.size = lambda: (w, h)
	e.chk_xy = lambda x, y: chk_xy(x, y, w, h)
	e.get = lambda x, y, v=None: data[y][x] if e.chk_xy(x, y) else v
	e.set = lambda x, y, c: set( data[y], x, c ) if e.chk_xy(x, y) else None
	e.clear = lambda c: loop_xy( w, h, lambda x, y: e.set(x, y, c) )
	def pos(c):
		lst = filter( lambda (x, y): e.get(x, y) == c, lst_xy(w, h) )
		return lst[0] if len(lst) == 1 else lst
	e.pos = pos
	return e

def arr_xy_bit_new(w, h):
	pat = lambda bit: 1 << bit if bit >= 0 else 0
	chg = lambda v, bit, bv: v | pat(bit) if bv else v & ~pat(bit)
	arr = arr_xy_new(w, h, 0)
	e = extends(arr)
	e.get = lambda x, y, bit: arr.get(x, y, 0) & pat(bit)
	e.set = lambda x, y, bit, bv: arr.set( x, y, chg( arr.get(x, y), bit, bv ) )
	e.clear = lambda: arr.clear(0)
	e.gets = lambda x, y: filter( lambda bit: e.get(x, y, bit), range( bit_w( arr.get(x, y, 0) ) ) )
	return e

def arr_xy_bit_c_new(w, h, bit_cs):
	arr_bit = arr_xy_bit_new(w, h)
	e = extends(arr_bit)
	e.to_bit = to_bit = dict( zip( bit_cs, range( len(bit_cs) ) ) )
	e.get = lambda x, y, c: arr_bit.get( x, y, to_bit.get(c, -1) )
	e.set = lambda x, y, c, v: arr_bit.set( x ,y, to_bit.get(c, -1), v )
	e.gets = lambda x, y: map( lambda bit: bit_cs[bit], arr_bit.gets(x, y) )
	return e

def arr_xy_bit_c_show_new(w, h, bit_cs, c_to_show_lst, xy_to_view, update_border=(0,0)):
	# c_to_show_lst(c, x, y) return [ (s, col, r), (s, col, r) ... ]

	arr_bit_c = arr_xy_bit_c_new(w, h, bit_cs)
	e = extends(arr_bit_c)

	def update(x, y):
		cs = []
		if update_border != (0,0):
			(bw, bh) = update_border
			xys = map( lambda (dx, dy): (x+dx-bw, y+dy-bh), lst_xy(bw*2+1, bh*2+1) )
			cs = sum( map( lambda (x, y): e.gets(x, y), xys ), [] )
			cs = reduce( lambda cs, c: cs if c in cs else cs + [c], cs, [] )
			cs.sort( key=lambda c: bit_cs.index(c) )
		else:
			cs = e.gets(x, y)

		show_lsts = map( lambda c: c_to_show_lst(c, x, y), cs )
		show_lst = reduce( over_show_lst, reversed( show_lsts ), [] )
		show_lst = trans_to_spc_show_lst(show_lst) if show_lst else [ ('  ', '', False) ]

		(x, y) = xy_to_view(x, y)
		lock_shows(x, y, show_lst)

	e.update = update
	return e

def rbuf(fname):
	(buf, w, h) = ([], 0, 0)
	with open(fname, 'r') as f:
		buf = f.read().strip().split( os.linesep )
		h = len(buf)
		w = max( map(len, buf) )
		buf = map( lambda s: s + ' ' * ( w - len(s) ), buf ) # fill

	arr = arr_xy_new(w, h, ' ')
	e = extends(arr)
	loop_xy( w, h, lambda x, y: arr.set( x, y, buf[y][x] ) )
	return e

def main(f, help_msg):
	if '-h' in sys.argv:
		print 'Usage: {} {}'.format( sys.argv[0], help_msg )
		sys.exit(0)
	try:
		restore = term_raw()
		screen_save()
		cursor_save()
		cursor(False)
		f()
	finally:
		cursor(True)
		cursor_load()
		screen_load()
		restore()
# EOF