#include <iostream>
using namespace std;

template <class TYPE, class MODIFICATION_TYPE> class segments_tree
{
	TYPE *SegmentTree;
	MODIFICATION_TYPE* ModifierList;
	size_t base_capacity;
	TYPE (*g)(const TYPE&, const TYPE&);
	TYPE (*m)(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&);
	MODIFICATION_TYPE (*combine_modifications)(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&);
	TYPE neutral;
	MODIFICATION_TYPE neutral_modifier;

	/*
	TYPE:
		Type of elements in the tree.

	MODIFICATION_TYPE:
		Special type, which allows to synchronize modifications on segment.

	SegmentTree: (pointer)
		Array-based tree of elements.

	base_capacity: (unsigned integer value)
		Parental array size, rounded to the closest upper power of 2.

	g: (pointer)
		Pointer to the funtion (associative binary operation), applied on the given array of elements.
		WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

	m: (pointer)
		Pointer to the function, used to modify segments of the tree.
	
	combine_modifications: (pointer)
		Pointer to the function, which combines old and new modifications to synchronize them.

	neutral: (array element)
		The value of element, which is neutral relatively to "g" function.

	neutral_modifier:
		Marker of non-modified vertexes.

	################################
	#### INNER HELPER FUNCTIONS ####
	################################
	try_push: pushes the modifier value from vertex to its left and right leaf.
	*/
	void try_push(size_t& v, size_t& tl, size_t& tr)
	{
		if (v < base_capacity) if (ModifierList[v] != neutral_modifier)
		{
			size_t mid = (tr+tl)/2, i = 2*v;
			SegmentTree[i] = m(SegmentTree[i], tl, mid, ModifierList[v]);
			SegmentTree[i+1] = m(SegmentTree[i+1], ++mid, tr, ModifierList[v]);

			if (i+1 < base_capacity)
			{
				ModifierList[i] = combine_modifications(ModifierList[i], ModifierList[v]);
				ModifierList[i+1] = combine_modifications(ModifierList[i+1], ModifierList[v]);
			}

			ModifierList[v] = neutral_modifier;
		}
	}

	/*
	assign_in:
		assigns a new values to the vertexes of the tree,
		which are responsible for the value of [l; r] segment.
	*/
	void assign_in
	(
		size_t v,
		size_t tl, size_t tr,
		size_t l, size_t r,
		const MODIFICATION_TYPE& new_modification
	)
	{
		if (l <= r)
		{
			try_push(v, tl, tr);
			if (l == tl && tr == r)
			{
				SegmentTree[v] = m(SegmentTree[v], tl, tr, new_modification);
				if (v < base_capacity) ModifierList[v] = new_modification;
			}
			else
			{
				size_t tm = (tl + tr) / 2;
				
				assign_in(2*v, tl, tm, l, min(r,tm), new_modification);
				assign_in(2*v+1, tm+1, tr, max(l,tm+1), r, new_modification);
				
				SegmentTree[v] = g(SegmentTree[2*v], SegmentTree[2*v+1]);
			}
		}
	}

	/*
	result_on_segment_in:
		returns value on segment [l, r];
	*/
	TYPE result_on_segment_in
	(
		size_t v, size_t tl,
		size_t tr, size_t l,
		size_t r
	)
	{
		if (l > r) return neutral;
		else
		{
			if (l == tl && r == tr) return SegmentTree[v];
			else
			{
				try_push(v, tl, tr);
				size_t tm = (tl + tr) / 2;
				return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
				result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
			}
		}
	}

	/*
	make_monoid_and_fill_rest:
		- fills the unused space of array (which appears due to rounding of size of parental array)
		with neutral elements.
		- assigns the necessary values to the upper "vertexes" of the tree.
	*/
	void make_monoid_and_fill_rest
	(
		TYPE *NewTree,
		const size_t &n,
		TYPE f(const TYPE&, const TYPE&),
		const TYPE &neutr,
		TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
		MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
		const MODIFICATION_TYPE &new_neutral_modifier
	)
	{
		g = f;
		m = modifier_function;
		combine_modifications = modification_combinator;
		neutral = neutr;
		neutral_modifier = new_neutral_modifier;
		for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
		{
			NewTree[i] = neutral;
		}
		for(size_t i = base_capacity-1; i > 0; --i)
		{
			NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
			ModifierList[i] = neutral_modifier;
		}
		ModifierList[0] = neutral_modifier;
		SegmentTree = NewTree;
	}

	/*
	fix_capacity:
		Rounds base_capacity of the base array to closest upper power of 2.
	*/
	void fix_capacity(const size_t &base_array_size)
	{
		for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
	}

	public:
	/*
	##########################
	#### PUBLIC FUNCTIONS ####
	##########################
	Definitions:
		n - amount of elements in the parental array;
		lb - binary logarithm.
		Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
		and (if exists) unused space, filled with neutral elements.

	construct:
		Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
		and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
		Complexity: O(n).
	*/
	void construct
	(
		const TYPE *begin,
		const TYPE *end,
		TYPE f(const TYPE&, const TYPE&),
		const TYPE neutr,
		TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
		MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
		const MODIFICATION_TYPE new_neutral_modifier
	)
	{
		size_t base_size = end - begin;
		fix_capacity(base_size);
		TYPE *NewTree = new TYPE[base_capacity*2];
		ModifierList = new MODIFICATION_TYPE[base_capacity];
		for(size_t i = 0; i < base_size; ++i)
		{
			NewTree[base_capacity+i] = begin[i];
		}
		make_monoid_and_fill_rest(NewTree, base_size, f, neutr, modifier_function, modification_combinator, new_neutral_modifier);
	}

	/*
	read_and_construct:
		Constructs the tree by filling with it with elements, created by "preprocessing_function",
		and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
		This method is useful for creating tree by giving preprocessing_function an ability to read
		the data from the incoming stream, if the separate memorisation of the base array is not needed.
		Complexity: O(n).
	*/
	void read_and_construct
	(
		const size_t amount_of_elements,
		TYPE preprocessing_function(),
		TYPE f(const TYPE&, const TYPE&),
		const TYPE neutr,
		TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
		MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
		const MODIFICATION_TYPE new_neutral_modifier
	)
	{
		fix_capacity(amount_of_elements);
		TYPE *NewTree = new TYPE[base_capacity*2];
		ModifierList = new MODIFICATION_TYPE[base_capacity];
		for(size_t i = 0; i < amount_of_elements; ++i)
		{
			NewTree[base_capacity+i] = preprocessing_function();
		}
		make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr, modifier_function, modification_combinator, new_neutral_modifier);
	}

	/*
	assign:
		Assigns new value to the element of base array with given index [i]
		or modifies the given segment [l, r], relatively to the modifier value.
		Complexity: O(lb(n))
	*/
	void assign(size_t i, const MODIFICATION_TYPE modifier)
	{
		assign_in(1, 0, base_capacity-1, i, i, modifier);
	}

	void assign(size_t l, size_t r, const MODIFICATION_TYPE modifier)
	{
		assign_in(1, 0, base_capacity-1, l, r, modifier);
	}

	/*
	result_on_segment:
		Returns value of operation on the given segment of parental array.
		Complexity: O(lb(n)).
	*/
	TYPE result_on_segment(size_t l, size_t r)
	{
		return result_on_segment_in(1, 0, base_capacity-1, l, r);
	}
};

int main()
{
	return 0;
}