Problem A. Homo or Hetero? ≡

Statement

Consider a list of numbers with two operations:

• insert number — adds the specified number to the end of the list.
• delete number — removes the first occurrence of the specified number from the list. If the list does not contain the number specified, no changes are performed.

For example: the result of the insertion of a number 4 to the list [1, 2, 1] is the list [1, 2, 1, 4]. If we delete the number 1 from this list, we get the list [2, 1, 4], but if we delete the number 3 from the list [1, 2, 1, 4], the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list [2, 2] is homogeneous, the list [2, 1, 4] is heterogeneous, the list [1, 2, 1, 4] is both, and the empty list is neither homogeneous nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list's homogeneity and heterogeneity after each operation.

Input file format

The first line of the input file contains an integer number n — the number of operations to handle (1 ≤ n ≤ 100 000).

Following n lines contain one operation description each. The operation description consists of a word insert or delete, followed by an integer number k — the operation argument (−10⁹ ≤ k ≤ 10⁹).

Output file format

For each operation output a line, containing a single word, describing the state of the list after the operation:

• both  — if the list is both homogeneous and heterogeneous.
• homo  — if the list is homogeneous, but not heterogeneous.
• hetero  — if the list is heterogeneous, but not homogeneous.
• neither — if the list is neither homogeneous nor heterogeneous.

Sample tests

11
insert 1
insert 2
insert 1
insert 4
delete 1
delete 3
delete 2
delete 1
insert 4
delete 4
delete 4

neither
hetero
both
both
hetero
hetero
hetero
neither
homo
neither
neither

Problem B. Jealous Numbers ≡

Statement

There is a trouble in Numberland, prime number p is jealous of another prime number q. She thinks that there are more integer numbers between a and b, inclusively, that are divisible by greater power of q than that of p. Help p to get rid of her feelings.

Let α(n, x) be maximal k such that n is divisible by x^k. Let us say that a number n is p-dominating over q if α(n, p)>α(n, q). Find out for how many numbers between a and b, inclusive are p-dominating over q.

Input file format

The first line of the input file contains a, b, p and q (1 ≤ a ≤ b ≤ 10¹⁸; 2 ≤ p, q ≤ 10⁹; p ≠ q; p and q are prime).

In the given example 3, 9, 15 and 18 are 3-dominating over 2.

Output file format

Output one number — how many numbers n between a and b, inclusive, are p-dominating over q.

Sample tests

1 20 3 2

4

Задача C. Набор сотрудников ≡

Условие

Молодой программист Вася недавно написал очень популярное и полезное веб-приложение, которое привлекло внимание спонсоров.

Теперь у Васи есть много денег, и он может основать свою компанию! Но для этого ему нужны сотрудники. Вася хочет чтобы у него в компании было два отдела. В первом отделе программисты будут заниматься разрабатыванием и тестированием новых идей, во втором - внедрением надежных и протестированных разработок первого отдела в приложение Васи.

Вася дал объявление о наборе сотрудников в каждый отдел и сейчас он имеет на руках список желающих. Каждый желающий указал, в какой отдел он хочет идти работать, либо указал, что готов работать в любом отделе. Тем не менее, Вася может нанять любого желающего только в один из отделов.

Каждому человеку из списка Вася поставил в соответствие некоторое целое число, которое характеризует полезность данного человека для компании. Теперь Вася хочет нанять сотрудников в оба отдела своей компании, так чтобы суммарная их полезность была максимально возможной.

Однако сотрудникам надо платить зарплату, а количество денег у Васи строго ограничено, поэтому он заранее указал количество сотрудников, которое он может нанять в каждый отдел.

Вам требуется написать программу, которая укажет, каких сотрудников нанял Вася в каждый отдел.

Формат входного файла

Первая строка входного файла содержит целые числа N, M, K  — количество желающих работать у Васи в компании, количество сотрудников, которое может нанять Вася в первый и второй отдел соответственно.

Вторая строка содержит N целых чисел a_i  — полезность желающего с номером i.

Третья строка содержит N целых чисел d_i, имеющих значения 1,2 либо 0  — 1, если i-й желающий хочет работать в первом отделе, 2  — во втором, либо 0  — в обоих.

Формат выходного файла

В первой строке входного файла требуется вывести N₁  — количество сотрудников, нанятых в первый отдел и N₁ целых чисел  — номера желающих, нанятых в данный отдел. Желающие пронумерованы начиная с 1.

В первой строке входного файла требуется вывести N₂  — количество сотрудников, нанятых во второй отдел и N₂ целых чисел  — номера желающих, нанятых в данный отдел.

Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N, M, K ≤ 100000.

1 ≤ a_i ≤ 10⁴.

Примеры тестов

1 1 1
123
1

1 1
0

2 1 1
123 145
1 1

1 2
0