Dосстановление windows Контактная информация Карта сайта Cкачать Flash программы
Новости О компании Услуги восстановления данных Партнерская программа Контакты
 
   

2005-05-02

Восстановление информации с поврежденных разделов NTFS

Опишем процесс ручного восстановления случайно удаленных файлов или файлов из поврежденных разделов системы NTFS при работе в ОС Windows NT. Проблема заключается в том, что в составе этой ОС нет соответствующих программных средств. Программы же восстановления NTFS от сторонних производителей, к сожалению, труднодоступны и дороги. Ситуация усугубляется отсутствием полной документации по низкоуровневой структуре управляющих блоков NTFS.

Что же делать, если в один прекрасный момент обнаруживается, что компьютер с ОС Windows NT больше не загружается или некоторые логические разделы NTFS стали вдруг недоступны?

Сначала нужно уточнить, с чем связана неисправность: физическим повреждением диска, выходом из строя контроллера или разрушением файловой системы NTFS.

Проблемы с диском

Жесткие диски имеют ограниченный срок службы, обычно - несколько лет. Выход устройства из строя иногда можно определить по характерным щелчкам в момент инициализации. Диск может несколько раз щелкнуть и затихнуть, так и не раскрутившись. При инициализации BIOS сообщит вам об этой неисправности. В такой ситуации следует произвести ремонт жесткого диска. Если стоимость потерянной информации заметно превышает стоимость самого диска, следует обратиться к специалистам, что, впрочем, недешево.

Ремонт выполняется следующим образом. Если из строя вышла электроника, расположенная вне герметичного пространства диска, то заменяется или ремонтируется соответствующая плата. Для этого часто приходится разбирать другой диск точно такого же типа.

В том случае, когда повреждены детали, расположенные внутри корпуса диска, проблем будет больше. Прежде всего, разбирать сломанный диск нужно в так называемой <чистой комнате>, где гарантируется отсутствие пыли. Затем следует заменить плату с электроникой, сняв ее с другого диска. Отремонтированный диск закрывается, после чего остается только скопировать информацию на третий диск по секторам.

Поэтому если сломался жесткий диск с ценной информацией, приготовьтесь пожертвовать еще одним для ремонта и найдите третий для копирования восстановленных данных.

Если есть подозрение на неисправность контроллера диска, попробуйте его заменить. Проверьте также соединительный кабель.

Проблемы с файловой системой

Убедившись, что диск, контроллер и соединительный кабель исправны, не торопитесь использовать дискету NT Repair Disk, созданную при установке ОС, или запускать программу восстановления файловой системы chkdsk - результат может оказаться плачевным. Не пытайтесь также найти <волшебную> программу восстановления NTFS в комплекте Norton Utilities для Windows NT - пока ее там нет. Если информация, записанная на диске, имеет особую ценность, нужно вначале проанализировать состояние управляющих блоков файловой системы NTFS с помощью редактора диска.

Такая работа требует достаточно высокой квалификации. В частности, нужно разбираться в форматах управляющих блоков файловой системы. Если вы не в состоянии выполнить ее самостоятельно, лучше вызвать специалиста и не предпринимать попыток самому отремонтировать NTFS.

Чтобы проверить управляющие блоки, нужно подключить к компьютеру два диска: первый, исправный загрузочный, и второй - тот, информацию с которого необходимо восстановить.

Сначала подключается только первый диск и инсталлируется ОС Windows NT. Этот диск будет использован для сохранения файлов, восстановленных из разделов поврежденного. Далее устанавливается редактор Disk Probe, входящий в состав Windows NT Resource Kit. Хотя этот редактор далек от совершенства, именно он позволит выполнить всю работу по восстановлению потерянных файлов.

Убедившись, что с первым диском все в порядке, выключите компьютер и подключите к нему второй, поврежденный диск.

Определение геометрии логического устройства

Для успешного восстановления информации следует определить размер кластера и адрес загрузочного сектора. Первое значение можно получить из загрузочного сектора раздела NTFS (если, конечно, его содержимое сохранилось).

Запустите программу Disk Probe. Выберите в меню Drive позицию Physical Drive. В панели Open Physical Drive, появившейся на экране, укажите устройство PhysicalDrive1, дважды щелкнув левой клавишей мыши по соответствующей строке списка Available Physical Drives. Затем нажмите кнопку Set Active, оставив включенным переключатель Read Only, и закройте панель кнопкой OK (рис. 1).


Рис. 1. Выбор физического диска

В результате программа Disk Probe получит доступ на чтение поврежденного диска. После этого попытайтесь прочитать содержимое главной загрузочной записи диска, расположенной в первом секторе на нулевой дорожке нулевого цилиндра. Для этого в меню Sectors выберите строку Read. Появится панель Read Sector. В поле Starting Sector укажите номер первого сектора, равный нулю, а в поле Numbers of Sectors установите значение 1. Затем нажмите кнопку Read.

Программа считает в оперативную память содержимое первого сектора и покажет его в шестнадцатеричном виде. Выберите из меню View строку Partition Table для форматного просмотра таблицы разделов диска, а затем перейдите на нужный раздел с помощью кнопки Go. Если необходимо (когда восстанавливаются файлы из расширенного раздела), повторите эту процедуру несколько раз.

Добравшись до загрузочной записи нужного вам раздела, выберите из меню View строку NTFS Bootsector. Вы должны увидеть что-то вроде изображения на рис. 2.


Рис. 2. Просмотр загрузочного сектора раздела NTFS

Здесь содержатся все сведения о геометрии восстанавливаемого раздела. В частности, размер кластера в секторах находится в поле Sectors per cluster. Кроме того, здесь приведены номера кластеров основной и резервной таблицы MFT (поля Clusters to MFT и Clusters to MFT mirr соответственно).

А что делать, если главная загрузочная запись или загрузочная запись нужного раздела уничтожены?

Эта ситуация тяжелая, но не фатальная. Подробную таблицу соответствия емкости логического устройства NTFS и числа кластеров можно найти в MSDN. Например, если емкость находится в интервале 1025 - 2048 Мбайт, размер кластера будет равен 4 секторам, а если в диапазоне от 8193 до 16 384 Мбайт - то в одном кластере будет 32 сектора. Заметим, однако, что, позаботившись заранее о возможности последующего восстановления диска в случае его повреждения, можно облегчить такую работу, когда в ней возникнет необходимость. Нужно определить и записать размер кластера сразу после установки ОС, пока загрузочный сектор NTFS еще цел.

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

Таблица MFT

Внутренняя структура файловой системы NTFS принципиально отличается от хорошо знакомой большинству FAT. Не вдаваясь в подробности, изложим лишь те сведения, которые необходимы для выполнения в ней восстановительных работ.

Файловая система FAT (и ее разновидность FAT32) хранит информацию о файлах в нескольких местах логического устройства. Дескриптор файла, содержащий его имя, размер, дату создания и номер первого выделенного для него кластера, находится в каталоге. Таблица размещения файлов File Allocation Table, от которой и произошло название файловой системы FAT, хранит связанный список всех кластеров, выделенных файлу. И наконец, сам файл может быть распылен по кластерам.

Такая организация в значительной мере затрудняет восстановление файлов в случае каких-либо сбоев. Особенно критичной является целостность таблицы FAT: если эта таблица пропала или ее содержимое оказалось частично разрушено, исчезает информация о кластерах, выделенных файлу. В результате файл можно с очень большим трудом собрать из отдельных кластеров, лишь зная его содержимое. К тому же эта работа требует очень много времени. Поэтому на практике исчезновение таблицы FAT и ее копии означает полную потерю файлов.

Потеря каталогов приводит к невозможности определения номера первого кластера, выделенного файлу, его имени и точного размера. В этом случае последствия не столь катастрофичны, так как в таблице FAT остались <бесхозные> цепочки кластеров, которые нетрудно превратить в файлы. Имена полученных таким образом файлов обычно состоят из цифр. Заметим, что при крушении каталогов, содержащих тысячи файлов, после восстановления будет трудно найти нужный файл, если хотя бы приблизительно не известно его содержимое.

В файловой системе NTFS вся информация о файлах хранится в так называемой главной таблице файлов Master File Table (MFT). Записи таблицы MFT содержат наборы дескрипторов с такой информацией о файлах, как имя, даты создания и модификации, атрибуты безопасности, и, что самое главное, списки кластеров, выделенных файлам. Если файл имеет небольшой размер, то он может храниться непосредственно в записи таблицы MFT.

Следовательно, возможность восстановления файлов из поврежденных разделов NTFS во многом определяется целостностью таблицы MFT и ее копии.

Как найти таблицу MFT?

Найти таблицу MFT достаточно просто, если сохранился загрузочный сектор раздела NTFS. Нажмите кнопку Go около поля Clusters to MFT или Clusters to MFT mirr в панели, показанной на рис. 2. Для просмотра содержимого первого сектора таблицы выберите из меню View программы Disk Probe строку Bytes. Результат выполнения такой операции показан на рис. 3.


Рис. 3. Содержимое первого сектора таблицы MFT

Обратите внимание на строку FILE, расположенную в самом начале сектора. С нее начинаются записи таблицы, описывающие файлы. Существуют еще записи для каталогов, элементов индекса и другие, которые мы не будем рассматривать.

Строка $.M.F.T. находится со смещением D2. Это имя системного файла, содержащего таблицу MFT, в кодировке Unicode. Таким образом, первая запись файла $MFT описывает сам этот файл. Просматривая таблицу, можно обнаружить записи для других системных файлов, таких как $MFTMirror, $LogFile, $Volume, $AttrDef и др.


Рис. 4. Поиск начала таблицы MFT

Если загрузочный сектор разрушен, начало таблицы MFT нетрудно найти с помощью программы Disk Probe. Для этого выберите в меню Tools строку Search Sector, установите переключатели в положение, показанное на рис. 4, и, заполнив поле Enter characters to search for, нажмите кнопку Search. Следует запастись терпением, поскольку процесс поиска может отнять немало времени.

Заметим, что подобным образом можно найти в таблице MFT записи для тех файлов, которые нужно восстановить. Так как имена файлов хранятся в кодировке Unicode, при поиске следует установить переключатель в положение Unicode characters. Кроме того, необходимо включить режим поиска Exhaustive search и Ignore case.

Анализ записей MFT

К сожалению, программа Disk Probe не содержит никаких средств для форматного просмотра содержимого записей MFT. Более того, точный формат этой записи отсутствует в открытой документации Microsoft. Однако многое можно обнаружить в Internet, сделав запрос по ключевым словам . Нам, например, удалось найти информацию, собранную разработчиками модулей для операционной системы Linux. Анализируя исходные тексты модуля для монтирования в Linux файловой системы NTFS, можно понять назначение отдельных полей записей MFT (авторы приносят благодарность Максиму Синеву за помощь в <расшифровке> записей MFT).

Запись MFT состоит из начального фрагмента фиксированного размера и набора атрибутов, имеющих в общем случае переменный размер. Для восстановления файлов нужно знать точный формат только атрибута данных. Что же касается других атрибутов, достаточно уметь определять их расположение и размер.

Первые четыре байта в записи, описывающей файл, образуют слово FILE. На рис. 3 они выделены красным цветом. Следующие два байта (выделенные синим цветом) - смещение так называемой области Fixup. В рассматриваемом случае значение смещения равно 002A (с учетом обратного порядка расположения байтов в слове). Здесь и далее будем пользоваться шестнадцатеричными числами.

Область Fixup используется в процессе обнаружения ошибок чтения или записи. Она состоит из слов размером два байта. Количество слов хранится в записи MFT со смещением 0006. На рис. 3 поле размера области Fixup выделено фиолетовым цветом. Там хранится значение 0003, следовательно, область Fixup начинается со смещения 002A и простирается до 002A+(2*0003)=002F.

Сразу за областью Fixup начинаются поля атрибутов. Смещение первого атрибута равно 0030.

Первые четыре байта области атрибутов определяют тип, а следующие четыре - размер в байтах. Например, вслед за областью Fixup со смещением 0030 следует атрибут с типом 10. На рис. 3 тип этого и следующего за ним атрибутов выделен красным цветом (размер атрибута выделен синим). Атрибут занимает 48 байт, следовательно, следующий атрибут (с типом 30) начнется со смещением 0078.

Таким образом можно выделить в записи MFT все атрибуты. В конце самого последнего записано значение FFFFFFFF - признак конца цепочки атрибутов.

Для восстановления файлов наибольший интерес представляют атрибуты типа 30 и 80. Первый из них хранит имя файла. По нему следует искать запись MFT, описывающую восстанавливаемый файл. Второй атрибут с типом 80 хранит список кластеров, выделенных файлу, или сам файл. Про него мы расскажем подробнее. Для удобства описание атрибута данных выделено на рис. 5.


Рис. 5. Атрибут данных

Как видно из рисунка, тип атрибута, равный 80, хранится в записи MFT со смещением 0160. Всего атрибут данных занимает D8 байт, так как именно это значение находится в четырехбайтовом поле со смещением 4 относительно начала атрибута.

Байт со смещением 8 относительно начала атрибута данных - это признак резидентного размещения файла. Если его значение равно 1, запись MFT хранит только список кластеров, выделенных файлу (как в описываемом случае), а если 0 - файл находится внутри самой записи MFT. Как правило, записи содержат только файлы небольших размеров.

Сначала рассмотрим случай нерезидентного размещения файла. При этом четыре байта со смещением 30 хранят длину файла, расположенного где-то на диске. В данном примере длина файла $MFT составляет B7B000 байт.

Для того чтобы определить точное расположение нерезидентного файла на диске, нужно проследить цепочку так называемых блоков виртуальных номеров кластеров Virtual Cluster Number (VCN), или просто блоков VCN. Показатель смещения начала этой цепочки хранится в двухбайтовом поле, имеющем смещение 20 байт относительно начала атрибута данных. В описываемом случае этот показатель равен 40, а смещение области блоков VCN относительно начала записи MFT равно 01A0. На рис. 5 эта область выделена жирной вертикальной линией зеленого цвета.

Анализ области блоков VCN

Файл, записанный в разделе NTFS, может быть сегментирован. Он состоит из одного или нескольких фрагментов, называемых экстентами. Размер и расположение каждого экстента описывается в блоке VCN. В зависимости от того, фрагментирован файл или нет, область VCN может содержать один блок или их набор. Блоки VCN имеют переменный размер, определяемый первым байтом.

Формат блока стоит показать на конкретном примере. Возьмем первый блок VCN, имеющий в рассматриваемом примере смещение 01A0 относительно начала записи MFT:

31 20 D9 86 02

Тетрады первого байта со значением 31 определяют размеры двух полей блока VCN. Первое поле, имеющее длину один байт, хранит количество кластеров, выделенных экстенту файла. Второе поле размером три байта содержит номер первого кластера. В данном случае первому экстенту файла $MFT выделено 20 кластеров, а номер первого кластера для первого экстента равен 0286D9. Таким образом определяем размер и расположение первого экстента файла.

Второй блок VCN расположен сразу вслед за первым:

12 24 08 21

Для того чтобы определить первый кластер второго экстента, необходимо прибавить к адресу первого экстента смещение, указанное во втором блоке VCN (с учетом знака). В данном случае второй экстент размещен в кластере с номером 0286D9+21=286FA. Длина второго экстента составляет 0824 кластера.

Анализируя остальные блоки VCN, можно определить размеры и расположение всех экстентов файла. Список блоков VCN закрывается байтом с нулевым значением.

Резидентные файлы

Файлы небольшого размера размещаются непосредственно в записи MFT, описывающей этот файл, для сокращения времени доступа. Если в байте со смещением 8 относительно начала атрибута данных находится нулевое значение, то не нужно прослеживать цепочки блоков VCN. Это означает, что файл находится внутри атрибута данных.


Рис. 6. Запись таблицы MFT с резидентным атрибутом

При этом смещение резидентных данных, т. е. файла, записано в двухбайтовом слове со смещением 14 относительно начала атрибута данных, а размер - в двухбайтовом слове со смещением 10.

Приведем небольшой пример. Для иллюстрации формата записи MFT, содержащей резидентный атрибут данных, мы подготовили маленький файл с именем Small.txt, содержащий текстовую строку . Затем с помощью программы Disk Probe мы обнаружили запись таблицы MFT, созданную для этого файла (рис. 6).

Здесь атрибут данных начинается со смещением 0160 относительно начала записи MFT. Байт со смещением 8 внутри этого атрибута (выделен зеленым цветом) равен нулю, следовательно, мы имеем дело с резидентным атрибутом.

Как видно из рис. 6, байты файла Small.txt (выделенные желтым цветом) находятся внутри записи MFT со смещением 18 относительно начала атрибута данных, а размер файла составляет 1A байт.

Как же восстановить файлы?

Теперь, вооружившись приведенными выше знаниями о внутренней структуре системных блоков NTFS, можно приступить к восстановлению файлов из поврежденного раздела этой файловой системы.

Когда известны имена файлов, подлежащих восстановлению, нужно найти соответствующие им записи в таблице MFT. Это можно сделать с помощью программы Disk Probe, воспользовавшись строкой Search Sector из меню Tools. Далее следует обнаружить в этой записи атрибут данных и определить, резидентный он или нет.

Если атрибут данных резидентный, то нужно сохранить сектор, содержащий запись MFT, в виде файла на исправном жестком диске или на дискете. Это можно сделать, используя строку Save as меню File программы Disk Probe. После этого следует вырезать нужную часть данных и сохранить результат в новом файле. Такую операцию нетрудно выполнить, например, в редакторе Norton Disk Editor для MS-DOS.

В случае нерезидентного атрибута работы будет намного больше.

Прослеживая цепочку блоков VCN, нужно определить расположение и размер экстентов восстанавливаемого файла. Далее с помощью приложения Disk Probe следует прочитать данные экстента, а затем сохранить их в файле на исправном диске. Не забудьте также, что в программе Disk Probe указывается количество секторов, которые нужно прочитать или записать, а в блоке VCN установлено количество кластеров, выделенных экстенту. Поэтому нужно выполнить соответствующий пересчет.

Восстановив все экстенты, объедините их в один файл (например, командой COPY с параметром /B). Затем установите правильную длину файла, полученную из поля со смещением 30 атрибута данных. В разделе FAT такая операция может быть выполнена с помощью все той же программы Norton Disk Editor.

К сожалению, на практике восстановление большого количества файлов требует много времени. Тяжелее всего дается ручная обработка цепочек блоков VCN, которые могут быть очень длинными. Приходится часами работать с калькулятором, переводя десятичные числа в шестнадцатеричные и обратно, а также производя различные арифметические действия, необходимые для определения размеров и расположения экстентов восстанавливаемых файлов. Поэтому обычно мы пользуемся небольшой самодельной программой NTFS Explorer, выполняющей наиболее трудоемкие операции в полуавтоматическом режиме.

Что же касается полностью автоматических средств, восстанавливающих разрушенные разделы NTFS и случайно удаленные файлы, до здесь можно упомянуть программу Tiramisu for Windows NT, разработанную в компании OnTrack Data International, Inc.

Эта версия, однако, позволяет только просмотреть восстанавливаемые файлы. Если же нужно сохранить имеющуюся в них информацию, приготовьте деньги. У вас есть выбор - заплатить либо 195 долл. за использование программы в течение ограниченного срока (одной недели), либо 390 долл. за версию без ограничений.

Мы все-таки рекомендуем использовать автоматические средства только в крайнем случае, особенно если речь идет о восстановлении особо важных данных. Известно, например, что такая программа, как Norton Disk Doctor, может в некоторых случаях не только не улучшить, но даже ухудшить состояние диска FAT, сделав потерю данных невозвратимой.

К сожалению, всякий раз сталкиваясь с необходимостью восстанавливать разрушенные разделы NTFS, мы убеждались в уникальности проводимой работы, ее приходилось выполнять по-разному в зависимости от причин и последствий аварии. Автоматическая программа вовсе не обязательно сможет принять правильное решение, если после сбоя от данных мало что осталось. С другой стороны, опытный специалист, вооруженный даже простейшим редактором диска, скорее всего, найдет способ восстановить пропавшие файлы.

ОБ АВТОРАХ
Фролов Александр Вячеславович, Фролов Григорий Вячеславович - авторы серий книг <Библиотека системного программиста> и <Персональный компьютер. Шаг за шагом>, их электронные адреса: frolov@glasnet.ru и http://www.glasnet.ru/~frolov

 

2017-06-29
Восстановление данных после Петя/НеПетя
Восстановление данных после заражения вируса-вымогателя Петя/НеПетя - ВОЗМОЖНО!
    ПодробнееПодробнее

2016-06-06
Дешифратор вируса-вымогателя BadBlock
Найдено решение для восстановления информации для всех, кто пострадал от вируса BadBlock
    ПодробнееПодробнее

2016-06-02
Дешифратор для Jigsaw Ransomware версия Invisible Empire
Новая версия вируса-вымогателя - Jigsaw Ransomware, блокируя Ваш экран, использует работы с фотовыставки Invisible Empire
    ПодробнееПодробнее

2016-05-05
Tesla - вирус-вымогатель, найдено решение!
Tesla - вирус-вымогатель, найдено решение! TeslaCrypt - выпустил программу - Мастер ключ для дешифровки данных, которые пострадали от вируса Тесла
    ПодробнееПодробнее

Новости О компании Услуги восстановления данных Партнерская программа Контакты

УТИЛИТЫ ДЛЯ FLASH
ПРОГРАММЫ ВОССТАНОВЛЕНИЯ ДАННЫХ
ПРОГРАММЫ РЕЗЕРВНОГО КОПИРОВАНИЯ

Google+ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1